Skip to content

Instantly share code, notes, and snippets.

@jasonicarter
Last active November 19, 2022 16:54
Show Gist options
  • Save jasonicarter/63ddf092750c9493dfc546f151e14189 to your computer and use it in GitHub Desktop.
Save jasonicarter/63ddf092750c9493dfc546f151e14189 to your computer and use it in GitHub Desktop.
Counting change recursive algorithm in Scala

Scala

Just a few interesting pieces of Scala code

def balance(chars: List[Char]): Boolean = {
def loop(chars: List[Char], stack: Int): Boolean = {
if (chars.isEmpty) stack == 0 // '(' and ')' should result in 0 if balanced
else if (chars.head == '(') loop(chars.tail, stack + 1)
else if (chars.head == ')') loop(chars.tail, stack - 1)
else loop(chars.tail, stack)
}
if (chars.isEmpty) true // if empty, debatable as balanced
else if (chars.head == chars.last) false // if head and last are equal brackets not balanced
else loop(chars, 0)
}
def countChange(money: Int, coins: List[Int]): Int = {
def loop(money: Int, coins: List[Int]): Int = {
if (money < 0 || coins.isEmpty ) 0
else if (money == 0 ) 1
else loop(money, coins.tail) + loop(money - coins.head, coins)
}
loop(money, coins)
}
def sum(xs: List[Int]): Int = {
def loop(xs: List[Int], prevHead: Int): Int = {
if (xs.isEmpty) 0
else if (xs.tail.isEmpty) xs.head+prevHead
else loop(xs.tail, xs.head+prevHead)
}
loop(xs, 0)
}
@aorjoa
Copy link

aorjoa commented Feb 11, 2017

Thank you, i have no idea so far until saw this gist :)

@asolgan
Copy link

asolgan commented Mar 14, 2017

Do you need the nested 'loop' function in counitngChange? Can't it be written with recursion onto itself (countingChange) instead?

@egoetsch101
Copy link

BrackeBalance - else if (chars.head == chars.last) false
What about balance("a()a".toList)
?
I was thinking maybe
" if(chars.isEmpty || x < 0) x ==0"

@lhauspie
Copy link

In the sum function, this part is useless:

        else if (xs.tail.isEmpty) xs.head+prevHead

If you replace this part:

        if (xs.isEmpty) 0

By this part:

        if (xs.isEmpty) prevHead

So the final source code will be:

  def sum(xs: List[Int]): Int = {
    def loop(xs: List[Int], prevHead: Int): Int = {
      if (xs.isEmpty) prevHead
      else loop(xs.tail, xs.head + prevHead)
    }
    loop(xs, 0)
  }

@dimavitvickiy
Copy link

dimavitvickiy commented Feb 19, 2018

def parenthesesBalancing(chars: List[Char]): Boolean = {
  @tailrec
  def parentheses(chars: List[Char], counter: Int): Int = {
    if (chars.isEmpty || counter < 0) counter
    else {
      if (chars.head == '(') parentheses(chars.tail, counter + 1)
      else if (chars.head == ')') parentheses(chars.tail, counter - 1)
      else parentheses(chars.tail, counter)
    }
  }

  parentheses(chars, 0) == 0
}

@dimavitvickiy
Copy link

def sumOfInt(numbers: List[Int]): Int = {
  @tailrec
  def loop(numbers: List[Int], acc: Int): Int = {
    if (numbers.isEmpty) acc
    else loop(numbers.tail, acc + numbers.head)
  }

  loop(numbers, 0)
}

@PyAntony
Copy link

can you please explain how in earth do you figure out stuff like this?

def countChange(money: Int, coins: List[Int]): Int = {

  def loop(money: Int, coins: List[Int]): Int = {
    if (money < 0 || coins.isEmpty ) 0
    else if (money == 0 ) 1
    else loop(money, coins.tail) + loop(money - coins.head, coins)
  }

  loop(money, coins)
}

I have a working function but it's about 14 lines of code.

@fbaierl
Copy link

fbaierl commented Jul 4, 2021

A bit late to the party, but think of it like this:

  • if we have to create a negative amount of money or we do not have any coins at all but have to create a positive amount of money (this check is missing afaik), there are exactly 0 possibilities (trivial case)
  • if we have to create 0, there is exactly 1 possibility (we use no coins)
  • else pick a random coin from coins (in this case via coins.head); now there are two possibilities:
    • either we use that coin, then we can deduct its amount and continue with the same coins-list (since we can still use the same coin again)
      -> loop(money - coins.head, coins)
    • or we do not use that coin (coins.head) at all. Then we can continue our calculation without that coin. Note that coins.tail equals coins without coins.head
      -> loop(money, coins.tail)
      Since in each case we are either deducting from either money or coins, the program is sure to finish.

Tricky, but very fun question. :)

@dksifoua
Copy link

dksifoua commented Jul 6, 2021

Could someone explain to me the intuition behind countChange function? I don't understand it!

@sinoop
Copy link

sinoop commented Dec 12, 2021

@dksifoua :
"Could someone explain to me the intuition behind countChange function? I don't understand it!"

Exercise 3: Counting Change
Write a recursive function that counts how many different ways you can make change for an amount, given a list of coin denominations. For example, there are 3 ways to give change for 4 if you have coins with denomination 1 and 2: 1+1+1+1, 1+1+2, 2+2.

@badbye
Copy link

badbye commented Nov 19, 2022

balance("())(()") returns true, which is not correct.

Here is my solution:

  def balance(chars: List[Char]): Boolean =
    def _balance(value: List[Char], count: Int): Boolean =
      if count < 0 then false
      else if value.isEmpty then count == 0
      else if value.head == ')' then _balance(value.tail, count - 1)
      else if value.head == '(' then _balance(value.tail, count + 1)
      else _balance(value.tail, count)
    _balance(chars, 0)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment