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

[Tommy]

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 ]