From: "Eric I." <rubytraining@...>
Date: 2008-01-28T05:50:02+09:00
Subject: Re: Making Change (#154)

I made a slight modification to Paolo's solution, so it avoids
searching coin combinations that are permutations of others (i.e.,
[25, 1] and [1, 25]).  It does this by only allowing the system to add
coins at or beyond the last coin used in the combination being built.
So, if the coins are [25, 10, 5, 1], and we're building from 25, 10,
10, 5 then the next coin be only a 5 or a 1.  It seems to speed
Paolo's solution by about 30% on my system.

Eric

----

Are you interested in on-site Ruby training that's been highly
reviewed by former students?  http://LearnRuby.com

====

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, 0]]
  while parents[a].nil? && !worklist.empty? do
    base, starting_index = worklist.shift
    starting_index.upto(list.size - 1) do |index|
      coin = list[index]
      tot = base + coin
      if tot <= a && parents[tot].nil?
        parents[tot] = base
        worklist << [tot, index]
      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