in reply to
Golf: Buying with exact change
That's very clever but you do appear to have chosen bounds that trivialise the problem. Try largest(1000, 1001, 1003) 100,000 isn't large enough, try 1,000,000 and then go make a cup of tea (actually you could probably grow a cup of tea in the time this will take)
Update Hmm.... the original did say not to worry about efficiency but it's not hard to produce examples with fairly small numbers that will run for years, maybe even centuries.
I've been waiting more than 7 minutes just to find out if 999999 is possible with largest(1000, 1001, 1002, 1003, 1004, 1005) and there's no sign of an answer yet.
Update again I killed it after 100 min of CPU time (1.7Ghz Pentium) and it still hadn't figured out if 999,999 was doable or not.
Re^2: Golf: Buying with exact change by blokhead (Monsignor) on Feb 22, 2005 at 06:35 UTC 
sub largest { 43 }
It works for largest(6,9,20), but one instance is a trivial subset of the problem space. Unreasonable.
The set of instances whose solutions are less than 1000.. 10000.. is that a "reasonable" subset? The idea is to find a concise algorithm to solve this particular problem, and to solve all these instances correctly, (a) you must actually carry out some sort of computation, and (b) your algorithm must probably be correct. To me, that's reasonable enough.
 [reply] [d/l] 

I'm justpointing out that the regex solution is terrible once the numbers start to get large. Efficiency is not the primary concern in golf but a soution should terminate before the sun dies :)
Another problem I have with the regex solution is that you don't know how much is enough for any given input. I'd say twice the largest 2 number would do it but I'm not sure, there will be complications when some of the numbers share factors.
It's an interesting puzzle though, it has a very simple solution when there's only 2 numbers:
largest(m, n) = (m  1) * (n  1)  1 
 [reply] 

Well, only if there is a solution. For instance, if you plug in 4 and 2 in your solution, you'll get 2 as an answer  but it's obvious you can pay 2 exactly. Note that for 2 numbers there is a (finite) answer if and only if the 2 numbers are relative prime. (Which is easy to see, if they aren't relative prime, they share a prime number p in their factors. Which means that any amount you can pay will be a multiple of p.)
 [reply] 

Here's a solution with no limits (beyond the memory used by memoize). It answers largest(1000, 1001, 1002, 1003, 1004, 1005) in 19 secs (the answer is 199,999 by the way). If you turn off memoize it takes much longer, although probably just days rather than centuries, It's based on a previous perlmonks challenge: How to generate restricted partitions of an integer.
It's definitely not golf! Is there a golfish answer that runs in similar time?
I'm going to bed now so I won't explain in detail. Hopefully someone will have posted a more golfish solution by the time I get to work tomorrow and I won't have to bother.
 [reply] [d/l] 
Re^2: Golf: Buying with exact change by BrowserUk (Pope) on Feb 22, 2005 at 07:37 UTC 
The first one I tried was 1,2,3still waiting:)
Examine what is said, not who speaks.
Silence betokens consent.
Love the truth but pardon error.
 [reply] [d/l] 

