Skip to content

Instantly share code, notes, and snippets.

@jasonicarter

jasonicarter/README.md

Last active November 19, 2022 16:54
Show Gist options
  • Save jasonicarter/63ddf092750c9493dfc546f151e14189 to your computer and use it in GitHub Desktop.
Save jasonicarter/63ddf092750c9493dfc546f151e14189 to your computer and use it in GitHub Desktop.
Download ZIP
Counting change recursive algorithm in Scala
Raw
README.md

Scala

Just a few interesting pieces of Scala code

Raw
bracketBalance.scala
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)
}
Raw
countingChange.scala
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)
}
Raw
sumListOfInts.scala
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)
}
@badbye
Copy link

badbye commented Nov 19, 2022

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