From: James Gray <james@...>
Date: 2008-01-29T00:16:27+09:00
Subject: Re: [QUIZ] Making Change (#154)

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

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

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

#!/usr/bin/env ruby -wKU

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

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

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

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

         return cur_coins.sort_by { |coin| -coin } if cur_total ==  
amount
         cur_totals[cur_total] ||= cur_coins       if cur_total < amount
       end
     end

     return if cur_totals.empty?

     prev_totals = cur_totals
   end
end

if __FILE__ == $PROGRAM_NAME
   amount, *coins = ARGV.map { |n| Integer(n) }
   abort "Usage:  #{$PROGRAM_NAME} AMOUNT [COIN[ COIN]...]" unless  
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  
at what the fastest strategies have been.

James Edward Gray II