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

in thread Mark Jason Dominus And Me - The Partition Problem

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