package recfun

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 - 1, r - 1) + pascal(c, r - 1)
  }

  /**
    * Exercise 2
    */
  def balance(chars: List[Char]): Boolean = {
    def balanceRec(chars: List[Char], balance: Int): Int= {
      if (balance < 0 || chars.isEmpty) return balance
      val head = chars.head
      if (head.equals('(')) balanceRec(chars.drop(1), balance + 1)
      else if (head.equals(')')) balanceRec(chars.drop(1), balance - 1)
      else balanceRec(chars.drop(1), balance)
    }

    balanceRec(chars, 0) == 0
  }

  /**
    * Exercise 3
    */
  def countChange(money: Int, coins: List[Int]): Int = {
    if (money == 0) return 0
    if (coins.isEmpty) return 0

    def maxPossibleFactorExists(n: Int): Boolean = {
      coins.exists(x => x <= money)
    }

    def maxPossibleFactor(n: Int): Int = {
      coins.filter(x => x <= money).max
    }

    if (!maxPossibleFactorExists(money)) return 0

    val max = maxPossibleFactor(money)
    if (max == money) 1 + countChange(money - max, coins)
    else 1 + countChange(max, coins) + countChange(money - max, coins)
  }
}