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;

##</code><code>##

    ^ ( 1{7} (?{ $^R+1 }) )* (?!1{7})
      ( 1{5} (?{ $^R+1 }) )* (?!1{5})
      ( 1{1} (?{ $^R+1 }) )* (?!1{1})
      (?{ $x = $^R }) x
  | ^ ( (1{1}|1{5}|1{7}) (?{ $^R+1 }) )*
      (?(?{ $^R < $x }) $ | x )

##</code><code>##

 ^ (1{7})* (?!1{7}) (1{5})* (?!1{5}) (1{1})* (?!1{1})

##</code><code>##

(?{ $x = $^R }) x

##</code><code>##

 ^ ( (1{1}|1{5}|1{7}) (?{ $^R+1 }) )* 
   (?(?{ $^R < $x }) $ | x )