[SUMMARY] Making Change (#154)

One submitter commented that our solutions were pretty complex.  The reason for
that is that we all sat around dreaming up pathological edge cases that took a
long time to solve without some complex code.  The good news is that such cases
don't generally come up in the day to day change making of most countries.

Let's begin with a peek at a non-complicated solution from Ilan Berci:

	def make_change(amount, coins = [25,10,5,1])
	  coins.sort.
	        reverse.
	        map{|coin| f = amount/coin; amount %= coin; Array.new(f){coin} }.
	        flatten
	end

This approach uses a greedy algorithm.  We call it greedy because it always
tries to move as close to the end result as possible with each step.  In this
particular case, that is accomplished by working from the biggest coins to the
smallest and always grabbing as many of each type of coin as possible without
going over our limit.

This technique is trivial and it works for all change made in the U.S., plus
many other countries.  It doesn't work for the fictional second test case given
in the quiz though, returning [10, 1, 1, 1, 1].

That's where the complexity began to creep in.

If we're going to get right answers for any combination of coins, we will have
to search all possible combinations.  Doing that for certain sets of coins can
take a long time and we would really rather it be fast.  To get speed we will
have to use something smarter than a brute force algorithm that checks all the
combinations.

Before I show the smarter approaches though, it's important to note that you
likely wouldn't need to be this clever to make change in any country.  The
reason is simple:  we don't usually give change for large amounts since we tend
to just use non-coin funds for that.  That keeps the search space small enough
that advanced techniques aren't too important.  Of course, it's still fun to
explore the possibilities.

This problem actually turns out to be famous in computer science.  It's called
the Knapsack Problem.  Once you know that you can apply the techniques often
used on that problem, the most popular of which is to use a dynamic programming
algorithm.  ("Dynamic programming" has a different meaning here than we often
use in Ruby circles about code writing code.)

The trick to a dynamic programming algorithm is to remember the smaller pieces
of a bigger problem once we've figured them out and reuse them as much as
possible without having to repeat the work.  You can do that while working your
way up to a solution or down from a solution, but the top-down approach, often
called memoization, is pretty popular.

Here's some code from Carl Porth that implements simple memoization using a
Hash:

	def make_change(amount, coins = [25, 10, 5, 1])
	 coins.sort! { |a, b| b <=> a }
	
	 # memoize solutions
	 optimal_change = Hash.new do |hash, key|
	   hash[key] = if key < coins.min
	     []
	   elsif coins.include?(key)
	     [key]
	   else
	     coins.
	       # prune unhelpful coins
	       reject { |coin| coin > key }.
	
	       # prune coins that are factors of larger coins
	       inject([]) {|mem, var| mem.any? {|c| c%var == 0} ? mem : mem+[var]}.
	
	       # recurse
	       map { |coin| [coin] + hash[key - coin] }.
	
	       # prune unhelpful solutions
	       reject { |change| change.sum != key }.
	
	       # pick the smallest, empty if none
	       min { |a, b| a.size <=> b.size } || []
	   end
	 end
	
	 optimal_change[amount]
	end

First, have a look at the structure of this code.  It doesn't really seem to do
much from the outside.  It sort!()s the coins from biggest to smallest, defines
a Hash, and indexes into the Hash to magically come up with the answer.  The
magic is in the definition of the Hash.

To understand how this works, you just have to think of the main problem in
smaller slices.  Say we want to make 39 cents of change with U.S. coins.  Here's
how the problem breaks down:

	              make_change(39)
	[25]        + make_change(39 - 25)
	[25, 10]    + make_change(39 - 25 - 10)
	[25, 10, 1] + make_change(39 - 25 - 10 - 1)
	
	# ...

Carl's magic Hash does exactly this process.  Have a look at this line of code
plucked from the middle of the Hash definition:

	       # ...
	       
	       # recurse
	       map { |coin| [coin] + hash[key - coin] }.
	       
	       # ...

That's the exact pattern I showed above.

The memoization part is basically automatic here, thanks to how Ruby's Hash
works.  When you provide a default block to the constructor like this, it will
be called the first time some key is accessed that the Hash doesn't know.  That
block can assign a value for the key though, as Carl does in this code, and then
all future attempts to access the same key are a simple Hash lookup (bypassing
all of the work in the block).  That makes sure that once we have found some
coin combination, we never have to find it again.

What are all the rest of those lines in Carl's solution though?  Pruning. 
That's the other trick for getting speed when searching a big space.  Throw out
everything you possibly can to make the work as small as possible.  Carls throws
out coins that are bigger than the current amount remaining, coins that are
factors of larger coins we could use, and change combinations that don't add up
to what we need.  This makes for less work and makes the code go faster.

Paolo Bonzini submitted another dynamic programming approach that was one of the
faster solutions we saw.  It's a bottom-up approach in contrast to the
memoization we just saw.  It prunes the space, orders the combinations checked
to find smaller counts faster, and avoids building a bunch of coin Arrays as it
works (Ruby's GC will slow you down when it kicks in).  Eric I. submitted a
small enhancement to the code that made it even faster.  The downside of all
this is that it's a little harder still to follow.

Let's see how that modified version works:

	def make_change(a, list = [25, 10, 5, 1])
	 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

The main work here is done in the second chunk of code and to break that down,
you need to know two things.  First, the parents Array holds values at the index
of a given amount for the previously used total.  That sounds a lot more
complicated than it is.  For example, in the make_change(11, [10, 1]) call,
parents ends up looking like this:

	[0, 0, nil, nil, nil, nil, nil, nil, nil, nil, 0, 10]

It may not look like it, but the answer is hidden in there!  To find it, you
start at the desired total (as an index) parents[11].  That's 10, which is the
previous total.  So, to find the last coin, we can just subtract them which
gives us the 1.  Then we move to that previous amount at parents[10].  That's a
zero and subtracting again gives us 10, the other coin needed.  This process I
just described is exactly what the third chunk of code does after a solution has
been found in the second chunk.

The second thing you need to understand is how it searches for solutions. 
Essentially, the worklist Array holds the progress so far.  Each bit of work in
there is shift()ed off, added to, and appended back on to the end if there's
more work to do.  This is the classic pattern for unrolling recursion into an
iterative solution.

Now each piece of work in worklist is the total we are currently on, plus an
index for the last coin added.  The total we are currently on represents the
work we need to do.  We can add coins to that to find new totals.  The index for
the last coin added just keeps us from repeating work by checking larger coins
than we've already covered.  (This solution assumes the coins are in order from
biggest to smallest.)  That's one example of the pruning done here.  The other
is the if conditional that only adds work below the desired total.

It's important to think about how using a queue works here.  First it will hold
a single zero coin total at the front.  In processing that, one coin totals will
be added onto the back.  When we reach those, the code will begin to add two
coin totals.  This means we are performing a breadth-first search from the
smallest coin count solutions to the largest.  This ensures that the first right
answer we see is the best and saves us any needless work.

My thanks to all who worked so hard to make sure we can quickly calibrate absurd
sums of change.  I'm sure we are collectively eliminating the need for paper
money thanks to our fun and games.

Tomorrow we will tackle a current hot topic in the Ruby community...