Weekly Challenge 201
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 valuei
.  the
if i not in n
part of the clause will only return numbers NOT in the original arrayn
.  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
$ ./ch1.py 0 1 3
2
$ ./ch1.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 remain
ing 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
$ ./ch2.py 5
7
$ ./ch2.py 50
204226
Top comments (0)