Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Perl, please do my math homework

by whakka (Hermit)
on Oct 18, 2009 at 05:17 UTC ( #801833=CUFP: print w/ replies, xml ) Need Help??

In the course of my math class in the engineering program I'm currently in it's often convenient to write up little programs that perform some calculation based on a function or algorithm. However, oftentimes a reasonable program makes calculations in a different way than humans might, and it becomes a challenge to parse the print statements I insert into the code to "show my work."

Well I finally decided to get around this problem after reading about inlining eval's in regular expressions while reading the Camel in a compromising position recently and faced with a particularly laborious exercise in my latest assignment:

Find the number of partitions of 7 and 8 using the formula for the number of partitions of a number (all possible combinations of adding smaller positive integers):

P(m,n) = { 1 if m or n = 1, P(m,m) if m < n, 1 + P(m,m-1) if m = n > 1, P(m,n-1) + P(m-n,n) if m > n > 1 }
My first attempt was straightforward:
sub partition { my ( $m, $n ) = @_; die "bad inputs" if $m <= 0 or $n <= 0; print "P($m,$n) = "; if ( $m == 1 or $n == 1 ) { say 1; return 1; } if ( $m < $n ) { say "P($m,$m)"; return partition( $m, $m ); } if ( $m == $n ) { say "1 + P($m,", $m - 1, ")"; return 1 + partition( $m, $m - 1 ); } if ( $m > $n ) { say "P($m,", $n - 1, ") + P(", $m - $n, ",$n)"; return partition( $m, $n - 1 ) + partition( $m - $n, $n ); } die "impossible!"; } MAIN: { my ( $m, $n ) = @ARGV; $n ||= $m; say partition( $m, $n ); }

The output to this program though is actually harder to put together than doing the problem manually! The recursion is depth-first and so the program goes straight to the bottom of each branch, and yet it's more natural to evaluate one level at a time and combine. Fortunately, Perl rocks my world:

sub P { # Returns strings! my ( $m, $n ) = @_; if ( $m == 1 or $n == 1 ) { return 1; } if ( $m < $n ) { return "P($m,$m)"; } if ( $m == $n ) { return sprintf( "1 + P(%i,%i)", $m, $m - 1 ); } if ( $m > $n ) { return sprintf( "P(%i,%i) + P(%i,%i)", $m, $n - 1, $m - $n, $n + ); } die "impossible!"; } MAIN: { local $_ = "P($m,$n)"; print; while ( /\D/ ) { # Put ints up front 1 while s/^(.+\)) \+ (\d+)/$2 + $1/; # Add the ints 1 while s/(\d+) \+ (\d+)/$1 + $2/eg; # Evaluate *one* level at a time s/(P\(\d+,\d+\))/$1/eeg; printf( "\n = %s", $_ ); } }

And the output looks like:

$ partition.pl 7 P(7,7) = 1 + P(7,6) = 1 + P(7,5) + P(1,6) = 1 + P(7,4) + P(2,5) + 1 = 2 + P(7,3) + P(3,4) + P(2,2) = 2 + P(7,2) + P(4,3) + P(3,3) + 1 + P(2,1) = 3 + P(7,1) + P(5,2) + P(4,2) + P(1,3) + 1 + P(3,2) + 1 = 5 + 1 + P(5,1) + P(3,2) + P(4,1) + P(2,2) + 1 + P(3,1) + P(1,2) = 7 + 1 + P(3,1) + P(1,2) + 1 + 1 + P(2,1) + 1 + 1 = 12 + 1 + 1 + 1 = 15
Beautiful! Copied straight to the notebook.

Update: For those interested in efficient solutions to this and other integer partition problems, Limbic~Region has this post.

Comment on Perl, please do my math homework
Select or Download Code
Re: Perl, please do my math homework
by omouse (Initiate) on Nov 15, 2009 at 06:44 UTC
    You should learn Common Lisp. It has this neat function/macro called TRACE that will automatically show the input of every call to whatever function you're tracing. Everytime I've debugged recursive functions I've used it.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: CUFP [id://801833]
Approved by planetscape
Front-paged by planetscape
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (13)
As of 2014-12-22 16:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (121 votes), past polls