use re 'eval';
use Test::More 'no_plan';

sub greedy_is_optimal {
    my @coins     = @_;
    my $greedy    = join "", map { "( 1{$_} (?{ \$^R+1 }) )* (?!1{$_})" }
                             reverse @coins;
    my $one_coin  = join "|", map { "1{$_}" } @coins;

    for ( $coins[2]+2 .. $coins[-1]+$coins[-2]-1 ) {
        local $x;
        (1 x $_) =~ /  ^ $greedy (?{ $x = $^R }) x
                     | ^ ( ($one_coin) (?{ $^R+1 }) )*
                         (?(?{ $^R < $x }) $ | x )    /x
            and return 0;
    }
    return 1;
}

is greedy_is_optimal(1,5,10,25), 1;
is greedy_is_optimal(1,6,10,25), 0;
is greedy_is_optimal(1,5,7),     0;