201: Missing numbers and piles of pennies

Missing numbers

Task: We are given an array of unique numbers and asked to write a script to find out all missing numbers in the range 0 .. $n where $n is the number of entries in the array.

Analysis: The first thing to note is that there will always be at least one missing number, as there are $n + 1 numbers in the range 0 .. $n and only $n entries in the array.

The easy way to do this task is to convert the array to a string:

$string = ',' . join(',', @$array) . ',';

The string will look something like this:

,1,2,3,4,5,6,

Now all we have to do is to loop $j over 0 to $n - 1 and:

$result .= qq[$j, ] unless $string =~ m|,$j,|;

and with a little tidying up of the format, we have the result requested.

My solution

Penny piles

Task: 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 solution 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.

My solution