Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

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

In reply to Re^4: Mark Jason Dominus And Me - The Partition Problem by Tommy
in thread Mark Jason Dominus And Me - The Partition Problem by Tommy

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others romping around the Monastery: (3)
    As of 2014-10-02 01:32 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      What is your favourite meta-syntactic variable name?














      Results (41 votes), past polls