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.

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.

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 ]

Replies are listed 'Best First'. | |
---|---|

Re^5: Mark Jason Dominus And Me - The Partition Problem by Tommy (Chaplain) on Nov 19, 2012 at 23:27 UTC |

In Section
Meditations

Comment onRe^4: Mark Jason Dominus And Me - The Partition ProblemSelectorDownloadCode