Beefy Boxes and Bandwidth Generously Provided by pair Networks vroom
Do you know where your variables are?
 
PerlMonks  

Re^3: Mark Jason Dominus And Me - The Partition Problem

by tilly (Archbishop)
on Nov 13, 2012 at 14:56 UTC ( #1003634=note: print w/ replies, xml ) Need Help??


in reply to Re^2: Mark Jason Dominus And Me - The Partition Problem
in thread Mark Jason Dominus And Me - The Partition Problem

For 1 the trick is in the first recursive call. When we subtract the current treasure from the target, we want to find solutions that include the current treasure. However inside that call, we don't know about the existence of that current treasure on the inner call - that fact is implicit in the fact that the target is smaller, and it will only get added back to the solution after the inner call returns.

For 2 the answer is, "Whenever we have a problem that we don't know how to solve, which can be somehow reduced to simpler versions of the same problem." For Fibonacci, that means smaller $n. In the case of the directory walk, that means farther down the directory tree. In the case of the partition problem, simpler means "fewer treasures".


Comment on Re^3: Mark Jason Dominus And Me - The Partition Problem
Re^4: Mark Jason Dominus And Me - The Partition Problem
by Tommy (Chaplain) on Nov 19, 2012 at 22:25 UTC

    Ummm. Just doesn't make sense to me to try and hit a moving $target... pun intended. It makes a helluva lot more sense now that my target stays constant and my "share" is the only thing really changing (see code below).

    Thank you tilly for helping me understand why I didn't understand. That's when everything started making sense.

    NEW CODE

    This is how I would do it... (remove "print" statements after debugging done).

    #!/usr/bin/perl use strict; use warnings; my ( $target, @treasures, $calls ); $target = shift @ARGV || 7; @treasures = @ARGV; @treasures = ( 2, 3, 4, 5, 1 ) unless @treasures; sub find_share { my ( $trial_set, $avail_choices, $depth ) = @_; $depth ||= 0; $depth += 1; $calls++; my $ts_total = 0; $ts_total += $_ for @$trial_set; printf qq{%-8s Call %-5d Depth: %-5d Trial set: %-10s Remaining: %- +16s ... }, ( '-' x $depth ) . '>', $calls, $depth, "[ @$trial_set ]", "[ @$avail_choices ]"; print qq{Found solution: [ @$trial_set ] == $target\n\n} and return $trial_set if $ts_total == $target; print qq{Returning undef because trial set total $ts_total > $targe +t\n} and return undef if $ts_total > $target; print qq{Returning undef because no available choices remain } . qq{and $ts_total < $target\n} and return undef if @$avail_choices == 0; my ( @my_trial_set ) = @$trial_set; my ( @my_avail_choices ) = @$avail_choices; push @my_trial_set, shift @my_avail_choices; print qq{$ts_total < $target, so I put "$my_trial_set[-1]" } . qq{into the trial set, and now I'll recurse\n}; my $solution = find_share( \@my_trial_set, \@my_avail_choices, $dep +th ); print +( '-' x $depth ) . '>', qq(A recursive call at depth @{[ $depth + 1 ]} found that a solu +tion } ) . qq(of [ @$solution ] adds up to my target of $target at depth $d +epth\n) and return [ @$solution ] if $solution; print '-' x $depth, '> ', qq{Situation failed. Omitting treasure [ $my_trial_set[-1] ] an +d } . qq{backtracking to choices of [ @my_avail_choices ] at depth $de +pth\n\n}; pop @my_trial_set; return find_share( \@my_trial_set, \@my_avail_choices, $depth ); } print qq{Trying to hit target of $target...\n\n}; print <<__ANS__; Solution: [ @{ find_share( [], \@treasures ) || [ "no solution possibl +e" ] } ] __ANS__ exit; __END__ DING! That moment when... \ | / _---_ \ / \ / __ | | __ \ 8-8 / / \l_l/ \ === =u= ...the light comes on and you get it.

    OUTPUT

    Click "Download code" link to see the actual, pretty, wide-formatted text

    $ perl find_shares_myway_2.pl Trying to hit target of 7... -> Call 1 Depth: 1 Trial set: [ ] Remaining: [ 2 +3 4 5 1 ] ... 0 < 7, so I put "2" into the trial set, and now I'll + recurse --> Call 2 Depth: 2 Trial set: [ 2 ] Remaining: [ 3 +4 5 1 ] ... 2 < 7, so I put "3" into the trial set, and now I'll + recurse ---> Call 3 Depth: 3 Trial set: [ 2 3 ] Remaining: [ 4 +5 1 ] ... 5 < 7, so I put "4" into the trial set, and now I'll + recurse ----> Call 4 Depth: 4 Trial set: [ 2 3 4 ] Remaining: [ 5 +1 ] ... Returning undef because trial set total 9 > 7 ---> Situation failed. Omitting treasure [ 4 ] and backtracking to ch +oices of [ 5 1 ] at depth 3 ----> Call 5 Depth: 4 Trial set: [ 2 3 ] Remaining: [ 5 +1 ] ... 5 < 7, so I put "5" into the trial set, and now I'll + recurse -----> Call 6 Depth: 5 Trial set: [ 2 3 5 ] Remaining: [ 1 +] ... Returning undef because trial set total 10 > 7 ----> Situation failed. Omitting treasure [ 5 ] and backtracking to c +hoices of [ 1 ] at depth 4 -----> Call 7 Depth: 5 Trial set: [ 2 3 ] Remaining: [ 1 +] ... 5 < 7, so I put "1" into the trial set, and now I'll + recurse ------> Call 8 Depth: 6 Trial set: [ 2 3 1 ] Remaining: [ ] + ... Returning undef because no available choices remain +and 6 < 7 -----> Situation failed. Omitting treasure [ 1 ] and backtracking to +choices of [ ] at depth 5 ------> Call 9 Depth: 6 Trial set: [ 2 3 ] Remaining: [ ] + ... Returning undef because no available choices remain +and 5 < 7 --> Situation failed. Omitting treasure [ 3 ] and backtracking to cho +ices of [ 4 5 1 ] at depth 2 ---> Call 10 Depth: 3 Trial set: [ 2 ] Remaining: [ 4 +5 1 ] ... 2 < 7, so I put "4" into the trial set, and now I'll + recurse ----> Call 11 Depth: 4 Trial set: [ 2 4 ] Remaining: [ 5 +1 ] ... 6 < 7, so I put "5" into the trial set, and now I'll + recurse -----> Call 12 Depth: 5 Trial set: [ 2 4 5 ] Remaining: [ 1 +] ... Returning undef because trial set total 11 > 7 ----> Situation failed. Omitting treasure [ 5 ] and backtracking to c +hoices of [ 1 ] at depth 4 -----> Call 13 Depth: 5 Trial set: [ 2 4 ] Remaining: [ 1 +] ... 6 < 7, so I put "1" into the trial set, and now I'll + recurse ------> Call 14 Depth: 6 Trial set: [ 2 4 1 ] Remaining: [ ] + ... Found solution: [ 2 4 1 ] == 7 ----->A recursive call at depth 6 found that a solution } of [ 2 4 1 ] + adds up to my target of 7 at depth 5 --->A recursive call at depth 4 found that a solution } of [ 2 4 1 ] a +dds up to my target of 7 at depth 3 ->A recursive call at depth 2 found that a solution } of [ 2 4 1 ] add +s up to my target of 7 at depth 1 Solution: [ 2 4 1 ]
    --
    Tommy
    $ perl -MMIME::Base64 -e 'print decode_base64 "YWNlQHRvbW15YnV0bGVyLm1lCg=="'

      INTERESTING!

      Maybe it doesn't hurt to program the way your brain really thinks...at least not this time. You see, I stripped down the MJD code to its barest form, exactly from the book. Then I removed the print statements from my own version which was just shared in the node previous to this node.

      Surprise: despite the fact that I'm passing around a reference to my "$share" with each call, my code benches twice as fast. I'm betting it's because I'm not constantly recalculating the "$target".

      Anyway, here's the benchmarks. I wonder what conclusions could be drawn. If I cared more, I'd run it through Devel::NYTprof and find out what's really going on and why it's faster to do it the way that makes the most sense to my dyslexic brain:

      $ perl ./find_shares_myway_2.pl Benchmark: timing 500000 iterations of test1... test1: 16 wallclock secs (15.43 usr + 0.00 sys = 15.43 CPU) @ 32 +404.41/s (n=500000) $VAR1 = { 'test1' => bless( [ 16, '15.43', 0, 0, 0, 500000 ], 'Benchmark' ) }; $ perl ./find_shares.pl Benchmark: timing 500000 iterations of test1... test1: 31 wallclock secs (30.10 usr + 0.02 sys = 30.12 CPU) @ 16 +600.27/s (n=500000) $VAR1 = { 'test1' => bless( [ 31, '30.1', '0.02', 0, 0, 500000 ], 'Benchmark' ) };
      --
      Tommy
      $ perl -MMIME::Base64 -e 'print decode_base64 "YWNlQHRvbW15YnV0bGVyLm1lCg=="'

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (6)
As of 2014-04-20 17:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (485 votes), past polls