http://qs321.pair.com?node_id=546453


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. 

use 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));

[download]
outputs 
>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'
          }
        ];

[download]
It's missing 
          {
            '1' => '5',
            '5' => '2'
            '10' => '1'
          },
          {
            '5' => '4'
          },
          {
            '5' => '2'
            '10' => '1'
          },
          {
            '10' => '2'
          },
          {
            '20' => '1',
          },

[download]

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
    yeah, first "*" never tries 0. (update: hmm, no, it does try, for 10.. then I don't know why..) But if you actually specify the max number of matches 
    my $choices = join "\n   ",
   map { "(  .{$_} (?{ my \%r = \%{\$^R}; \$r{$_}++; +{ \%r } })  ){0,
+".(int($amount/$_))."}" }
                   @bills;

    [download]
    it works fine: 
    12:28pm /home/Ivancho/bin> probichka.pl 20
(?x-ism:
   ^
   (?{ +{} })
   (  .{1} (?{ my %r = %{$^R}; $r{1}++; +{ %r } })  ){0,20}
   (  .{5} (?{ my %r = %{$^R}; $r{5}++; +{ %r } })  ){0,4}
   (  .{10} (?{ my %r = %{$^R}; $r{10}++; +{ %r } })  ){0,2}
   (  .{20} (?{ my %r = %{$^R}; $r{20}++; +{ %r } })  ){0,1}
   (  .{50} (?{ my %r = %{$^R}; $r{50}++; +{ %r } })  ){0,0}
   (  .{100} (?{ my %r = %{$^R}; $r{100}++; +{ %r } })  ){0,0}
   $
   (?{ push(@matches, $^R) })
   (?!)
)

$VAR1 = [
          {
            '1' => 20
          },
          {
            '1' => 15,
            '5' => 1
          },
          {
            '1' => 10,
            '5' => 2
          },
          {
            '1' => 10,
            '10' => 1
          },
          {
            '1' => 5,
            '5' => 3
          },
          {
            '1' => 5,
            '10' => 1,
            '5' => 1
          },
          {
            '5' => 4
          },
          {
            '10' => 1,
            '5' => 2
          },
          {
            '10' => 2
          },
          {
            '20' => 1
          }
        ];

    [download]
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom