FPP in Scala week1

recfun.scala

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

  }
  /**
  def pascal_(c: Int, r: Int): Int = {
    (c,r) match {
      case _ if c > r  => throw new IllegalArgumentException
      case _ if c < 0 || r < 0 => throw new IllegalArgumentException
      case _ if c == 0 || r == 0 => 1
      case _ if c == r => 1
      case _           => pascal(c-1, r-1) + pascal(c, r-1)
    }
  }
  */

  /**
   * Exercise 2
   */
  def balance(chars: List[Char]): Boolean = {
    @tailrec
    def matchP(xs: List[Char], stack: List[Char]): Boolean = {
      xs match {
        case _       if xs.isEmpty => stack.isEmpty
        case x :: xs if x == '('   => matchP(xs, x :: stack)
        case x :: xs if x == ')'   => if (stack.isEmpty) false else matchP(xs, stack.tail)
        case x :: xs               => matchP(xs, stack)
      }
    }

    matchP(chars, List[Char]())

  }

  /**
  def balance(chars: List[Char]): Boolean = {
    chars.foldLeft(0) {
      case (0, ')') => return false
      case (x, ')') => x - 1
      case (x, '(') => x + 1
      case (x, _) => x
    } == 0
  }
  */


  /**
   * Exercise 3
   */
  def countChange(money: Int, coins: List[Int]): Int = {
    (money, coins) match {
      case _ if money == 0 => 1
      case _ if money < 0  => 0
      case _ if coins.isEmpty => 0
      case _ => countChange(money, coins.tail) + countChange(money - coins.head, coins)
    }
  }
  /**
  def countChange(money: Int, coins: List[Int]): Int = {
    def mapcons(coins: List[Int], alt: Alt): List[Alt] = {
      coins map (x => Alt(alt.remain - x, x :: alt.alt))
    }
    def makeTree(coins: List[Int], alts: List[Alt]) : List[Alt] = {
      val wholeTree: List[List[Alt]] = alts map (alt => {
        val filtered = coins filter (x => x <= alt.remain)
        if (filtered.isEmpty)
          List[Alt](alt)
        else {
          makeTree(coins, mapcons(filtered, alt))
        }
      })
      wholeTree.flatten
    }

    val list: List[Alt] = makeTree(coins, List(Alt(money, List[Int]())))
    val possible = list filter (x => x.remain == 0)
    return possible.length : Int

  }
  */

}