Scala Assignment: Recursion

gistfile1.scala

package recfun

import scala.collection.mutable.ListBuffer
import common._

/** https://class.coursera.org/progfun-2012-001/assignment/view?assignment_id=4 */
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: Pascal's Triangle
   */
  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: Parentheses Balancing
   */
  def balance(chars: List[Char]): Boolean = {
    def f(chars: List[Char], numOpens: Int): Boolean = {
      if (chars.isEmpty) {
        numOpens == 0
      } else {
        val h = chars.head
        val n =
          if (h == '(') numOpens + 1
          else if (h == ')') numOpens - 1
          else numOpens
        if (n >= 0) f(chars.tail, n)
        else false
      }
    }

    f(chars, 0)
  }

  /**
   * Exercise 3: Counting Change
   * Write a recursive function that counts how many different ways you can make
   * change for an amount, given a list of coin denominations. For example,
   * there are 3 ways to give change for 4 if you have coins with denomiation
   * 1 and 2: 1+1+1+1, 1+1+2, 2+2.
   */
  def countChange(money: Int, coins: List[Int]): Int = {
    def f(lastMaxCoin_total_coll: List[(Int, Int)], count: Int): Int = {
      if (lastMaxCoin_total_coll.isEmpty) {
        count
      } else {
        val b = ListBuffer[(Int, Int)]()
        var newCount = count
        for ((lastMaxCoin, total) <- lastMaxCoin_total_coll) {
          if (total < money) {
            for (c <- coins) {
              if (c >= lastMaxCoin) {
                val e = (c, total + c)
                b += e
              }
            }
          } else if (total == money) {
            newCount += 1
          }
        }

        f(b.toList, newCount)
      }
    }

    val b = coins.map { c => (c, c) }
    f(b, 0)
  }
}

@jeffreyyun's solutions above are the best. But here are mine.

  def pascal(c: Int, r: Int): Int = {
    if (r < 0 || c < 0 || c > r) 0
    else if (c == 0 || c == r) 1
    else pascal(c - 1, r - 1) + pascal(c, r - 1)
  }

  def balance(chars: List[Char]): Boolean = {
    val OPEN = '('
    val CLOSE = ')'
    def balanceRec(chars: List[Char], numOpen: Int): Boolean = {
      (chars) match {
        case (Nil) => numOpen == 0
        case (c :: tail) =>
          if (numOpen < 0) false
          else if (c == OPEN) balanceRec(tail, numOpen + 1)
          else if (c == CLOSE) balanceRec(tail, numOpen - 1)
          else balanceRec(tail, numOpen)
      }
    }
    balanceRec(chars, 0)
  }

  def countChange(money: Int, coins: List[Int]): Int = {
    (coins) match {
      case (Nil) => 0
      case (c :: tail) =>
        if (money < 0) 0
        else if (money == 0) 1
        else countChange(money - c, coins) + countChange(money, tail)
    }
  }

def balance(chars: List[Char]): Boolean = {
  def balanced(chars: List[Char], open: Int): Boolean = {
    if (open < 0) false else
    chars match {
      case Nil => open == 0
      case _ => {
      chars.head match {
        case '(' => balanced(chars.tail, open + 1)
        case ')' => balanced(chars.tail, open - 1)
        case _ => balanced(chars.tail, open)
       }
     }
   }
 }

  balanced(chars, 0)
}

def balance(chars: List[Char]): Boolean = {
  def balanced(chars: List[Char], open: Int): Boolean = {
    if (open < 0) false else
    chars match {
      case Nil => open == 0
      case _ => {
      chars.head match {
        case '(' => balanced(chars.tail, open + 1)
        case ')' => balanced(chars.tail, open - 1)
        case _ => balanced(chars.tail, open)
       }
     }
   }
 }

  balanced(chars, 0)
}

Hi, I have a much more simplified version of the balance code:

def balance(chars : List[Char]) : Boolean = {
val equal : Int = 0
@tailrec
def equality (chars : List[Char], equal : Int) : Boolean = {
if (chars.isEmpty) equal == 0 else {
chars.head match{
case '(' => equality(chars.tail, equal + 1)
case ')' => equality(chars.tail, equal - 1)
case _ => equality(chars.tail, equal)
}
}
}
equality(chars, 0)
}

:) The answer is really not smart. Code just like in C but not functional language. Use recursive function.

Indeed... the change function, I'm sure works but it uses two if not three, more advanced elements not lectured in the course yet... that's not the point.
maps,
for
and listbuffer