note
Tommy
<p>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).</p>
<p>Thank you [tilly] for helping me understand why I didn't understand. That's when everything started making sense.</p>
<h3>NEW CODE</h3>
<p>This is how I would do it... (remove "print" statements after debugging done).</p>
<code>
#!/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 > $target\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, $depth );
print +( '-' x $depth ) . '>',
qq(A recursive call at depth @{[ $depth + 1 ]} found that a solution } ) .
qq(of [ @$solution ] adds up to my target of $target at depth $depth\n)
and return [ @$solution ] if $solution;
print '-' x $depth, '> ',
qq{Situation failed. Omitting treasure [ $my_trial_set[-1] ] and } .
qq{backtracking to choices of [ @my_avail_choices ] at depth $depth\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 possible" ] } ]
__ANS__
exit;
__END__
DING! That moment when...
\ | /
_---_
\ / \ /
__ | | __
\ 8-8 /
/ \l_l/ \
===
=u=
...the light comes on and you get it.
</code>
<h3>OUTPUT</h3>
<p>Click "Download code" link to see the actual, pretty, wide-formatted text</p>
<code>
$ 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 choices 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 choices 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 choices 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 choices 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 ] adds up to my target of 7 at depth 3
->A recursive call at depth 2 found that a solution } of [ 2 4 1 ] adds up to my target of 7 at depth 1
Solution: [ 2 4 1 ]
</code>
<div class="pmsig"><div class="pmsig-222307">
--
<br />
[Tommy]<br />
<code>$ perl -MMIME::Base64 -e 'print decode_base64 "YWNlQHRvbW15YnV0bGVyLm1lCg=="'</code>
</div></div>
1003519
1003634