Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: The greedy change-making problem using regexes

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


in reply to The greedy change-making problem using regexes

Here are two subs which solve the make change problem using regexes. First one is the greedy algorithm, second one is the best change. Both subs take as first argument the amount to make change for, then a list of denominations. First sub uses 'pure' regexes, second sub uses a code fragment.

sub greedy_change { my $change = shift; my @coins = sort {$b <=> $a} @_; my $re; $re .= sprintf '((?:%s)*)', '1' x $_ for @coins; if (my @chunks = ('1' x $change) =~ /$re/) { return map {length($chunks[$_])/$coins[$_]} 0 .. $#coins; } else { return; } } sub best_change { my $change = shift; my @coins = sort {$b <=> $a} @_; our $S = $change + 1; our @C = (); my $re; $re .= sprintf '((?:%s)*)', '1' x $_ for @coins; $re .= '$(?{my @c = map {length($$_)/$coins[$_-1]} 1 .. @coins; my $s = 0; $s += $_ for @c; if ($s < $S) {$S = $s; @C = @c}})'; $re .= '(?!)'; use re 'eval'; ('1' x $change) =~ /^$re/; @C; }


Comment on Re: The greedy change-making problem using regexes
Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (6)
As of 2014-07-30 03:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (229 votes), past polls