The Beer Money Problem - A Simple Approach (#1)

This post is about my first attempt at answering the MLUG beer money challenge outlined in this post.

So, where to start? After grappling with this problem for a while, I decided to type up exactly what I was doing when trying to solve it on paper, and go from there.

The question is slightly ambiguous: do we care about which of the identical coins (e.g. which of the 10 x 1ps) we have selected? I decided that we didn't - I've never had a checkout assistant examine my coins at Tesco. So by this logic the coins of the same denomination can be grouped together. Anyway, if we did care about this, there are ways of converting between the two types of answer.

Imagine you're counting up in binary: 000, 001, 010, 011, 100 etc. Let the MSB represent the largest denomination coin/note, and the LSB represent the smallest. (You could do it the other way of course, but I find that confusing). Binary is the 'base 2' numeral system, but we don't just have 0 or 1 of each type of coin. So make each digit base N, where N is the quantity of each coin in the wallet.

Let's change the question a little to make it easier to demonstrate. If I had 3 £10 notes, 2 £5 notes and 1 £2 coin, I would count upwards like this: 

000, 001, 002, 003 (incrementing the £2 coins)

010, 011, 012, 013 (adding a £5 note to the above)

020, 021, 022, 023 (adding another £5)

100, 101, 102, 103 (etc.)

110, 111, 112, 113

120, 121, 122, 123

Imagining this as a nested for loop:

Figure 1: The above sequence as a nested for loop

You'll notice that all of the answers are generated in the middle loop, and then I just index them and concatenate them out to get a list. Also notice that I have to add 1 to the quantities because i is zero based.

Here is the output that it generates: notice that I've transposed the array to make it fit on the screen better

Figure 2: Output generated by the above code.

Top tip - to get Front Panel screenshots without the grid etc., use Ctrl+M to toggle between run and edit mode.

So you can see that if I do the dot product of each solution column against it's value vector, out pops the total value of each solution. This can be compared to the goal amount. You can also see that if I add 1 to each element in the quantity vector, then multiply the elements together, then I get the total possible number of combinations: 2*3*4 = 24  solutions.

But when you have a whole wallet of coins to work with, you can see it might take a while to go through each and every solution. Is there any way that we could skip out answers that were obviously not going to give our goal total? Yes, by using conditional terminals on the for loops. This is where it is favourable that our middle loop contains the smallest denomination - you know that if you meet or exceed the goal amount, there is no point adding more small change: just increment the next loop out and do the comparison again.

The last thing to do is to preallocate some arrays for your answers if you wish (dynamically growing arrays = bad). My code is available here - open up the 'nested loops.vi' solution in the project.

But Leah, you say, incrementing quantities by 1 at a time must be really slow. Well, I've actually found this method to be faster than a more complex algorithm. I can get all 2184 answers to the original question within 0.47 seconds if I don't output my progress, and 0.31 seconds if I don't record all of the combos - both much quicker than the other answers I looked at. My laptop is nothing special, so I bet it runs faster on other machines.

So, how could this answer be improved? You'd notice that it isn't written in a very scalable or parameterised way - if you wanted to add in a £50 note, you'd have to add an extra for loop into the code. In my next post, I'll write about how to get round this with our friend recursion - a method that I can usually seldom find opportunities to use!