RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved an array search and a mathematical classic. (Note that this is open until 29 January 2023.)

Task 1: Missing Numbers

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.

The examples both assume an integer return, i.e. there's a single missing number, so that's what I wrote – more specifically the lowest missing number. Otherwise I'd have used a grep, filter, find_all, etc., returning an array.

(How could it be multiple if the numbers are unique? [100, 101, 102] would return [0, 1, 2, 3].)

Ruby:

def missingnumber(l)
  v = Set.new(l)
  0.upto(l.length) do |i|
    if !v.include?(i) then
      return i
    end
  end
  return 0
end

Task 2: Penny Piles

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.

This is in fact the partition function, the number of distinct additive partitions of the input number, which is A000041 in the OEIS. Not rating myself with Ramanujan, I borrowed and converted some SAGE (now SageMath) code from that page (originally by Peter Luschny).

(Except in Perl, since there I allow myself Math::Prime::Util which includes its own implementation.)

Raku:

sub pennypiles($n) {
    if ($n == 0) {
        return 1;
    }
    my $s = 0;
    my $j = $n - 1;
    my $k = 2;
    while ($j >= 0) {
        my $t = pennypiles($j);
        if (($k div 2) % 2 == 1) {
            $s += $t;
        } else {
            $s -= $t;
        }
        if ($k % 2 == 1) {
            $j -= $k;
        } else {
            $j -= ($k div 2);
        }
        $k++;
    }
    return $s;
}

Full code on github.