Missing numbers and

piles of pennies

Weekly challenge 201 — 23 January 2023

Week 201 - 23 Jan 2023

Task 2

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.

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.

#!/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]); } }

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

The content of this website which has been created by

Peter Campbell Smith is hereby placed in the public domain

Peter Campbell Smith is hereby placed in the public domain