```On Jan 25, 2008, at 9:50 AM, Ruby Quiz wrote:

> This week's Ruby Quiz is to complete a change making function=85

Here's my own solution to this week's quiz:

#!/usr/bin/env ruby -wKU

def make_change(amount, coins =3D [25, 10, 5, 1])
return [ ] if amount.zero?

coins =3D coins.sort_by { |coin| -coin }

prev_totals =3D {0 =3D> [ ]}
loop do
cur_totals =3D { }

prev_totals.each do |prev_total, prev_coins|
coins.each do |coin|
cur_total, cur_coins =3D prev_total + coin, prev_coins + [coin]

return cur_coins.sort_by { |coin| -coin } if cur_total =3D=3D =20=

amount
cur_totals[cur_total] ||=3D cur_coins       if cur_total < =
amount
end
end

return if cur_totals.empty?

prev_totals =3D cur_totals
end
end

if __FILE__ =3D=3D \$PROGRAM_NAME
amount, *coins =3D ARGV.map { |n| Integer(n) }
abort "Usage:  #{\$PROGRAM_NAME} AMOUNT [COIN[ COIN]...]" unless =20
amount

p coins.empty? ? make_change(amount) : make_change(amount, coins)
end

__END__

Has anyone done time comparisons of the submissions?  I'm just curious =20=

at what the fastest strategies have been.

James Edward Gray II

```