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.

Replies are listed 'Best First'.
Re^2: Golf: Buying with exact change
by blokhead (Monsignor) on Feb 22, 2005 at 06:35 UTC
    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 }

    [download]
    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.

    blokhead

[reply]
[d/l]
      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.

[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]
Re^2: Golf: Buying with exact change
by BrowserUk (Patriarch) on Feb 22, 2005 at 07:37 UTC

    The first one I tried was 1,2,3--still waiting:)

    Examine what is said, not who speaks.
    Silence betokens consent.
    Love the truth but pardon error.
[reply]
[d/l]

In Section Meditations