Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
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', },


Comment on Re: puzzle: how many ways to make $100
Select or Download Code
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 } ];

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://546453]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (8)
As of 2014-12-25 01:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (159 votes), past polls