```Here is my second attempt:

def make_change(a, list = [25, 10, 5, 1])
# to pass testcases :-P
return nil if a < 0
return nil if a != a.floor

parents = Array.new(a + 1)
parents = 0
worklist = 
while parents[a].nil? && !worklist.empty? do
base = worklist.shift
list.each do |coin|
tot = base + coin
if tot <= a && parents[tot].nil?
parents[tot] = base
worklist << tot
end
end
end

return nil if parents[a].nil?
result = []
while a > 0 do
parent = parents[a]
result << a - parent
a = parent
end
result.sort!.reverse!
end

parents[a] is nil if the solution for amount "a" has not been found
yet, and a-c if the solution is the same as the solution for amount "a-
c" plus a coin of value "c".  The solution is reconstructed in the
second while loop.

My first solution used an 1.upto(a) loop to compute the optimal
solution for make_change(1), then for make_change(2), etc.  This was a
classic dynamic programming style where lower-cost solutions replace
older ones as they are found.  In this solution, instead of computing
subproblem solutions in order of amount, I compute solutions in order
of cost: first all solutions of cost 1, then all solutions of cost 2,
etc., until the solution is found for the requested amount (see the
parents[a].nil? test).  It is interesting that in this way we don't
even need to store the solutions' costs.

The worst case is when there's no solution and it has cost O(a |
list|).  I didn't make any attempt at optimizing it.

The performance is good; vsv's testcases run in 10 seconds (compared
to 30 for my 1.upto(a) solution).

I tried running a similar program in GNU Smalltalk and the results
were disappointing for Ruby 1.8: GNU Smalltalk was about 10 times
faster for this solution, and 18 times faster for the slower
solution.  The ratio goes down from 18 to 10 probably because variable-
size collection in Smalltalk require an OrderedCollection, which is
written in 100% Smalltalk (unlike Ruby's Arrays and Smalltalk's fixed-
size Arrays).  I'd be very interested if people ran it under Ruby 1.9
or Rubinius and gave times for it.

Paolo

```