Counting change recursive algorithm in Scala

README.md

Scala

Just a few interesting pieces of Scala code

bracketBalance.scala

    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)

    }

countingChange.scala

    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)
    }

sumListOfInts.scala

    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)
  }

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.

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. :)

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

@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.

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)