Re^2: Golf: Buying with exact change

[blokhead]

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 smart-ass 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.

[fergal]

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?

Read more... (2 kB)

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.

[fergal]

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

[Anonymous Monk]

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.)