-
-
Save ngocdaothanh/3764694 to your computer and use it in GitHub Desktop.
| 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) | |
| } | |
| } |
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)
}
}
}
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)
}
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 _))
}
- 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)
}
`
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)
}
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)
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)
}
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)
}
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
Can you give solution#3 on erlang please? can anyone?
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)
}
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)
}
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)
}
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)
}
}
this is a function program!!!
so
def balance(chars: List[Char]): Boolean = chars.filter(_ == '(').length == chars.filter(_ == ')').length
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}
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])Booleanor 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
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
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
}
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)
}
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)
}
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?
@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).
@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
@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)
}
}