Coins in Scala

In this article I’m gonna present my Scala solution for 2 quite popular coin related problems (ask Google for curiosity about these problems and you will see tones of answers). The full code implementation with tests attached can be found here: (https://github.com/mdfecioru/algos/tree/master/coins_scala)

So, what are the problems? Two of them (for now):

  • Giving a set of coin types (e.g. 1, 5, 10, 25 cents) in how many ways you can give a certain amount of money (e.g. 37 cents)?
  • Giving a set of coin types what is the minimum number of coins you can use to give a certain amount of money?

Problem 1: Total number of coins combination to give an amount of money
So, let’s see what we are really asked here: we need to generate a simple count of combinations and not all the combinations. Thus, we could say that the problem is a little bit simplified for us. The solution in Scala is as follows:

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

  if (money == 0) 0
  else countChangeInner(money, coins)
}

As you can see, the solution is really straight-forward. First, we create an inner function in order to easily handle the case where provided amount of money is zero (0). Then the inner function’s job is to recursively generate new solutions. How to do that? Well… giving a list of coin types and an amount of money, there are 2 ways we can generate new solutions:

  • keep the coins list but reduce the amount of money: either we use the first coin in the list of coins and we continue the solution for the remaining amount o money (money – coins.head) using the same coins list
  • keep the money but reduce the coins list: we search solutions for the same amount of money but using a reduce list of coins list by removing the first coin type (coins.tail)

Recursivity ends in two cases:

  • either we have found a solution: we have reduced the amount of money by using our coins until we’ve reached with EXACTLY 0. In this case, we return 1, to increment the number of valid solutions.
    • NOTE: To differentiate between this happy case and receiving 0 from the beginning, we needed to define the countChangeInner function…
  • either we have found that the current option will not lead to a valid solution: this is identified by either reducing the coin type space (coins.isEmpty) or by finding out that we’ve ended-up dealing with a negative amount of money as a result of using a certain coin type. In this case, we return 0 to not modify the number of valid solutions.

Problem 2: Minimum number of coins to return a sum of money
So, this is a totally different problem compared with the first one: we are now asked to identify from the entire set of possible coins combinations that we can use in order to return a sum of money the minimum amount of coins we can use to return that sum. A recursive solution to this problem is presented below:

def minChangeRec(money: Int, coins: List[Int]): Int = {
  val cache = collection.mutable.Map[Int, Int]()
  val infinity: Integer = money + 1

  def minChangeRecInner(money: Int): Int = {
    if (coins.contains(money)) cache(money) = 1
    else if (cache.getOrElse(money, infinity) == infinity) {
      cache(money) = infinity
      for (c <- coins.filter(_ <= money))
          cache(money) = Math.min(1 + minChangeRecInner(money - c), cache(money))
      }
      cache(money)
    }

    minChangeRecInner(money)
    if (cache(money) == infinity) 0 else cache(money)
}

Even if the minChangeRecInner function seems a bit complex, the “magic” happens in the for loop which does the following:

  • for each coin (c) that we can use for the current sum (coins.filter(_ <= money)) we reduce the problem further on the recursivity path by saying that for a certain selected coin, the solution is 1 (the selected coin) plus the minimum set of coins we need to express the rest of the money (1 + minChangeRecInner(money – c)).
  • as the for loop will execute the work describe above, it will also store the minimum value produce by each coin in a local cache (cache(money))

What’s with the cache? Can we write the function without it? The answer, is yes, we could not use the cache but it is not recommended as the solution space generated by the recursivity will very quickly grow(see here a really good / complete explanation http://interactivepython.org/runestone/static/pythonds/Recursion/DynamicProgramming.html). The cache is used to store away the minimum coins used for a certain sum of money so that next time we need this information somewhere in the recursivity tree we can simply re-use it instead of re-executing a costly recursivity.

There is also an iterative solution to this issue that is implementing the Dynamic Programming way of problem solving: start with solving the problem for initial steps or smaller problem spaces and then us this information to slowly build-up the solution for the case you are interested in.

Translating the above statement for our problem: let’s find out the minimum amount of coins we can use to pay 0, 1, 2, 3 … and so on an us this information to slowly compute the minimum amount of coins needed to the amount of money we are interested in. The code for this solution is listed below:

def minChangeDP(money: Int, coins: List[Int]): Int = { 
  val minCoins = collection.mutable.ArrayBuffer[Int]() 
  val infinity: Integer = money + 1 

  for (m <- 0 to money) { 
    var coinCount: Int = m 
    if (m == 0) minCoins += 0 else minCoins += infinity 

    for (c <- coins.filter(_ <= m)) 
      if (minCoins(m - c) + 1 <= coinCount) { 
        coinCount = minCoins(m - c) + 1 
        minCoins(m) = coinCount 
      } 
    } 

  if (minCoins(money) == infinity) 0 else minCoins(money) 
}

As you can see, the approach here is that we start buy building solutions for our problem for all the values in the 0 to money interval. For each amount of money in this interval, we are trying to use the minimum solutions we have identified for sum of money less than the current value in order to compute the minimum for the current amount of money. How we do that? We look at each coin available and see if we use it together with the minimum we have computed for the amount of money less the selected coin value to get a better minimum number of coins for the current sum of money.

That’s what the “if (minCoins(m – c) + 1 <= coinCount)” line is doing: selecting the coin ‘c’ the rest of the money we need to may is ‘m-c’ and the minimum amount of coins to pay this amount is already computed: minCoins(m – c). Thus, if we select coin ‘c’ the minimum amount of coins will be 'minCoins(m – c) + 1’ to pay the amount of money ‘m’. We do this for all possible coins and compute the minimum between all these values – that’s going to be the actual minimum for the amount of money ‘m’. We save this and we go to the next step until we reach the ‘money’ value.

Cannot say “THE END” until I mention 2 articles that really helped me understand solving this problem:

This entry was posted in Scala. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s