This is my response to The Weekly Challenge #201.
0..$n where
$n is the array size.
Input: @array = (0,1,3)
Output: 2
The array size i.e. total element count is 3, so the range is 0..3.
The missing number is 2 in the given array.
Input: @array = (0,1)
Output: 2
The array size is 2, therefore the range is 0..2.
The missing number is 2.
The challenge prescribes «numbers», which include non-integers. But thankfully, only integers are reported as missing in the examples. I deduce that the input values should also be constrained to integers.
Negative integers should also be excluded, as the range starts at zero.
If we assume that all the numbers are in the given range, i.e. only one value is missing - as in the examples, we can get away with this:
File: missing-numbers-wrong
#! /usr/bin/env raku
unit sub MAIN (*@array where @array.elems
&& all(@array) ~~ /^<[0..9]>*$/, # [1]
:v(:$verbose));
my $n = @array.elems; # [2]
my @sorted = @array.sort; # [3]
for ^$n -> $i # [4]
{
say ": $i -> @sorted[$i]" if $verbose;
unless @sorted[$i] == $i # [5]
{
say $i; # [5a]
exit; # [5b]
}
}
say $n; # [6]
[1] At least one element, and they must be non-negative integers only.
[2] The number of elements.
[3] Sort them, as that makes the lookup easier.
[4] Iterate over the numbers/indices.
[5] The number should be same at the index. If not, we have found the missing value [5a] and are done [5b].
[6] If the loop did not find it, the very last value is missing.
Running it:
$ ./missing-numbers-wrong 0 1 3
2
$ ./missing-numbers-wrong 0 1
2
With verbose mode:
$ ./missing-numbers-wrong -v 0 1 3
: 0 -> 0
: 1 -> 1
: 2 -> 3
2
$ ./missing-numbers-wrong -v 0 1
: 0 -> 0
: 1 -> 1
2
Let us see what happens if we ignore the assumption that all the numbers are in the given range:
$ ./missing-numbers-wrong -v 10
: 0 -> 10
0
$ ./missing-numbers-wrong -v 10 20
: 0 -> 10
0
$ ./missing-numbers-wrong -v 10 20 30
: 0 -> 10
0
Yes, well. If we were to make sunch as assumption, then the program should make sure that the input actually satisfies the assumption. (That is actually easy to fix, but the assumption is probably abolutely wrong.)
Here is an assumption-less program:
File: missing-numbers
#! /usr/bin/env raku
unit sub MAIN (*@array where @array.elems && all(@array) ~~ /^<[0..9]>*$/,
:v(:$verbose));
my $n = @array.elems;
my @sorted = @array.sort;
my @missing = (); # [1]
my $current = @sorted.shift; # [2]
for 0 .. $n -> $i # [3]
{
say ": Checking $i" if $verbose;
$current == $i # [4]
?? ( $current = @sorted.shift || next ) # [4a]
!! ( @missing.push: $i ); # [4b]
}
say @missing.join(","); # [5]
[1] The missing values, as there can be more than one, will end up here.
[2] The first value, ready for the loop.
[3] The loop. Iterate over the last value as well (the array length).
[4] Have we found the number? If yes, get ready for the next iteration (by setting
the next number we are to look for) [4a]. If not, add it to the array of missing
values. Note the ||next so that the program does not have a fit if we
try to shift a value from an empty array, which will happen if the missing value is
higher than the last one in the array. As is the case in the first example. The actual
code after || does not really matter, as the loop finishes by itself
anyway after doing this.
[5] Print the missing value(s). Note that we will have at least one missing value.
Running it gives the same result as the first program, on the examples (except for the verbose output):
$ ./missing-numbers -v 0 1
: Checking 0
: Checking 1
: Checking 2
2
$ ./missing-numbers -v 0 1 3
: Checking 0
: Checking 1
: Checking 2
: Checking 3
2
Values not in the range work out this time:
$ ./missing-numbers -v 10
: Checking 0
: Checking 1
0,1
$ ./missing-numbers -v 10 20
: Checking 0
: Checking 1
: Checking 2
0,1,2
$ ./missing-numbers -v 10 20 30
: Checking 0
: Checking 1
: Checking 2
: Checking 3
0,1,2,3
Yes!
$n > 0.
$n pennies
in a row of piles of ascending heights from left to right.
Input: $n = 5
Output: 7
Since $n=5, there are 7 ways of stacking 5 pennies in ascending piles:
1 1 1 1 1
1 1 1 2
1 2 2
1 1 3
2 3
1 4
5
Recursion is the thing here, because recursion is the thing here...
File: penny-piles
#! /usr/bin/env raku
unit sub MAIN (UInt $n, :v(:$verbose)); # [1]
my $piles := gather # [2]
{
recurse( (), +$n); # [3]
}
sub recurse (@done, $todo) # [5]
{
if $todo == 0 # [6]
{
say ": @done[]" if $verbose;
take @done; # [6a]
return; # [6b]
}
for 1 .. $todo -> $i # [7]
{
last if @done && $i > @done.head; # [8]
my @next = @done.clone; # [9]
@next.unshift: $i; # [10]
recurse(@next, $todo - $i); # [11]
}
}
say $piles.elems; # [4]
[1] Ensure an unsigned integer with the UInt type.
[2] Using gather/take to set up
the sequence is ideal here, as we return values (with take) are returned
(so to speak) inside a recursive procedure - one at a time.
See my Raku Gather,
I Take article or
docs.raku.org/syntax/gather take for more information about
gather/take.
[3] The first argument is the list of values already done, and the second is the number of pennies still to be done. Note the rather unimaginative name of the recursive procedure.
[4] Print the number of piles.
[5] The recursive procedure.
[6] No more pennies to do? Return (with take) the piles [6a] and we are done
(i.e. return) [6b] with this recursion.
[7] Iterate over the number of pennies still to do.
[8] We skip the rest of the iterations if we have reached a number that is higher than the first one we have done - as this would violate the sorted clause. (Higher than, because we are going to add the new pile (value) at the front.
[9]
Note the use of clone to get a copy, so that when we
add an element (in [10]), we do it without clobbering up the global variable. Using
is copy in the procedure signature would not have helped here, as we add
elements several times to the same (unchanged) array.
See
docs.raku.org/routine/clone for
more information about the clone method.
See
docs.raku.org/type/Signature#index-entry-trait_is_copy
more information about is copy.
[10] Add the new value to the front of the array (with
unshift), so that we get the piles in the correct order.
See
docs.raku.org/routine/unshift
for more information about unshift.
[11] Recursively call ourselves.
Running it:
$ ./penny-piles 5
7
Running it with verbose mode is a good idea:
$ ./penny-piles -v 5
: 1 1 1 1 1
: 1 1 1 2
: 1 2 2
: 1 1 3
: 2 3
: 1 4
: 5
7
This program gives us a sequence, where the first 14 numbers are as follows
(given after the # ->):
$ ./penny-piles 1 # -> 1
$ ./penny-piles 2 # -> 2
$ ./penny-piles 3 # -> 3
$ ./penny-piles 4 # -> 5
$ ./penny-piles 5 # -> 7
$ ./penny-piles 6 # -> 11
$ ./penny-piles 7 # -> 15
$ ./penny-piles 8 # -> 22
$ ./penny-piles 9 # -> 30
$ ./penny-piles 10 # -> 42
$ ./penny-piles 11 # -> 56
$ ./penny-piles 12 # -> 77
$ ./penny-piles 13 # -> 101
$ ./penny-piles 14 # -> 135
Recognizing this sequence is pretty hard, but googling those 14 numbers did the trick. This is the Euler’s Partition Theorem. Also known as Sequence A000041, if you skip the first value in that sequence (as '41 has an extra 1 up front).
Euler is perhaps more famous for his Seven Bridges of Königsberg, which I paid homage to in my Seven Bridges to Raku five part article.
And the missing first value can actually be computed, if you want to:
$ ./penny-piles 0
1
This is how many ways we can put zero pennies in a row of piles. One (pun intended) can argue that 0 would be a better answer, though...
And that's it.