#coin problem

A McNugget number is an integer that can be obtained by adding orders of McDonald’s Chicken McNuggets, which originally came in boxes of 6, 9 and 20. For instance, 61 is McNugget (20 + 20 + 9 + 6 + 6), while 23 is not.

According to Schur’s theorem, any sufficiently large integer can be expressed as a linear combination of 6, 9 and 20 since these integers are coprime. Therefore there exists a largest non-McNugget number. It turns out that every positive integer is a McNugget number, with the following finite number of exceptions: 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37 and 43 (sequence A065003 in OEIS).

Exponential runtime algorithms get a bad rap. They're not really terrible, but they scale terribly, which means for a lot of problems and a large number of reasonable inputs, they work perfectly well. Usually you need to show some artificially high input to bring out the brute-force solution's ugly super-long runtime-side. That's why I like the Coin problem (also called the Change problem): It's a great example of a problem with an (almost) unrunnable brute-force solution, even for perfectly reasonable inputs. 

The Coin problem:

Given a list of coin-denominations, how many ways can you combine coins them to form some target amount? Here's an example: Your list of coin-denominations are [3,2,1] with  a target amount of 7. 

Here's a solution that totals up to 7: (1, 2, 0). That is, 1 three-coin, and 2 two-coins for a total of 7. You could also just have 7 one-coins. Or three 2-coins with one 1-coin and so on (the total number of ways is 8, by the way).

Here's a better real-world example: In the United Kingdom, they have eight coin-denominations (in pence), ranging from a penny to two pounds: [1, 2, 5, 10, 20, 50, 100, 200]. How many ways you can combine them to get two pounds (200 pence)?

This isn't an artificial example - the coin denominations are real. And the target amount isn't insanely high. Yet a brute-force solution took me seventy-five minutes to run on a i7 laptop.  

Solution I: Brute Force

All solutions are essentially a vector over the list of coins - like the (1,2,0) example above. You could have 0 of the first coin, or maybe 1 or more, depending on the value of (target/coin). For instance, we can use 0, 1 or 2 of the three-coin above. Similarly, the number of two-coins used for a solution could range between 0-3 and 0-7 for the one-coin. 

We could get all possible ways by three for-loops, one for each coin, ranging between 0 and (target/coin). This is exactly equivalent to a cartesian product, which is excellent news because python's itertools lib has a cartesian-product-generating function 1. 

So we now simply generate all possible vectors and then check each one to see if they total up to the target. Here's the code:

If you look at the runtime, you can see this scales terribly: We have two elements for the runtime: One's the gap or ratio between the target and the smallest-denom coin (a penny), which is at most 200 in our example, (this forms the base) and two, the number of coins (eight in our example) which dictates the number of for-loops (and thus forms the exponent). So the outer loop has an upper bound of 2008 with the inner section taking O(n).

So O(bn)*n is an upper bound (probably non-strict, but it'll do). The point is, it scales terribly. 

To see if my laptop could handle it, I did a quick back-of-the-envelope calculation for number of cycles:

The outer loop consists of:

itertools.product(range(200+1), range(100+1), range(40+1), range(20+1), range(10+1), range(4+1), range(2+1), range(1+1))

which is 5.76 billion iterations * inner loop=8  yields roughly 46 billion iterations. Multiplied by 3 or 4 constant-time ops inside the inner loop (there's a break, remember?), we get roughly 140 to 180 billion operations. To find out how long my laptop takes for each common op (in Python), I ran a simple loop containing 1 mult/add/if op. In one second my laptop runs 17 million mult ops / 25 million add ops / 30 million if ops. At that rate, my algorithm should take roughly 6000 seconds to run. Actually, it took  me 4531 seconds - 75 minutes. So we should really be looking for a better solution. 

Solution II : Dynamic programming

Let's have a closer look how we solve coin problems using human computation: Let's sort coins in ascending order and then take the first coin - a penny. How many ways can we represent 2 pounds with pennies? Exactly one way - with 200 coins. In fact, for an target amount x, we can represent it exactly one way with pennies - using x pennies. How many ways can we represent say, 10 pence with pennies and tuppence - coins (1,2)? Well, we know it'll include all the ways we can represent it with pennies (which we know is 1). That is, it'll include all the ways we can represent 10 with some pennies and no (0) tuppence. Then we check if it can be represented with some pennies (possibly 0) and 1 tuppence, with 2 tuppence and so on. We can think of this recursively: If we represent 10 pence with (some combination including) 1 tuppence, we need to know something else : How many ways can we represent the target amount minus the 1 tuppence (8 pence) with (1,2)?

Like most dynprog solutions, I actually needed to spend nontrivial time working out the recurrence relation from several small examples by hand. So here's our new solution: We make a matrix with rows as target amounts from 0 to our (final) target (200 in our example) and the coins (sorted, ascending) are the columns. We populate the first row (target=0) with all 1s since for any set of coin-denominations, there's exactly one way to represent that:  0 of the first coin, 0 of the second coin, etc. We populate the first column (denom = one penny) with all 1s, since for any target x, there's exactly one way to represent it with pennies (with x pennies, to be precise). Then exactly like we mentioned above, for any cell, let's say the 200th row X 2nd column ("How many ways can we represent 200 pence with all coins less than or equal to tuppence?") , our value is equal to:

(1) How many ways can we represent 200 with just pennies (matrix[200,1])  +

(2) How many ways can we represent (200- (1*tuppence)=198) with pennies and tuppence (matrix[198,2]).

 We have our recurrence relation. Now we just loop over and populate our matrix using this relation. The answer is in matrix[200, 200] ("How many ways can we represent 200 pence with coins less than equal to two pounds?"). 

Here's the code:

The algorithm may have taken a while to work out, but the speedup was huge - this took just over a thousandth of a second to get the result.That's a speedup of four-and-a-half billion times.

Solution III : Recursive

There's more than one way to skin a cat - another human-computation approach is to consider the coins in descending order:

Considering the 2-pound-coin, we can represent 200 pence with 1 * 2-pound coin (and nothing else, in that solution). Considering the 1-pound coin, we could represent 200 pence with 2 * 1-pound-coins, or 1 * 1-pound coin and 2 * 50-pence coins. Or 1 * 1-pound coins, 1 * 50-pence coin and 2 * 25-pence coins. Or 1 * 1-pound coins, 1 * 50-pence coins, 1 * 25-pence coins,...and so on. You get the idea - We get a new subproblem after taking away the value of a coin from the target amount (much like the dynprog approach). How many ways can you represent 200 pence with at least one 1-pound coin?  We need to calculate how many ways to represent 200 -100 =100 with coins of 50 pence or lower, and this further reduces to another subproblem with a smaller target amount (and eventually smaller coin denominations) and so on. 

And here's the code for that solution: 

This takes 1.75 seconds to find the solution.