Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
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 surveying the Monastery: (11)
As of 2014-09-01 13:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite cookbook is:










    Results (10 votes), past polls