## Sunday, April 27, 2008

### Greedy Coin Changer in Scala

OnLamp has published this Python implementation of the Greedy Coin Changer. Here is my version of a functional implementation of the same in Scala.

object GreedyCoinChanger {  def divMod(dividend: Int, divisor: Int) = {      (dividend / divisor, dividend % divisor)  }  // the list has to be sorted in descending order of denomination  def change(coins: List[Int], amount: Int) = {    def changeOne(pair: (List[Int], Int), div: Int) = {      val dm = divMod(pair._2, div)      ((dm._1 :: pair._1), dm._2)    }    (((List[Int](), amount) /: coins)(changeOne(_,_)))._1.reverse  }  def main(args: Array[String]) = {    println(change(List(25, 10, 5, 1), 71))  }}

Running this will print :

>> List(2, 2, 0, 1)

indicating 2 quarters, 2 dimes, 0 nickels and 1 penny. To make things a little more explanatory and verbose, here is a slightly more decorated version :

object GreedyCoinChanger {  def divMod(dividend: Int, divisor: Int) = {    (dividend / divisor, dividend % divisor)  }  def pluralize(no: Int, phrase: String) = phrase match {    case "penny" if no > 1 =>        "pennies"    case something if no > 1 =>        something + "s"    case other => other  }  // the list has to be sorted in descending order of denomination  def change(coins: List[(Int,String)], amount: Int) = {    def changeOne(pair: (List[String], Int), denomination: (Int,String)) = {      val (div, mod) = divMod(pair._2, denomination._1)      div match {        case 0 => (pair._1, mod)        case _ => ((div + " " + pluralize(div, denomination._2) :: pair._1), mod)      }    }    (((List[String](), amount) /: coins)(changeOne(_,_)))._1.reverse.mkString("(", ", ", ")")  }  def main(args: Array[String]) = {    println(change(List((25,"quarter"), (10,"dime"), (5,"nickel"), (1,"penny")), 71))  }}

Running this will print :

>> (2 quarters, 2 dimes, 1 penny)

I am not an expert in Scala or functional programming. Any suggestion to make it more idiomatic is most welcome.

paulk said...

I did a Groovy version here:
http://groovy.codehaus.org/Greedy+Coin+Changer+in+Groovy

Digressing a bit from the intent of the post...
Does this problem map to a special case of unbounded knapsack problem where it is a 0/1 problem with cost same as value? If so, then it is NP-Complete probably.

Gregg said...

scala> println(c.change(List((25,"quarter"), (16, "sixteener"), (10,"dime"), (5,"nickel"), (1,"penny")), 48))
(1 quarter, 1 sixteener, 1 nickel, 2 pennies)

Ideally, wouldn't this print "3 sixteeners"? How could the algorithm be adjusted to return the least number of coins in this case?

Gregg said...

never mind - I see you have another post on the topic - thanks - very informative.