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