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;
####
^ ( 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 )
##
##
^ (1{7})* (?!1{7}) (1{5})* (?!1{5}) (1{1})* (?!1{1})
##
##
(?{ $x = $^R }) x
##
##
^ ( (1{1}|1{5}|1{7}) (?{ $^R+1 }) )*
(?(?{ $^R < $x }) $ | x )