# Making Change (#154)

**URL:** <https://www.ruby-forum.com/t/making-change-154/127702>\
**Category:** Ruby\
**Created:** [January 31, 2008, 2:59pm UTC](https://www.ruby-forum.com/t/making-change-154/127702 "2008-01-31T14:59:50Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [January 31, 2008, 2:59pm UTC](https://www.ruby-forum.com/t/making-change-154/127702/1 "2008-01-31T14:59:50Z")

</div>

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…