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.

4 comments:

paulk said...

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

Biswadeep said...

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.