Task — Piles of pennies

We are given an integer, $n > 0, and asked to write a script to determine the number of ways of putting $n pennies in a row of piles such that each pile contains no fewer pennies than the one on its left.

Analysis

Having given this some thought I decided to start with the rightmost, ie largest, stack and work backwards creating more, ever smaller stacks till I run out of pennies.

This is one of those tasks where recursion works well. Let's define a subroutine find_ways($pennies, $height). Each time we call it, $pennies is the number of pennies we have still not stacked, and $height is the maximum height of the next stack.

So we're going to start with find_ways($n, $n), because we start with $n pennies and clearly the maximum height is also $n when all the pennies are in a single stack.

The essence of find_ways is just this:

for $h (1..($pennies > $height ? $height : $pennies)) {
    find_ways($pennies - $h, $h);
}

What we're doing here is trying all the possible heights ($h) for the next stack from 1 up to the smaller of $pennies and $height. It can't be more than $pennies, because that's all we've got and it can't be more than height or it would be higher than the stack on its right.

What happens when we run out of pennies? If that happens, find_ways will be called with $pennies == 0, and we have to trap that before we so the loop shown above. The trap looks like this:

if ($pennies == 0) {
    $ways ++;
    return;
}

If you look at my script you'll see that I have slightly complicated it so as to return the lists of piles as well as the number of ways the piles can be created.

Try it 

#!/usr/bin/perl

# Peter Campbell Smith - 2023-01-23
# PWC 201 task 2

use v5.28;
use utf8;
use warnings;

# Task: You are given an integer, $n > 0. Write a script to determine the number of ways of putting $n 
# pennies in a row of piles such that each pile contains no fewer pennies than the one on its left.

# Blog: https://pjcs-pwc.blogspot.com/2023/01/201-missing-numbers-and-piles-of-pennies.html

my (@tests, $n, $ways, $piles);

@tests = (1, 2, 3, 4, 5, 20);

# loop over tests
for $n (@tests) {
    
    # initialise
    $ways = 0;
    $piles = '';
    
    # find possible ways to do it
    find_ways($n, $n, '');
    
    # output results
    say qq[Input:  \$n = $n\nOutput: ] . $ways;
    say qq[Piles:\n$piles];
}   

sub find_ways {
    
    # returns the number of possible ways of stacking $pennies pennies in stacks no more than $height
    my ($pennies, $height, $stack) = @_;
    my ($h);

    # no pennies left - answer found
    if ($pennies == 0) {
        $piles .= qq[$stack\n];
        $stack = '';
        $ways ++;
        return;
    }
    
    # loop over possible piles
    for $h (1 .. ($pennies > $height ? $height : $pennies)) {
        find_ways($pennies - $h, $h, qq[$h $stack]);
    }
}

Output

Input:  $n = 1
Output: 1
Piles:
1

Input:  $n = 2
Output: 2
Piles:
1 1
2

Input:  $n = 3
Output: 3
Piles:
1 1 1
1 2
3

Input:  $n = 4
Output: 5
Piles:
1 1 1 1
1 1 2
2 2
1 3
4

Input:  $n = 5
Output: 7
Piles:
1 1 1 1 1
1 1 1 2
1 2 2
1 1 3
2 3
1 4
5