sca

gistfile1.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 =
    if (exceedsBounds(r, c)) 0
    else if (plotsAtEitherEnds(r, c)) 1
    else pascal(c - 1, r - 1) + pascal(c, r-1)  //> pascal: (r: Int, c: Int)Int

  def plotsAtEitherEnds(r: Int, c: Int): Boolean = c == 0 || r == c
                                                  //> plotsAtEitherEnds: (r: Int, c: Int)Boolean
  def exceedsBounds(r: Int, c: Int): Boolean = c > r
  /**
   * Exercise 2
   */
  def balance(chars: List[Char]): Boolean = {
	def balanceCore(chars: List[Char], stack: List[Char]): Boolean =
		if (chars.isEmpty && stack.isEmpty) true
		else if (chars.isEmpty && !stack.isEmpty) false
		else if (chars.head == '(') balanceCore(chars.tail, ('(' :: stack))
		else if (chars.head == ')') !stack.isEmpty && balanceCore(chars.tail, stack.tail)
		else balanceCore(chars.tail,stack)
	balanceCore(chars,"".toList)
  }
  /**
   * Exercise 3
   */
    def countChange(amount: Int, coins: List[Int]): Int = {
    if (amount <= 0) 0
    if (coins == null || coins.length == 0) 0

    val dp: Array[Int] = Array.fill(amount + 1) { 0 }
    dp(0) = 1

    for (i <- 0 to coins.length - 1) {
      for (j <- coins(i) to amount) {
        dp(j) += dp(j - coins(i))
      }
    }
    dp(amount)
  }                                               //> countChange: (amount: Int, coins: List[Int])Int
}