1
votes

To practice Scala I wanted do solve simple dynamic programming exercises with Scala. For some exercises I already wrote a Python implementation. Using Python most of the time I saved the intermediate results in an array.

For example this Exercise:

The algorithm outputs the minimal amount of coins needed to reach a value, given the value and a list of coins. (Assuming there is an unlimited amount of coins.)

def automat(n, coins = [1,2,5,10,20,50,100,200]):
    A = [0]
    for i in range(1, n + 1):
        smallest_change = min([A[i - coin] for coin in coins if 0 <= i - coin])
        A.append(smallest_change + 1)
    return A[n]

Looks very simple in Python. Nevertheless I have problems writing the same code in Scala. Because of the functional paradigm I did not want to use a for-loop, but rather a tail-recursive algorithm to solve that problem. And I couldn't find any good solution. Maybe a tail-recursive algorithm is not the right way to go and there is a different scala-way to implement this simple algorithm.

I already looked for scala implementation of dynamic programming exercises and couldn't find a good source yet. Has someone an idea what the scala way to implement this would look like?

UPDATE:

The closest I came so far is very similar to Dimas tail-recursive approach. It looks like this

def automat(n: Int, coins: List[Int] = List(1, 2, 5, 10, 20, 50, 100, 200)): Int = {
    inner(n, n + 1, coins, List(0)).last
}

def inner(n: Int, m: Int, coins: List[Int], result: List[Int]): List[Int] = n match {
    case 0 => result
    case _ => inner(n-1, m, coins, result ::: List(coins.collect { case coin if (0 <= m - n - coin) => result(m - n - coin) }.min + 1))
}
3

3 Answers

2
votes

You can do something like that :

 def automat(n: Int, coins: List[Int]): Int = (n, coins) match {
         case (0, _) => 1
         case (m, _) if m < 0 => 0
         case (_, cs)  if cs.isEmpty => 0
         case (m, cs) => automat(m - cs.head, cs) + automat(m, cs.tail) 
    }

If you are interested in Scala, the Coursera class of Martin Odersky is a good starting point.

0
votes

This is a more or less literal translation of your algorithm into idiomatic scala. The common idea in implementations like this is to replace loops updating mutable state sequentially with recursion, that passes state updates down as function arguments, and up as return values:

   def automat(n: Int, coins: Seq[Int] = Seq(1,2,5,10,20,50,100,200)): Array[Int] = n match {
     case 0 => Array(0)
     case n => 
       val out = automat(n-1, coins)
       val num = coins
         .collect { case coin if coin <= n  =>  out(n - coin) } 
         .min + 1
       out :+ num
   }

A better approach is to reverse the direction of the recursion, so that the algorithm can be implemented as a tail-recursive function, that removes the possibility of stack overflow with very large n:

  @tailrec
  def automat2(
    max: Int, 
    coins: Seq[Int] = Seq(1,2,5,10,20,50,100,200), 
    n: Int = 1, 
    out: Array[Int] = Array(0)
  ): Array[Int] = n match {
    case n if n > max => out
    case n => 
      val num = coins
        .collect { case coin if coin <= n  =>  out(n - coin) } 
        .min + 1
      automat2(max, coins, n+1, out :+ num)
  }

Of course, if you didn't want to stick to the particular algorithm you have been using, and were willing instead to settle on another approach, you could then have a much simpler solution like this:

@tailrec
def automat3(n: Int, coins: List[Int] = List(200, 100, 50, 20, 10, 5, 2, 1), result: Int = 0): Int = (n, coins) match { 
   case (0, _) => result
   case (n, Nil) => 0
   case (n, head::tail) if head > n => automat3(n, tail, result)
   case (n, head::_) => automat3(n - head, coins, result+1)
}  
0
votes

Here is one version that I remember doing for one of the Scala couse

def minCoins(amount: Int, coins: Seq[Int]): Int =
  if (amount < 0) 0
  else if (coins.isEmpty) if (amount == 0) 1 else 0
  else
    minCoins(amount, coins.tail) + minCoins(amount - coins.head, coins)

So what you basically do is to have some combinations first by subtracting the amount from the Set of given coins and concatenating the combinations of the rest of the coins in the Set of given coins.