Interesting little loop optimization exercise

[Dave Britten]

I stumbled across this earlier during some downtime:

http://i.imgur.com/E1kRdcv.jpg

Transcribed:

Quote:Liam has five coins.

Three of the coins add up to 30p.

Three of the coins add up to 40p.

All five coins add up to £1.

What are the coins that Liam has?

UK coins: 1p, 2p, 5p, 10p, 20p, 50p, £1, £2.

I came up with a valid solution pretty quickly messing around with some scratch paper, but wondered if there were more than one solution.

I did a relatively straight-forward GW-BASIC program on my 200LX, which has FOR loops nested 8 deep. Thanks to a few optimizations, it runs to completion in just 4.5 seconds. The C# version on my desktop is effectively instantaneous. I'll probably throw together a 48 version eventually. What interesting approaches can you guys come up with?

EDIT: Got the GW-BASIC version down to 3.2 sec. I imagine this should be pretty doable on anything that makes indirect addressing easy enough.

[Jim Horn]

Hmmm - just a bit of analysis eliminates some of the eight coins. The requirements that three add to 30 and three add to 40 eliminates as well, leaving the solution(s) by a few minutes thought. My programming skills would take longer to code that... (No, I don't want to give away the answer yet).

It will be fun to see the clever routines that others will find!

[Paul Dale]

Well, we can place an immediate restriction on some of the coins.

We cannot have £1 or £2 because they exceed the maximum value.

We must have exactly one 50p. There is only one way to make the £1 using five smaller valued coins (5 x 20p) but this cannot satisfy the three make 30p requirement.

We've now got four unknown coins.

Both the 1p and 2p can be excluded since we don't have enough coins to bring them to a multiple of 5p which is required to hope to get to the 50p remainder.

So we're down to needing four coins from the 5p, 10p and 20p set that total 50p and have two three element subsets that total 40p and 30p.

A 5p coin needs a pair and two coins to make the remaining 40p. The only solution here can't make the 40p in three coins requirement. Thus we can't have a 5p coin.

I think we're down to the unique solution without any searching or looping


Pauli

[Paul Dale]

(05-14-2015 08:27 PM)Dave Britten Wrote:  I did a relatively straight-forward GW-BASIC program on my 200LX, which has FOR loops nested 8 deep.

Why would you need more than five nested loops?


Pauli

[Dave Britten]

(05-15-2015 01:42 AM)Paul Dale Wrote:  

(05-14-2015 08:27 PM)Dave Britten Wrote:  I did a relatively straight-forward GW-BASIC program on my 200LX, which has FOR loops nested 8 deep.

Why would you need more than five nested loops?


Pauli

Five loops that step through the combinations of coins, then three loops inside that to look for sums of 30 and 40. Nothing too fancy, but it runs pretty quick with a bit of optimization.

[Katie Wasserman]

(05-15-2015 01:41 AM)Paul Dale Wrote:  Well, we can place an immediate restriction on some of the coins.
.....
I think we're down to the unique solution without any searching or looping

I did this similarly but didn't want to post too soon:


a+b+c+d+e = 100
- Since the sum of three of these must be 40, they must all be 20 or one must be 50.
- Since the sum of three of these must be 30, they can't all be 20, so there's one 50.
- Now a+b+c+d = 50, and the sum of three must be 30 so there must be at least one 20. and the sum of three must be 40 so there must be at least one 10.
- Now a+b = 20, which only has one solution.