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

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);
}
[download]

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	[reply]
Re^4: The greedy change-making problem using regexes by Anonymous Monk on Mar 10, 2005 at 13:14 UTC
Which is the correct answer for the greedy algorithm. But see my posting elsewhere in this thread for a more general solution.	[reply]

In Section Meditations