progfun1.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 = {
    def genNextRow(row: IndexedSeq[Int]): IndexedSeq[Int] =
      (0 to row.size).map(i => if (i == 0 || i == row.size) 1
      else row(i - 1) + row(i))

    def pascalIter(r: Int, row: IndexedSeq[Int]): IndexedSeq[Int] =
      if (r == 0) row
      else pascalIter(r - 1, genNextRow(row))

    pascalIter(r, IndexedSeq(1))(c)
  }

  /**
   * Exercise 2
   */
  def balance(chars: List[Char]): Boolean = {
    def parse(p: Char): Int =
      p match {
        case '(' => 1
        case ')' => -1
        case _ => 0
      }

    def balanceIter(head: Char, tail: List[Char], acc: Int): Boolean =
      if (acc < 0) false
      else if (tail.isEmpty) acc + parse(head) == 0
      else balanceIter(tail.head, tail.tail, acc + parse(head))

    balanceIter(chars.head, chars.tail, 0)
  }

  /**
   * Exercise 3
   */
  def countChange(money: Int, coins: List[Int]): Int = {
    def combinations(list: List[Int]): IndexedSeq[List[Int]] = {
      def combinationsIter(head: Int, tail: List[Int], acc: List[Int]): IndexedSeq[List[Int]] =
        if (tail.isEmpty) (0 to head).map(i => acc :+ i)
        else (0 to head).flatMap(i => combinationsIter(tail.head, tail.tail, acc :+ i))

      combinationsIter(list.head, list.tail, List())
    }

    val max_coins = coins.map(money / _)
    combinations(max_coins).filter(c => (c, coins).zipped.map(_*_).sum == money).size
  }

}