http://www.perlmonks.org?node_id=407006

Here is my try to [solve] the puzzle

Heh, a fine example of Ken Thompson's adage "when in doubt, use brute force".

Your code does have the merit of being very straightforward to understand. If I had the tuits I would code up an iterator solution using the closure-as-odometer idiom, but the code would not be as clear.

A simple observation of your code is to note that many a time, the sum exceeds 100 way before you get down to the fifth inner loop. Therefore, exiting the loop early via last will save considerable amount of time:

```my \$cnt = 0;
for my \$f ( 0 .. 20 ) {
for my \$z ( 0 .. 10 ) {
last if \$f*5 + \$z*10 > 100;
for my \$zw ( 0 .. 5 ) {
last if \$f*5 + \$z*10 + \$zw*20 > 100;
for my \$fu ( 0 .. 2 ) {
last if \$f*5 + \$z*10 + \$zw*20 + \$fu*50 > 100;
for my \$hu ( 0 .. 1 ) {
\$cnt++ if \$f * 5 + \$z * 10 + \$zw * 20 + \$fu * 50 + \$hu * 100
+ == 100;
}
}
}
}
}
print \$cnt;

You could unconditionally increment a counter in the inner loop inside this code and yours, and compare how many less times my inner loop gets called.

- another intruder with the mooring of the heart of the Perl

Replies are listed 'Best First'.
Re^2: How to generate restricted partitions of an integer
by tachyon (Chancellor) on Nov 11, 2004 at 14:13 UTC
686 loops for yours. 8316 for the original. 197 for mine which uses a slightly more optimised fail fast.

46 for mine :-)

function calls, not loops though :-(

Updated was 67 but I moved an if and reduced it to 46