Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re^3: Golf: Buying with exact change

by fergal (Chaplain)
on Feb 22, 2005 at 07:15 UTC ( #433274=note: print w/ replies, xml ) Need Help??


in reply to Re^2: Golf: Buying with exact change
in thread Golf: Buying with exact change

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


Comment on Re^3: Golf: Buying with exact change
Re^4: Golf: Buying with exact change
by Anonymous Monk on Feb 22, 2005 at 09:12 UTC
    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.)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://433274]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (9)
As of 2015-07-06 08:17 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (70 votes), past polls