use strict;
use warnings;
use re 'eval';

my @denoms = (10, 6, 5, 1);
my $expr = join '', map "((?:$_)*)", map '1' x $_, @denoms;

print "E=$expr\n";

sub greedy_change {
    my $change = shift;
    my $coin_count = 0;
    my @combo;
    $_ = ('1' x $change);
print "Trying to change $change with @denoms...\n";
print "$expr on $_\n";
    if (
    m{^$expr$
      (?{
print "Code doesn't get run after once.\n";
        my @lengths = ($+[1]);
        my $new_count = 0;
        $lengths[$_] = $+[$_+1] - $+[$_] for 1..$#denoms;
        $new_count += $lengths[$_]/$denoms[$_] for 0..$#denoms;
        if (!$coin_count or $new_count < $coin_count) {
            print "$change: $new_count is better than $coin_count\n";
            $coin_count = $new_count;
            @combo = @lengths;
        }
      })
    }x) {
        print "Matched!\n";
    }
    if ($coin_count) {
        print "C=$coin_count\n";
    }
    else {
        print "No matching combination found\n";
    }
    @combo;
}

for my $num (12, 14, 36) {
    my @change = greedy_change($num);
    print "$num: @change\n";
}
[download]