Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

Comment on

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

I've been reading Mark Jason Dominus' "Higher Order Perl", and I really like it. It's certainly helping me to open my mind to new ways of approaching problems.

...And speaking of problems, there's one that MJD presents in the book which he calls "The Partition Problem", where you have a random sequence of numbers (representing things of value, like currency amounts, scoops of ice cream, or "treasures") and you need to figure out how to evenly divide them (or in some cases to hit a target number, or "fair share"). Basically you are looking at the numbers to find out what numbers add up to the target "fair share". In some code examples for this problem, the "fair share" target is hard coded, and in others it is 1/2 the total sum of all the numbers. Both code examples in this meditation will work either way.

MJD approaches the partition problem with some smart recursion. The issue I face is that his recursion is smarter than me; it just makes no damn sense. Well, to be fair, I spent several hours with it attempting to understand it better, but now it just makes damn little sense. Sure, it's an improvement, but the problem here, at least for me, is that the approach to the problem is something I can't visualize. If I can't see it mapped out in my mind, I can't really grasp it completely; I want to see what the code is doing, and understand the flow of execution.

In an attempt to make sense of the logic, I took MJD's example code and added things to it that would output some visual queues to help me understand where/when/how the code was diving through recursions and what was being returned, and in what order, back up the stack. As part of this meditation, I'll include my example code and some example output.

In a further attempt to make sense MJD's approach to the Partition Problem I decided to take some things I learned from his code and teachings in the book, and then write my own solution from scratch in a way that makes sense to me. I will also include that code here as well.

The issue upon which I meditate is that I remain disappointed that after having read, pondered, and customized MJD's code, and thereafter having written some code of my own which solves the same partition problem, I still don't completely understand MJD's code and why it works. (This isn't a happy meditation).

Code samples follow below. You can read the exact code from MJD's "Higher Order Perl" book for free online at http://hop.perl.plover.com/book/. It starts on page 35.

As for the code I'm providing, please be forewarned that it isn't the most beautiful, but by definition of the word "most", most code isn't. (Meditate on that :smirk:)

MJD's Approach, Modified

Here is the MJD code, modified to provide visual output that explains what the code is doing

#!/usr/bin/perl use strict; use warnings; my ( $target, @treasures, $calls ); $target = 5; @treasures = ( 50, 2, 4, 3, 1, 2, 4, 8 ); sub find_share { my ( $target, $treasures, $share, $depth ) = @_; $depth ||= 0; $depth += 1; $share ||= []; $calls++; printf qq{%-8s Calls: %-5d Depth: %-5d Share: %-10s Target: %-5d Tr +easures: %-16s ... }, ( '-' x $depth ) . '>', $calls, $depth, "[ @$share ]", $target, "[ @$treasures ]"; print qq{Returning "[]" because target == 0\n\n} and return [] if $target == 0; print qq{Returning undef because target < 0\n\n} and return undef if $target < 0; print qq{Returning undef because no treasures remaining\n\n} and return undef if @$treasures == 0; my ( $first, @rest ) = @$treasures; print qq(Putting "$first" into the share, leaving treasures [ @rest + ]\n\n); my $solution = find_share( $target - $first, \@rest, [ @$share, $fi +rst ], $depth ); print qq(A recursive call at depth @{[ $depth + 1 ]} found that a s +olution of [ @{[$first,@$solution]} ] adds up to my target of $target + at depth $depth\n\n) and return [ $first, @$solution ] if $solution; print '-' x $depth, '> ', qq{Situation failed. Couldn't hit target. Omitting treasure [ +$first ] and backtracking to target of $target, treasures [ @rest ] a +t depth $depth\n\n}; return find_share( $target, \@rest, $share, $depth ); } print qq<Solution: @{ find_share( $target, \@treasures ) }>; exit;

...And its output (it's quite a "wide-angle" view):

-> Calls: 1 Depth: 1 Share: [ ] Target: 5 Tre +asures: [ 50 2 4 3 1 2 4 8 ] ... Putting "50" into the share, leaving + treasures [ 2 4 3 1 2 4 8 ] --> Calls: 2 Depth: 2 Share: [ 50 ] Target: -45 Tre +asures: [ 2 4 3 1 2 4 8 ] ... Returning undef because target < 0 -> Situation failed. Couldn't hit target. Omitting treasure [ 50 ] a +nd backtracking to target of 5, treasures [ 2 4 3 1 2 4 8 ] at depth +1 --> Calls: 3 Depth: 2 Share: [ ] Target: 5 Tre +asures: [ 2 4 3 1 2 4 8 ] ... Putting "2" into the share, leaving tre +asures [ 4 3 1 2 4 8 ] ---> Calls: 4 Depth: 3 Share: [ 2 ] Target: 3 Tre +asures: [ 4 3 1 2 4 8 ] ... Putting "4" into the share, leaving trea +sures [ 3 1 2 4 8 ] ----> Calls: 5 Depth: 4 Share: [ 2 4 ] Target: -1 Tre +asures: [ 3 1 2 4 8 ] ... Returning undef because target < 0 ---> Situation failed. Couldn't hit target. Omitting treasure [ 4 ] +and backtracking to target of 3, treasures [ 3 1 2 4 8 ] at depth 3 ----> Calls: 6 Depth: 4 Share: [ 2 ] Target: 3 Tre +asures: [ 3 1 2 4 8 ] ... Putting "3" into the share, leaving trea +sures [ 1 2 4 8 ] -----> Calls: 7 Depth: 5 Share: [ 2 3 ] Target: 0 Tre +asures: [ 1 2 4 8 ] ... Returning "[]" because target == 0 A recursive call at depth 5 found that a solution of [ 3 ] adds up to +my target of 3 at depth 4 A recursive call at depth 3 found that a solution of [ 2 3 ] adds up t +o my target of 5 at depth 2 Solution: 2 3

And Now My Approach to the Partition Problem

This code makes vastly more sense to me, and reflects the way my brain thinks, to a certain degree. I wish to continue meditating on MJD's code until I can understand it on a much better level, even to the point that I understand this code below:

#!/usr/bin/perl use strict; use warnings; my ( $target, @treasures, $calls ); $target = 5; @treasures = ( 50, 2, 4, 3, 1, 2, 4, 8 ); print "Looking for numbers that add up to target: $target...\n"; print <<__OUT__; Solution: @{ try_treasures( \@treasures, $target ) || 'none?' } Calls: $calls __OUT__ sub try_treasures { my ( $treasures, $target ) = @_; my @legit_treasures = grep { $_ <= $target } @$treasures; # save so +me cycles # try each number, with all others for ( my $i = 0; $i < @legit_treasures; $i++ ) { my $add_this = $legit_treasures[ $i ]; my @to_these = @legit_treasures; splice @to_these, $i, 1; # every number except the one we're wor +king with my $attempt = try_bucket( [], $target, [ $add_this, @to_these ] +); return $attempt if $attempt; # when everything adds up perfectly + in sequence for ( my $j = 0; $j < @to_these; $j++ ) # ...when everything doe +s not { my @try_without = @to_these; # start trying combinations of numbers while sequentially omi +tting # ones that didn't work before splice @try_without, $j, 1; my $attempt = try_bucket( [], $target, [ $add_this, @try_with +out ] ); return $attempt if $attempt; } } } sub try_bucket { $calls++; my ( $bucket, $target, $choices ) = @_; return undef unless @$choices; push @$bucket, shift @$choices; # calculate sum of all numbers in the bucket, unless there's only o +ne my $bucket_sum = @$bucket == 1 ? $bucket->[0] : add_these( @$bucket + ); if ( $bucket_sum == $target ) { return $bucket; } elsif ( $bucket_sum < $target ) { return try_bucket( $bucket, $target, $choices ); } } sub add_these { my @add_these = @_; my $total = 0; print qq(Adding up [ @{[ join ' + ', @add_these ]} ] = ); for my $this_one ( @add_these ) { $total += $this_one } print qq{$total\n}; return $total; }

...And its output as well (not as complicated)

Looking for numbers that add up to target: 5... Adding up [ 2 + 4 ] = 6 Adding up [ 2 + 3 ] = 5 Solution: 2 3 Calls: 4
--
Tommy
$ perl -MMIME::Base64 -e 'print decode_base64 "YWNlQHRvbW15YnV0bGVyLm1lCg=="'

In reply to 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 browsing the Monastery: (3)
    As of 2014-07-26 14:44 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      My favorite superfluous repetitious redundant duplicative phrase is:









      Results (178 votes), past polls