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…