Change algorithm

gistfile1.txt

object coins {
  val usa = Seq(.01, .05, .10, .25)
  val euro = Seq(.01, .02, .05, .10, .20, .50, 1, 2)
}

def cents(coin: Double) = (coin * 100).toInt

def makeChange(algorithm: (Double, Seq[Double]) => Map[Double, Int],
               denominations: Seq[Double],
               amount: Double) = algorithm(amount, denominations).values.sum

def fastChange(amount: Double, denoms: Seq[Double]) = {

  val result = denoms.foldRight(cents(amount), Map.empty[Double, Int]) { (coin, change) =>

    val oldRemainder = change._1
    val coinQty = oldRemainder / cents(coin)
    val newRemainder = oldRemainder - (coinQty * cents(coin))

    (newRemainder, change._2 + (coin -> coinQty))
  }

  result._2

}

def accurateChange(amount: Double, denoms: Seq[Double]) = {

  // TODO no sense promoting coins that divide evenly into greater coins
  // TODO try deeper promotions

  denoms.sorted.foldLeft(fastChange(amount, denoms)) { (best, coin) =>

    val coinOrder = (denoms.sorted diff Seq(coin)).+:(coin)
    val result = fastChange(amount, coinOrder)

    if(result.values.sum > best.values.sum) best else result

  }

}

val noMoreNickels = coins.usa diff Seq(.05)

val fastAllCoins = makeChange(fastChange, coins.usa.sorted, .30) // 2
val fastNoNickels = makeChange(fastChange, noMoreNickels.sorted, .30) // 6
val accurateAllCoins = makeChange(accurateChange, coins.usa.sorted, .30) // 2
val accurateNoNickels = makeChange(accurateChange, noMoreNickels.sorted, .30) // 3