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