countChange.scala

package recfun

object Main {
  def main(args: Array[String]) {
  }

  /**
   * Exercise 1
   */
  def pascal(c: Int, r: Int): Int =
    if ((c == 0) || (c == r)) 1
    else pascal(c - 1, r - 1) + pascal(c, r - 1)

  /**
   * Exercise 2
   */
  def balance(chars: List[Char]): Boolean = {
    def isBalanced(m: Int, head: Char, t: List[Char]): Boolean = {
      def balancingLeftParen() =
        if (head == '(') 1
        else 0
      def balancingRightParen() =
        if (head == ')') -1
        else 0

      val currentBalance = m + balancingLeftParen + balancingRightParen

      if(m < 0) return false

      if (t.isEmpty) currentBalance == 0
      else isBalanced(currentBalance, t.head, t.tail)
    }

    chars.isEmpty || isBalanced(0, chars.head, chars.tail)
  }

  def sum(l: List[Int]): Int =
    if(l.isEmpty) 0
    else l.head + sum(l.tail)

  def sumAcc(l: List[Int]) = {
    def sumIter(acc: Int, list: List[Int]): Int =
      if(list.isEmpty) acc
      else sumIter(acc + list.head, list.tail)

    sumIter(0, l)
  }


  /**
   * Exercise 3
   */
  def countChange(money: Int, coins: List[Int]): Int = {
    def countChangeIter(acc: Int, amount: Int, wallet: List[Int]): Int = {
      if(amount == 0) acc + 1
      else if(wallet.isEmpty || amount < 0) acc
      else countChangeIter(acc + countChangeIter(0, amount - wallet.head, wallet), amount, wallet.tail)
    }


    countChangeIter(0, money, coins)
  }
}