Interesting little loop optimization exercise

05142015, 08:27 PM
(This post was last modified: 05142015 08:37 PM by Dave Britten.)
Post: #1




Interesting little loop optimization exercise
I stumbled across this earlier during some downtime:
http://i.imgur.com/E1kRdcv.jpg Transcribed: Quote:Liam has five coins. 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 straightforward GWBASIC 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 GWBASIC version down to 3.2 sec. I imagine this should be pretty doable on anything that makes indirect addressing easy enough. 

05152015, 01:10 AM
Post: #2




RE: Interesting little loop optimization exercise
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! 

05152015, 01:41 AM
Post: #3




RE: Interesting little loop optimization exercise
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 

05152015, 01:42 AM
Post: #4




RE: Interesting little loop optimization exercise  
05152015, 02:29 AM
Post: #5




RE: Interesting little loop optimization exercise
(05152015 01:42 AM)Paul Dale Wrote:(05142015 08:27 PM)Dave Britten Wrote: I did a relatively straightforward GWBASIC program on my 200LX, which has FOR loops nested 8 deep. 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. 

05152015, 01:09 PM
(This post was last modified: 05152015 01:09 PM by Katie Wasserman.)
Post: #6




RE: Interesting little loop optimization exercise
(05152015 01:41 AM)Paul Dale Wrote: Well, we can place an immediate restriction on some of the coins. 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. katie 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)