making_change.scala

object main
{
  val coins = Array(1, 5, 10, 25)
  val minCoin = coins.reduceLeft (_ min _)
  var table: Map[Int, Seq[Int]] = Map()
  val infinity: Seq[Int] = for (i <- 1 to 100000) yield i
          
  
  def calculateMinCoins(n: Int): Seq[Int] = {
    if (n == 0) { Seq() }
    else if (n < minCoin) { infinity }
    else {    
      table getOrElse (n, {
        val subSolutions: Array[(Int, Seq[Int])] = coins map { c => (c, calculateMinCoins(n - c)) }
        val bestSubsolution = (subSolutions.sortBy (_._2.length)).head
        val solution = bestSubsolution._2 ++ Seq(bestSubsolution._1)
        table = table.updated(n, solution)
        solution
      })
    }
  }
  
  def main(args: Array[String]): Unit = {
    println(calculateMinCoins(9))
  }
}