The Beer Money Problem - Two Less Successful Solutions (#3)

This is the final post about the MLUG Beer Money challenge: if you are lost, start here.

The first solution method that I describe isn't particularly fast, but it is fun.

In Post #1 I talked about 'counting up in base quantity', and I later realised that this is something that can be accomplished with the quotient remainder function. So this code basically generates the list of all possible combos of coins, and then does the comparison in a separate loop. This extra comparison loop is necessary because the combinations are generated a column at a time, whereas the comparison is done on rows. And with no way of ensuring that combinations above the goal amount are not generated, it does take rather longer than the other methods. But I have a soft spot for it because the quotient remainder trick is rather nifty. Maybe one day I'll figure out a way of doing it row-wise.

This is what it looks like - see Quotient Remainder Solution.vi in my code.

A solution that uses two lots of the Quotient Remainder function

My final solution uses permutations instead of combinations - here I mean that it matters which of the coins of the same denomination that we choose. (Luckily we don't care about the order that the coins are presented to the cashier, or the calculation would be very onerous). It is written so that its depth first search only explores the tree branches that have the potential to yield solutions. However the way I have implemented it to store the successful permutations (plus, the sheer number of permutations) means that it is very slow. I can use my other solution and some factorials to back-calculate how many permutations there are: I get 2.2 billion.

Back-calculating how many permutations there are.

So the problem is a bit too big for this method, but it does make some pretty patterns. If you're still interested in how I implemented it, here is a description of my process:

My first idea was that I could order all of the coins from largest to smallest, and then represent them as a binary array. The array would have 42 elements (to match the 42 coins), and the MSB (Most Significant Bit) would be arbitrarily on the right of the array and would represent the largest coin. I would set a bit to 1 if the coin is used, or 0 otherwise. I could then count up from 0 in binary, evaluating the total for each, until all possibilities have been exhausted. The number of possibilities that were equal in value to the goal of £11.99 could then be counted. 

This solution is easy to implement and explain. But how many entries would need checking? Each coin has 2 options: to use it or not to use it. 2^42 is ... hmmm... 4.4 x 10^12, or 4.4 billion. LabVIEW stores boolean data as 8-bit values, so 4.4 billion x 42 array elements x 1 byte per element is 185 gigabytes of data. My 32-bit copy of LabVIEW can only keep 4 Gb of data in its memory, so I wouldn't want to output that array at the end! Plus searching every single possibility would take a long time.

I quickly came up with a way of speeding the process up. Instead of counting up in binary, I could start with an array of zeros, then starting from the right (large) coins, set each subsequent bit to 1 (i.e. add more and more coins of smaller value), then apply some rules. After the monetary value is evaluated:

• If the amount is less than the goal amount, add the boolean value to a 'hold' list to come back to, then set the next bit to 1.

• If the amount is equal to the goal amount, count it as a result and go back to one of the items in the 'hold' list. There's no point adding more smaller-denomination coins to the total because it would just go over.

• If the amount is more than the goal amount, again there's no point adding more smaller denomination coins, so go back to one of the items in the 'hold' list.

If an item from the hold list is picked up, the largest value coin is discarded and the larger coin to its left is instead used. Otherwise you would be treading the same ground again.

This might be a bit tricky to visualise, so I made a quick video using a simplified example with a goal of £7.

However, keeping this 'hold list' is fairly memory intensive. If you visualise the problem as a massive tree, the hold list gets used to fork a branch. Back in the day, I dabbled in Decision Maths and Game Theory, so am used to visualising these sort of problems as a 'tree' or State Space. But being a visual programmer, I struggle slightly to explain this all in words. Looking at the code is probably the easiest way of making sense of this. 

So, those were my various solutions to this fascinating problem. Thanks for reading - do let me know if you've come up with any interesting solutions yourself!