Perl Monk, Perl Meditation PerlMonks

### Re: puzzle: how many ways to make \$100

by ikegami (Pope)
 on Apr 29, 2006 at 02:30 UTC ( #546453=note: print w/replies, xml ) Need Help??

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));
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'
}
];
It's missing
```          {
'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
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;
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
}
];

Create A New User
Node Status?
node history
Node Type: note [id://546453]
help
Chatterbox?

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (9)
As of 2018-05-25 08:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (182 votes). Check out past polls.

Notices?