Just a few interesting pieces of Scala code
Last active
November 19, 2022 16:54
-
-
Save jasonicarter/63ddf092750c9493dfc546f151e14189 to your computer and use it in GitHub Desktop.
Counting change recursive algorithm in Scala
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def balance(chars: List[Char]): Boolean = { | |
| def loop(chars: List[Char], stack: Int): Boolean = { | |
| if (chars.isEmpty) stack == 0 // '(' and ')' should result in 0 if balanced | |
| else if (chars.head == '(') loop(chars.tail, stack + 1) | |
| else if (chars.head == ')') loop(chars.tail, stack - 1) | |
| else loop(chars.tail, stack) | |
| } | |
| if (chars.isEmpty) true // if empty, debatable as balanced | |
| else if (chars.head == chars.last) false // if head and last are equal brackets not balanced | |
| else loop(chars, 0) | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def countChange(money: Int, coins: List[Int]): Int = { | |
| def loop(money: Int, coins: List[Int]): Int = { | |
| if (money < 0 || coins.isEmpty ) 0 | |
| else if (money == 0 ) 1 | |
| else loop(money, coins.tail) + loop(money - coins.head, coins) | |
| } | |
| loop(money, coins) | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def sum(xs: List[Int]): Int = { | |
| def loop(xs: List[Int], prevHead: Int): Int = { | |
| if (xs.isEmpty) 0 | |
| else if (xs.tail.isEmpty) xs.head+prevHead | |
| else loop(xs.tail, xs.head+prevHead) | |
| } | |
| loop(xs, 0) | |
| } |
Do you need the nested 'loop' function in counitngChange? Can't it be written with recursion onto itself (countingChange) instead?
BrackeBalance - else if (chars.head == chars.last) false
What about balance("a()a".toList)
?
I was thinking maybe
" if(chars.isEmpty || x < 0) x ==0"
In the sum function, this part is useless:
else if (xs.tail.isEmpty) xs.head+prevHead
If you replace this part:
if (xs.isEmpty) 0
By this part:
if (xs.isEmpty) prevHead
So the final source code will be:
def sum(xs: List[Int]): Int = {
def loop(xs: List[Int], prevHead: Int): Int = {
if (xs.isEmpty) prevHead
else loop(xs.tail, xs.head + prevHead)
}
loop(xs, 0)
}
def parenthesesBalancing(chars: List[Char]): Boolean = {
@tailrec
def parentheses(chars: List[Char], counter: Int): Int = {
if (chars.isEmpty || counter < 0) counter
else {
if (chars.head == '(') parentheses(chars.tail, counter + 1)
else if (chars.head == ')') parentheses(chars.tail, counter - 1)
else parentheses(chars.tail, counter)
}
}
parentheses(chars, 0) == 0
}
def sumOfInt(numbers: List[Int]): Int = {
@tailrec
def loop(numbers: List[Int], acc: Int): Int = {
if (numbers.isEmpty) acc
else loop(numbers.tail, acc + numbers.head)
}
loop(numbers, 0)
}
can you please explain how in earth do you figure out stuff like this?
def countChange(money: Int, coins: List[Int]): Int = {
def loop(money: Int, coins: List[Int]): Int = {
if (money < 0 || coins.isEmpty ) 0
else if (money == 0 ) 1
else loop(money, coins.tail) + loop(money - coins.head, coins)
}
loop(money, coins)
}
I have a working function but it's about 14 lines of code.
A bit late to the party, but think of it like this:
- if we have to create a negative amount of money or we do not have any coins at all but have to create a positive amount of money (this check is missing afaik), there are exactly 0 possibilities (trivial case)
- if we have to create 0, there is exactly 1 possibility (we use no coins)
- else pick a random coin from coins (in this case via coins.head); now there are two possibilities:
- either we use that coin, then we can deduct its amount and continue with the same coins-list (since we can still use the same coin again)
-> loop(money - coins.head, coins) - or we do not use that coin (coins.head) at all. Then we can continue our calculation without that coin. Note that coins.tail equals coins without coins.head
-> loop(money, coins.tail)
Since in each case we are either deducting from either money or coins, the program is sure to finish.
- either we use that coin, then we can deduct its amount and continue with the same coins-list (since we can still use the same coin again)
Tricky, but very fun question. :)
Could someone explain to me the intuition behind countChange function? I don't understand it!
@dksifoua :
"Could someone explain to me the intuition behind countChange function? I don't understand it!"
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 denomination 1 and 2: 1+1+1+1, 1+1+2, 2+2.
balance("())(()") returns true, which is not correct.
Here is my solution:
def balance(chars: List[Char]): Boolean =
def _balance(value: List[Char], count: Int): Boolean =
if count < 0 then false
else if value.isEmpty then count == 0
else if value.head == ')' then _balance(value.tail, count - 1)
else if value.head == '(' then _balance(value.tail, count + 1)
else _balance(value.tail, count)
_balance(chars, 0)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thank you, i have no idea so far until saw this gist :)