Re: The greedy change-making problem using regexes

[Anonymous Monk]

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;
}