From: James Gray <james@...>
Date: 2008-01-28T08:08:03+09:00
Subject: Fwd: Please Forward: Ruby Quiz Submission

--Apple-Mail-1--170211014
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed;
	delsp=yes
Content-Transfer-Encoding: 7bit

Begin forwarded message:

> From: "Clark Grubb" <clarkgrubb@gmail.com>
> Date: January 27, 2008 1:04:14 PM CST
> To: submission@rubyquiz.com
> Subject: Please Forward: Ruby Quiz Submission
>
> This is a recursive solution.  We prune the possibilities needing
> examination by observing that if a coin has value N, then among N  
> coins of
> lesser value, it will be possible to replace some of them with fewer
> coins of value N.  If we could not do this, each combination of the  
> lesser coins
> would have to have a different value modulo N, none of which could  
> be 0 modulo N.
> --------------------------
>
> def make_change_aux(amount, coins)
>   coin = coins.first
>   if 1 == coins.size
>     return 0 == amount % coin ? [coin] * (amount / coin) : nil
>   end
>   change = nil
>   (amount/coin).downto([ amount/coin - coins[1], 0 ].max) do |n|
>     a = make_change_aux(amount - n * coin,
>                         coins.slice(1, coins.size-1))
>     if a and (change.nil? or a.size + n < change.size )
>         change =  ([ coin ] * n).concat(a)
>     end
>   end
>   change
> end
>
> def make_change(amount, a = [25,10,5,1] )
>   coins = a.uniq.sort.reverse
>   coins.each do |c|
>     raise "Not a positive integer value: #{c}" if c < 1 or c != c.to_i
>   end
>   if coins.empty?
>     return 0 == amount ? [] : nil
>   end
>   make_change_aux(amount, coins)
> end
>


--Apple-Mail-1--170211014--