in reply to Re: Golf: Buying with exact change in thread Golf: Buying with exact change
I guess we disagree on what trivializing the problem means ;) I didn't mean to imply that all instances of the problem in fact do have solutions which are so small  that is clearly not true. My intent is that, if it helps you, your solution can solve a restricted but "reasonable" subset of instances (and to make things clear, define what restricted subset your solution is correct for, if you can). What is "reasonable?"
I basically want to rule out smartass solutions like this:
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.
Re^3: Golf: Buying with exact change by fergal (Chaplain) on Feb 22, 2005 at 09:16 UTC 
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^3: Golf: Buying with exact change by fergal (Chaplain) on Feb 22, 2005 at 07:15 UTC 
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] 
