From: Paolo Bonzini <bonzini@...>
Date: 2008-01-28T01:04:57+09:00
Subject: Re: Making Change (#154)

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] = 0
  worklist = [0]
  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