Learning Scala - Solution to the 1st week assignment

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: standard recursive version of the Pascal's Triangle
    *
    * pascal(0, r) = 1  // edge
    * pascal(c, c) = 1  // edge
    * pascal(c, r) = pascal(c-1, r-1) + pascal(c, r-1)  // recursion
    *
    * @param c the column index
    * @param r the row index
    * @return the value of the element at row r and column c in the Pascal's Triangle
    */
  def pascal(c: Int, r: Int): Int =

    if (c > r) -1
    else if (c == 0 || c == r) 1
    else pascal(c-1, r-1) + pascal(c, r-1)

  /**
    * Excercise 2: tail recursive version of the parenthesis balance problem
    *
    * @param chars the list of input characters
    * @return true if the input string is balanced, false otherwise
    */
  def balance(chars: List[Char]): Boolean = {

    @tailrec
    def balanceAcc(acc: Int, chars: List[Char]): Boolean = {
      if (chars.isEmpty) acc == 0
      else
        if (chars.head == '(') balanceAcc(acc + 1, chars.tail)
        else if (chars.head == ')') acc > 0 && balanceAcc(acc - 1, chars.tail)
        else balanceAcc(acc, chars.tail)
    }

    balanceAcc(0, chars)
  }


  /**
    * Exercise 3: a standard recursive version of the change problem
    *
    *
    * @param money the change
    * @param coins the available coins for the change
    * @return
    */
  def countChange(money: Int, coins: List[Int]): Int = {

    def count(m: Int, c: List[Int]) : Int = {
      if (c.isEmpty || m - c.head < 0) 0
      else if (m - c.head == 0) 1
      else count(m - c.head, c) + count(m, c.tail)
    }
    count(money, coins.sorted)
  }

}

Another way to write the for comprehension (both ways are fine)

for {
row <- 0 to 10
col <- 0 to row
} yield {
  print(pascal(col, row) + " ")
  if(col == row) println()
}

Minor styling issue, better always wrap function body with {}

Not sure if you already saw pattern matching but you can rewrite balanceAcc with:

def balanceAcc(acc: Int, chars: List[Char]): Boolean = chars match {
  case Nil => acc == 0
  case '(' :: tail => balanceAcc(acc + 1, tail)
  case ')' :: tail => acc > 0 && balanceAcc(acc - 1, tail)
  case _ :: tail => balanceAcc(acc, tail)
}

Also count:

def count(m: Int, c: List[Int]) : Int = c match {
  case Nil => 0
  case h :: _ if m - h < 0 => 0
  case h :: _ if m - h == 0 => 1
  case h :: t => count(m - h, c) + count(m, t)
}

cool, congrats, you write quite clean Scala code already! 👍