Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re^2: The greedy change-making problem using regexes

by Anonymous Monk
on Mar 10, 2005 at 10:45 UTC ( #438204=note: print w/ replies, xml ) Need Help??


in reply to Re: The greedy change-making problem using regexes
in thread The greedy change-making problem using regexes

No need for code blocks, and it works very fast as well (as you'd expect from a greedy algorithm).

my $dime = '(?:' . ('1' x 10) . ')'; my $halfdozen = '(?:' . ('1' x 6) . ')'; my $nickel = '(?:' . ('1' x 5) . ')'; my $cent = '(?:' . ('1' x 1) . ')'; sub greedy_change { my $change = shift; my ($c10, $c6, $c5, $c1) = ('1' x $change) =~ /^($dime*)($halfdozen*)($nickel*)($cent*)$/; return (length ($c10 || "") / 10, length ($c6 || "") / 6, length ($c5 || "") / 5, length ($c1 || "") / 1); }


Comment on Re^2: The greedy change-making problem using regexes
Download Code
Replies are listed 'Best First'.
Re^3: The greedy change-making problem using regexes
by japhy (Canon) on Mar 10, 2005 at 12:32 UTC
    No, that doesn't work: it ends up using three coins (a dime and two pennies) for 12 cents, instead of two six-cent coins.
    _____________________________________________________
    Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
    How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart
      Which is the correct answer for the greedy algorithm. But see my posting elsewhere in this thread for a more general solution.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (8)
As of 2015-07-30 15:10 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 (271 votes), past polls