Skip to content

Instantly share code, notes, and snippets.

@ngocdaothanh
Created September 22, 2012 00:43
Show Gist options
  • Star 65 You must be signed in to star a gist
  • Fork 16 You must be signed in to fork a gist
  • Save ngocdaothanh/3764694 to your computer and use it in GitHub Desktop.
Save ngocdaothanh/3764694 to your computer and use it in GitHub Desktop.
Scala Assignment: Recursion
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)
}
}
@said026
Copy link

said026 commented Mar 2, 2017

For the second exercise 👍

 def balance(chars: List[Char]): Boolean = {

      // Checks if there is a closing parentheses, and the count is still positive
      def isBalanced(chain: List[Char], remaining_parenthesis:Int) : Boolean = {
        if (chain.isEmpty)
          true
        else if (chain.head == '(') {
          val chain_tail =chain.tail
          remaining_parenthesis > 0 && chain_tail.count(_ == ')') > 0 &&
            isBalanced(chain_tail, remaining_parenthesis - 1)
        }
        else
          isBalanced(chain.tail, remaining_parenthesis)
      }

      val opening_parentheses_number = chars.count(_ == '(')
      val closing_parentheses_number = chars.count(_ == ')')

      if (opening_parentheses_number!=  closing_parentheses_number)
        false
      else
        isBalanced(chars, closing_parentheses_number)
}

@horatiuj-telenav
Copy link

3rd exercise

class CurrencyCalculator extends ((Int, List[Int]) => Int) {
  override def apply(money: Int, coins: List[Int]): Int = {
    val sortedCoins = coins.sorted.reverse
    getPossibilities(money, sortedCoins)
  }

  private def getPossibilities(money: Int, coins: List[Int]): Int = {
    if (coins.isEmpty) return 0
    val largestCoin = coins.head
    val nbOfLargestCoins = money / largestCoin
    (if (money % largestCoin == 0) 1 else 0) + nbOfLargestCoins * getPossibilities(largestCoin, coins.tail)
  }
}

@zty8023ys
Copy link

zty8023ys commented Jul 3, 2017

this is a function program!!!
so
def balance(chars: List[Char]): Boolean = chars.filter(_ == '(').length == chars.filter(_ == ')').length

@deekshaaneja
Copy link

BalanceParenthesis using stack

def balance(chars: List[Char]): Boolean = {if (pfunc(chars)==0) return true else (return false)}

def pfunc(chars: List[Char]): Int ={
var st = mutable.StackChar
if(!chars.contains('(')) return 1
for (char <-chars) {
if (char == '(') st.push(char)
else if (char == ')' && !st.isEmpty)
{if ( st.top=='(') st.pop()}
//System.out.println(st.toString(),st.size)
};return st.size}

@valtih1978
Copy link

valtih1978 commented Jul 13, 2017

Balance using fold where int accumulator counts the balance between ( and ) and bool accumulator is used for breaking out of the fold, (https://stackoverflow.com/questions/12892701/abort-early-in-a-fold uses opt for that)

  def balance2(chars: Iterable[Char]): Boolean = {
  	val (bool, int) = chars.foldLeft(true -> 0){
  		case ((bool, int), char) => char match {
  			case '(' => bool -> (int + 1)
  			case ')' => (bool && int != 0) -> (int - 1)
  			case _ => bool -> int
  		}
  	}; bool && (int == 0)
  }                                               //> balance2: (chars: Array[Char])Boolean

or even use return to break out of the fold

  def balance22(chars: Iterable[Char]): Boolean = {
  	chars.foldLeft(0){
  		case (acc, char) => char match {
  			case '(' => acc + 1
  			case ')' => if (acc == 0) return false
  				acc - 1
  			case _ => acc
  		}
  	} == 0
  }                                               //> balance22: (chars: Array[Char])Boolean

  balance22("")                                   //> res11: Boolean = true
  balance22("123")                                //> res12: Boolean = true
  balance22("(df())")                             //> res13: Boolean = true
  balance22("())(")                               //> res14: Boolean = false
  balance22("(((")                                //> res15: Boolean = false

@valtih1978
Copy link

valtih1978 commented Jul 13, 2017

Based on https://github.com/hsleep/Coursera/blob/master/parprog1/reductions/src/main/scala/reductions/ParallelParenthesesBalancing.scala

  def balance(chars: Iterable[Char]): Boolean = {
    val code = Map('(' -> 1, ')' -> -1).withDefaultValue(0)

    def loop(chLs: List[Char], acc: Int = 0): Int = chLs match {
      case head::tail if acc >= 0 => loop(tail, acc + code(head))
      case _ => acc
    }
    loop(chars.toList) == 0
  }                                               //> balance3: (chars: Array[Char])Boolean

@saleem-mirza
Copy link

saleem-mirza commented Sep 19, 2017

I'm still trying to grasp functional programming concepts and honestly struggling with it. However, I came up with an imperative solution.

  def balance(chars: List[Char]): Boolean = {
    val stack = new mutable.Stack[Char]()
    for (c <- chars) {
      if (c == '(')
        stack.push(c)
      else {
        if (c == ')') {
          if (stack.nonEmpty) {
            stack.pop()
          } else {
            return false
          }
        }
      }
    }
    if (stack.isEmpty) {
      true
    } else
      false
  }

@jeffreyyun
Copy link

jeffreyyun commented Dec 28, 2017

My solutions for Exercises 1, 2, and 3:

  def pascal(c: Int, r: Int): Int = {
    if (c == 0 || c == r) 1 else pascal(c - 1, r - 1) + pascal(c, r - 1)
  }
  def balance(chars: List[Char]): Boolean = {
    def balanced(chars: List[Char], count: Int): Boolean =
      if (chars.isEmpty) count == 0
      else if (count < 0) false
      else if (chars.head == '(') balanced(chars.tail, count + 1)
      else if (chars.head == ')') balanced(chars.tail, count - 1)
      else balanced(chars.tail, count)

    balanced(chars, 0)
  }
  def countChange(money: Int, coins: List[Int]): Int = {
    if (money == 0) 1
    else if (money < 0) 0
    else if (coins.isEmpty) 0
    else countChange(money - coins.head, coins) + countChange(money, coins.tail)
  }

@taverasmisael
Copy link

I tweeked @vigneshwaranr's solution switching the if/elses to a match. Is the same implementation, don't know if better or not, judge yourself:

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

  balanced(chars, 0)
}

@PyAntony
Copy link

Can anybody please explain how in earth do you get solution for number 1 in just 2 lines of code? I mean, not how it works but how do you notice the pattern in the first place!??? I have a working solution but it takes 10 lines of code. I would have never notice for the life of me that it was that simple. Or is everybody just copying/pasting from the internet?

@BarthesSimpson
Copy link

BarthesSimpson commented Jan 9, 2019

@PyAntony it helps to break recursive problems down into a base case and a recursive step. If you find yourself stuck, try figuring out your base case(s) first: the simplest possible input (often 0 or 1) where you can just return a value. Then for the recursive step figure out how you'd get from that to the next case. The base case is usually just a statement (or a couple of statements) and the recursive step is then a (tail) recursive function call.

So in the pascal case, the base case is that you are in the first column or the last column, in which case return 1. (I actually prefer to add another base case of an illegal input where c < 0, r < 0 or c > r, in which case I return 0). Then the recursive step is that assuming you already have everything computed up to the current step, you can get the correct value by adding the adjacent values from the row above, i.e. pascal(c-1, r-1) and pascal(c-1, r).

@BarthesSimpson
Copy link

BarthesSimpson commented Jan 9, 2019

@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)
    }
  }

@nachteulen
Copy link

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)
}

@Knk00
Copy link

Knk00 commented Jan 29, 2020

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)
}

@dandosi
Copy link

dandosi commented Jul 26, 2021

:) 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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment