Find minimum number of coins (count and list of coins too)

Question

For a given set of denominations, you are asked to find the minimum number of coins with which a given amount of money can be paid. Assume that you can use as many coins of a particular denomination as necessary.

For example, given the denominations 1, 3, 4, and the target amount 6, the algorithm should find the optimal 2 coins required: 3 + 3.

As an exercise while learning Scala, I implemented two versions. One to find just the number of coins, and one to find the list of coins. I'm looking for a review of all aspects of this code.

import org.junit.runner.RunWith
import org.scalatest.FunSuite
import org.scalatest.junit.JUnitRunner
    
@RunWith(classOf[JUnitRunner])
class FindMinCoinsTest extends FunSuite {

  def findMinCoins(amount: Int, coins: Set[Int]): Int = {
    def findMinCoins(amount: Int, count: Int): Int = {
      if (amount == 0) count
      else if (amount < 0) Integer.MAX_VALUE
      else coins.map(coin => findMinCoins(amount - coin, count + 1)).min
    }

    val count = findMinCoins(amount, 0)
    if (count == Integer.MAX_VALUE) 0
    else count
  }

  test("find 10 with 1, 5, 7") {
    assert(2 == findMinCoins(10, Set(1, 5, 7)))
  }

  test("find 10 with 1, 5, 10") {
    assert(1 == findMinCoins(10, Set(1, 5, 10)))
  }

  test("find 7 with 3, 5") {
    assert(0 == findMinCoins(7, Set(3, 5)))
  }

  test("find 6 with 1, 3, 4") {
    assert(2 == findMinCoins(6, Set(1, 3, 4)))
  }

  def findMinCoinsList(amount: Int, coins: Set[Int]): List[Int] = {
    def findMinCoinsList(amount: Int, list: List[Int]): (Boolean, List[Int]) = {
      if (amount == 0) (true, list)
      else if (amount < 0) (false, Nil)
      else {
        val solutions = coins.map(coin => findMinCoinsList(amount - coin, coin :: list)).filter(_._1)
        if (solutions.nonEmpty) solutions.minBy(_._2.size)
        else (false, Nil)
      }
    }

    findMinCoinsList(amount, Nil)._2.sorted
  }

  test("find sorted list, for 10 with 1, 5, 7") {
    assert(List(5, 5) == findMinCoinsList(10, Set(1, 5, 7)))
  }

  test("find sorted list, for 10 with 1, 5, 10") {
    assert(List(10) == findMinCoinsList(10, Set(1, 5, 10)))
  }

  test("find sorted list, for 7 with 3, 5") {
    assert(Nil == findMinCoinsList(7, Set(3, 5)))
  }

  test("find sorted list, for 6 with 1, 3, 4") {
    assert(List(3, 3) == findMinCoinsList(6, Set(1, 3, 4)))
  }

  test("find list 7 with 1, 3, 4") {
    assert(List(3, 4) == findMinCoinsList(7, Set(1, 3, 4)))
  }

}

Answer 1

Here are some things that I would maybe do in another way:

• replace Integer.MAX_VALUE by Int.MaxValue
• replace cascade if-else statements by pattern matching
• return value of Int.MaxValue replaced by throwing an IllegalArgumentException
• try to make recursive functions tail-recursive and use the @tailrec annotation
• maybe use Seq instead of List. IMHO you can use List as a concrete implementation for Seq. I am not 100% sure in this case that there won't be additional overhead (e.g. by creating unnecessary collection objects). Read about scala's collection API.
• Maybe you would like to simplify the whole thing by writing just on top-level function def minimumCoins(amount: Int, availibleCoins: Seq[Int]): Seq[Int]. It returns the coins as solution. An empty Seq means you need no coins. You can easily get the number of coins by the size of the Seq. There can be cases where no solution exists! What should happen in those cases? Maybe an ecxeption should be thrown again. Or was that the sense of the boolean return value? Maybe you wrap the returned Seq with an Option like Option[Seq[Int]].
• I did not really spend time understanding your algorithm. If that is what you want you should tell it explicitly. Anyway some collections have combinatorical functions like mySeq.combinations(5) and mySeq.permutations which can be useful for such problems. If you have an specific analytic algorithm (from your brain or from anywhere else) it is probably better and more efficient than those based on those functions. Those functions tend to solve problems by something like brute-force. So the code used for this may be of little amount and you get something useful quickly and with less analytics. You can be more productive and let the computer do the work. On the other side, processing all combinations or permutations can be very inefficient especially on large parameters their number gets quickly very very high. Those functions are alluring.