Assignment Week 1: Functions & Evaluations

recfun.scala

package recfun
import common._

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 = {
    require(c <= r)
    require(c >= 0)
    require(r >= 0)
    if (c == 0 || c == r) 1 else pascal(c, r - 1) + pascal(c - 1, r - 1)
  }

  /**
   * Exercise 2
   */
  def balance(chars: List[Char]): Boolean = {
    def loop(chars: List[Char], left: Int, right: Int): Boolean = {
      if (right > left) false else if (chars.isEmpty) left == right else {
        val head = chars.head
        val tail = chars.tail
        val newLeft = if (head == '(') left + 1 else left
        val newRight = if (head == ')') right + 1 else right
        loop(tail, newLeft, newRight)
      }
    }
    loop(chars, 0, 0)
  }

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

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