Missing pennies

Weekly Challenge 201

Challenge, My solution

Task 1: Missing Numbers

Task

You are given an array of unique numbers.

Write a script to find out all missing numbers in the range 0..$n where $n is the array size.

My solution

This is a one liner in Python, giving the list n, the solution I provided is:

missing = [i for i in range(len(n)+1) if i not in n]

Breaking it down into parts:

• range(len(n)+1) is the range from 0 to the length of the array (inclusive).
• this is called in a for loop, with each iteration given the value i.
• the if i not in n part of the clause will only return numbers NOT in the original array n.
• the i after the opening bracket will return that value.

For the Perl code, I took a different approach given that it does not support for ... if or the in keyword. The first thing I do is convert @n an array, to %n a hash with the map function. Then I run this code:

@missing = grep { !exists( $n{$_} ) } ( 0 .. $#n + 1 );

Like with the Python code ( 0 .. $#n + 1 ) is the range from 0 to to the length of the array (inclusive). The grep function iterates through the list, setting $_ as the current value. The exists function checks to see if that value exists in a hash.

Examples

$ ./ch-1.py 0 1 3
2

$ ./ch-1.py 0 1
2

Task 2: Penny Piles

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 of ascending heights from left to right.

My solution

Pennies were removed from circulation in New Zealand (my birth country) in 1967, well before I was born. Even 1¢ coins were removed when I was a kid.

Let me start off by acknowledging that the answer for the most efficient solution is probably already in OEIS. In previous tasks I've occasionally looked at producing the most efficient solution. Not today.

This time I'm solving the solution as it is described, and with yet another recursive function. The good thing is we don't care about what the combinations are, just how many there are.

For this solution my recursive function is called pile, and takes two inputs, the remaining pennies, and the minimum number I can take. The first call to the function in the input number, and a minimum of 1 penny.

For each call, I loop from the minimum value to the remaining pennies. If the two values are the same, we have found a solution. If there are coins left over, I call the pile function again, with the remaining coins and the coins I took (i.e. the new minimum). The return of each call is the number of solutions found.

Examples

$ ./ch-2.py 5
7

$ ./ch-2.py 50
204226