Perl-Sensitive Sunglasses 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??

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

Replies are listed 'Best First'.
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

```\$ 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=="'

Create A New User
Node Status?
node history
Node Type: note [id://1003634]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (4)
As of 2017-12-16 00:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What programming language do you hate the most?

Results (447 votes). Check out past polls.

Notices?