Exercises in Scala, Week 1

progfun-week-001

package recfun
import common._
import scala.annotation.tailrec

object Main {
  def main(args: Array[String]) {
    println("Pascal's Triangle")
    for (row <- 0 to 10) {
      for (col <- 0 to row)
        print(pascal(col, row) + " ")
      println()
    }
  }

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

  /**
   * Exercise 2
   */
  def balance(chars: List[Char]): Boolean = {

    @tailrec
    def balanceOpenings(opened: Int, chars: List[Char]): Boolean =
      if (chars.isEmpty) opened == 0
      else if (chars.head == '(') balanceOpenings(opened + 1, chars.tail)
      else if (chars.head == ')') opened > 0 && balanceOpenings(opened - 1, chars.tail)
      else balanceOpenings(opened, chars.tail)

    balanceOpenings(0, chars)

  }

  /**
   * Exercise 3
   */
  def countChange(money: Int, coins: List[Int]): Int = {

    def kittyTheCount(money: Int, coins: List[Int], sum: Int): Int =
      if (money == 0 || coins.isEmpty) 0
      else if (money == sum) 1
      else if (money - sum >= coins.head)
        kittyTheCount(money, coins, coins.head + sum) +
          kittyTheCount(money, coins.tail, sum)
      else kittyTheCount(money, coins.tail, sum)

    kittyTheCount(money, coins.sorted.reverse, 0)
  }
  
}