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 B.:
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 P. 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 B. 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…