From: Jesse Merriman <jesse.d.merriman@...>
Date: 2008-01-28T01:01:16+09:00
Subject: [SOLUTION][QUIZ] Making Change (#154)

--Boundary-00=_RrKnHbXcKwOd0/F
Content-Type: Multipart/Mixed;
  boundary="Boundary-00=_RrKnHbXcKwOd0/F"

--Boundary-00=_RrKnHbXcKwOd0/F
Content-Type: text/plain;
  charset="utf-8"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Here's my solution, attached and pastied here:
http://pastie.caboo.se/pastes/144060

Its recursive, can solve the simplest problems, but soon gets overwhelmed by 
cases like Yoan's Swiss money test. I killed it after 12 hours. Solutions are 
stored as hashes of coin-value => count (if you want it in the array form its 
easy to convert - see line 59). Its also accepts a score function, and so can 
do things like:

jesse@ricercar $ ./make_change.rb 21 1 7 10 least
0 of 1-coins
3 of 7-coins
0 of 10-coins
3 total
jesse@ricercar $ ./make_change.rb 21 1 7 10 variety
4 of 1-coins
1 of 7-coins
1 of 10-coins
6 total
jesse@ricercar $ ./make_change.rb 21 1 7 10 most
21 of 1-coins
0 of 7-coins
0 of 10-coins
21 total

I played around with a few optimizations, like storing the coins array once 
and passing indices instead of duplicating it on line 18, but they hardly 
made a difference.

-Jesse

--Boundary-00=_RrKnHbXcKwOd0/F
Content-Type: application/x-ruby;
  name="make_change.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename="make_change.rb"

#!/usr/bin/env ruby
# Ruby Quiz 154: Making Change
# Score-function-general solution.
# Jesse Merriman

Infinity = 1.0 / 0

module Enumerable
  def sum; inject { |sum, x| sum + x }; end
end

LeastCoins = lambda { |sol| - sol.values.sum }
MostCoins  = lambda { |sol| sol.values.sum }
Variety    = lambda { |sol| sol.values.select { |v| v > 0 }.size }

def make_change amount, coins = [25, 10, 5, 1], scorer = LeastCoins
  pick = coins.first
  others = coins[1..-1]

  if coins.size == 1
    return (amount % pick).zero? ? {pick => amount / pick} : nil
  end

  best_so_far = {:sol => nil, :score => -Infinity}

  (0 .. amount / pick).each do |count|
    sol = make_change amount - count * pick, others, scorer

    if not sol.nil?
      sol[pick] = count
      s = scorer[sol]
      if s > best_so_far[:score]
        best_so_far[:sol] = sol
        best_so_far[:score] = s
      end
    end
  end

  best_so_far[:sol]
end

if $0 == __FILE__
  amount = ARGV.first.to_i
  coins = ARGV[1..-2].map { |x| x.to_i }
  scorer = case ARGV.last
    when /most/i    then MostCoins
    when /variety/i then Variety
    else LeastCoins
  end

  sol = make_change amount, coins, scorer
  if sol.nil?
    puts 'No solution could be found.'
  else
    sol.each do |coin, count|
      puts "#{count} of #{coin}-coins"
    end
    puts "#{sol.values.sum} total"
    #sol.to_a.map { |x| [x.first] * x.last }.flatten
  end
end


--Boundary-00=_RrKnHbXcKwOd0/F--
--Boundary-00=_RrKnHbXcKwOd0/F--