in reply to puzzle: how many ways to make $100
arg, I've been working on the following (brute force regexp engine) solution for a while, but I can't get it to work. It finds some matches, then gives up. I suspect there's some kind of optimization in the regexp engine making it think it's done. I figured I'd post it in case someone else wants to tinker with it.
outputsuse strict; use warnings; use re 'eval'; #use re 'debug'; use Data::Dumper qw( Dumper ); my $amount = shift; my @bills = (1, 5, 10, 20, 50, 100); my $choices = join "\n ", map { "( .{$_} (?{ my \%r = \%{\$^R}; \$r{$_}++; +{ \%r + } }) )*" } @bills; my $regexp = qr/ ^ (?{ +{} }) $choices $ (?{ push(@matches, $^R) }) (?!) /x; print($regexp, "\n"); our @matches; ('.' x $amount) =~ $regexp; print(Dumper(\@matches));
It's missing>perl 546453.pl 20 (?x-ism: ^ (?{ +{} }) ( .{1} (?{ my %r = %{$^R}; $r{1}++; +{ %r } }) )* ( .{5} (?{ my %r = %{$^R}; $r{5}++; +{ %r } }) )* ( .{10} (?{ my %r = %{$^R}; $r{10}++; +{ %r } }) )* ( .{20} (?{ my %r = %{$^R}; $r{20}++; +{ %r } }) )* ( .{50} (?{ my %r = %{$^R}; $r{50}++; +{ %r } }) )* ( .{100} (?{ my %r = %{$^R}; $r{100}++; +{ %r } }) )* $ (?{ push(@matches, $^R) }) (?!) ) $VAR1 = [ { '1' => '20' }, { '1' => '15', '5' => '1' }, { '1' => '10', '5' => '2' }, { '1' => '10', '10' => '1' }, { '1' => '5', '5' => '3' } ];
{ '1' => '5', '5' => '2' '10' => '1' }, { '5' => '4' }, { '5' => '2' '10' => '1' }, { '10' => '2' }, { '20' => '1', },
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^2: puzzle: how many ways to make $100
by ivancho (Hermit) on Apr 29, 2006 at 16:28 UTC |
In Section
Seekers of Perl Wisdom