ngocdaothanh/gist:3764694

gsriram7 · 2015-05-18T07:08:33Z

Here is my solution for exercise #2 using recursion and pattern matching..

def parenthesis(input: List[Char], count: Int):Boolean ={
input match {
case Nil if count==0 => true
case Nil if count!=0 => false
case head :: tail if count==(-1) => false
case head :: tail if head == '('=> parenthesis(tail, count + 1)
case head :: tail if head == ')'=> parenthesis(tail, count - 1)
case head :: tail if head!='(' && head!=')' => parenthesis(tail, count)
}
}

azazi-sa · 2015-06-02T12:49:50Z

How about a tail recursive function?

  /**
   * Exercise 2
   */
  @tailrec
  def balance(chars: List[Char], buffer: Int = 0): Boolean = {

    if (chars.isEmpty || buffer < 0)
      buffer == 0
    else if (chars.head == '(')
      balance(chars.tail, buffer + 1)
    else if (chars.head == ')')
      balance(chars.tail, buffer - 1)
    else
      balance(chars.tail, buffer)
  }

ganger85 · 2015-06-02T15:38:50Z

@tailrec
def balance(chars: List[Char], opens: Int = 0): Boolean = {
if (opens < 0) return false
if (chars.length == 0) return opens == 0
chars.head match {
case '(' => balance(chars.tail, opens + 1)
case ')' => balance(chars.tail, opens - 1)
case _ => balance(chars.tail, opens)
}
}

maximilianmordig · 2015-07-03T17:00:03Z

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

rimeh-bennjima · 2015-09-17T16:07:53Z

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

val queue= new mutable.Queue[Char]()

def test (chars : List[Char], q: Queue[Char]): Boolean =
{
  chars match {
    case Nil => q.isEmpty
    case '(':: tail => q += '('; test(chars.tail,q)
    case ')':: tail => if (q.isEmpty) false else {q.dequeue  ; test(chars.tail,q)}
    case x::tail => test(chars.tail,q)
  }
}
test(chars,queue)

}

danielOKeefe · 2015-09-20T02:23:48Z

another recursive option

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

//true for paren false for other chars
def isParen(aChar : Char) : Boolean = {
  if (aChar == '(' || aChar == ')')
    true
  else
    false
}

def subBalanced(chars: List[Char]) : Boolean = {
  //if we have an empty list we're technically balanced
  if (chars.isEmpty) true
  //if an open paren is at the beginning we aren't balanced
  else if (chars.head == ')') false
  //if we have two of the same type of parentheses we aren't balanced
  else if (chars.head == chars.last)
    false
  else subBalanced(chars.drop(1).dropRight(1))
}

//runs recursive function on filtered list
subBalanced(chars.filter(isParen _))

}

rohinp · 2016-04-20T10:13:34Z

Exercise 1

`

def pascal(c: Int, r: Int): Int = {

def fact(n:Int):Int =

    if(n == 0) 1

    else n * fact(n - 1)

fact(r) / fact(r-c)

}

`

haritos30 · 2016-06-09T15:02:36Z

My solution for Exercise 2:

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

      def internalCount(chars: List[Char], balance: Int,  needsClosing: Boolean): Boolean = {

      // operation has finished
      if (chars.isEmpty && balance == 0 && needsClosing == false)
        true
      else if(chars.isEmpty)
        false

      else if (chars.head == '(') 
        internalCount(chars.tail, balance+1, true)
      else if (chars.head == ')') 
        internalCount(chars.tail, balance-1, false)
      else 
        internalCount(chars.tail, balance, needsClosing)
    }

    return internalCount(chars, 0, false)
  }

SangeetaGulia · 2016-06-14T12:29:22Z

def factorial(num: Long): Long = {
if(num==0) 1
else num*factorial(num-1)
}

def computation(n: Long, r: Long): Double = {
factorial(n)/ (factorial(r) * factorial(n-r))
}

def pascalTriangle(level: Int)={
for(i <- 0 to level) {
for(j <- 0 to i){
print(computation(i,j) + " ")
}
println("")
}
}

pascalTriangle(5)

mamalisk · 2016-08-09T14:08:34Z

Another solution for the balance could be:

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

   val onlyBrackets = chars.filter(c => '('.equals(c) || ')'.equals(c))

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

  onlyBrackets.size % 2 == 0 && isBalanced(0,onlyBrackets)
 }

akshaygunner · 2016-10-15T05:14:06Z

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

wzieba · 2016-11-27T23:53:40Z

If you want to deeply understand algorithm of the third task (without breaking coursera's honor code) I recommend you post on my blog. I provided text and visual explanation with help of mitpress (thank you @thegovyadina for link!)

https://wzieba.github.io/programming/2016/11/25/count-change-algorithm.html

tuafeeqahmed · 2016-12-30T09:21:50Z

Can you give solution#3 on erlang please? can anyone?

ivportilla · 2017-01-22T02:33:23Z

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

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

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

  iterate(chars, 0)
}

dev3loperb · 2017-02-28T06:06:20Z

exercise 3

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

said026 · 2017-03-02T15:25:31Z

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 · 2017-04-07T09:17:29Z

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 · 2017-07-03T12:06:09Z

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

deekshaaneja · 2017-07-07T21:47:12Z

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 · 2017-07-13T10:25:01Z

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 · 2017-07-13T11:07:05Z

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 · 2017-09-19T01:20:01Z

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
  }

alexcyun · 2017-12-28T23:42:35Z

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 · 2018-10-14T03:05:22Z

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 · 2018-12-25T09:54:03Z

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 · 2019-01-09T05:16:10Z

@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 · 2019-01-09T05:21:29Z

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

dieNachteule · 2019-03-09T12:41:04Z

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 · 2020-01-29T15:01:14Z

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 · 2021-07-26T19:12:28Z

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

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

ngocdaothanh/gist:3764694

gsriram7 commented May 18, 2015

Uh oh!

azazi-sa commented Jun 2, 2015

Uh oh!

ganger85 commented Jun 2, 2015

Uh oh!

maximilianmordig commented Jul 3, 2015

Uh oh!

rimeh-bennjima commented Sep 17, 2015

Uh oh!

danielOKeefe commented Sep 20, 2015

Uh oh!

rohinp commented Apr 20, 2016

Uh oh!

haritos30 commented Jun 9, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

SangeetaGulia commented Jun 14, 2016

Uh oh!

mamalisk commented Aug 9, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

akshaygunner commented Oct 15, 2016

Uh oh!

wzieba commented Nov 27, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tuafeeqahmed commented Dec 30, 2016

Uh oh!

ivportilla commented Jan 22, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dev3loperb commented Feb 28, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

said026 commented Mar 2, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

horatiuj-telenav commented Apr 7, 2017

Uh oh!

zty8023ys commented Jul 3, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

deekshaaneja commented Jul 7, 2017

Uh oh!

valtih1978 commented Jul 13, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

valtih1978 commented Jul 13, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

saleem-mirza commented Sep 19, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

alexcyun commented Dec 28, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

taverasmisael commented Oct 14, 2018

Uh oh!

PyAntony commented Dec 25, 2018

Uh oh!

BarthesSimpson commented Jan 9, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

BarthesSimpson commented Jan 9, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dieNachteule commented Mar 9, 2019

Uh oh!

Knk00 commented Jan 29, 2020

Uh oh!

dandosi commented Jul 26, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

haritos30 commented Jun 9, 2016 •

edited

Loading

mamalisk commented Aug 9, 2016 •

edited

Loading

wzieba commented Nov 27, 2016 •

edited

Loading

ivportilla commented Jan 22, 2017 •

edited

Loading

dev3loperb commented Feb 28, 2017 •

edited

Loading

said026 commented Mar 2, 2017 •

edited

Loading

zty8023ys commented Jul 3, 2017 •

edited

Loading

valtih1978 commented Jul 13, 2017 •

edited

Loading

valtih1978 commented Jul 13, 2017 •

edited

Loading

saleem-mirza commented Sep 19, 2017 •

edited

Loading

alexcyun commented Dec 28, 2017 •

edited

Loading

BarthesSimpson commented Jan 9, 2019 •

edited

Loading

BarthesSimpson commented Jan 9, 2019 •

edited

Loading

dandosi commented Jul 26, 2021 •

edited

Loading