Perl Weekly Challenge: Week 201
Challenge 1:
Missing Numbers
You are given an array of unique numbers.
Write a script to find out all missing numbers in the range
0..$nwhere$nis the array size.
Example 1
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.
Example 2
Input: @array = (0,1)
Output: 2
The array size is 2, therefore the range is 0..2.
The missing number is 2.
Basically, what we need to do here is compare the difference between two sets. One is
@array. The other is the range from 0 to the length of @array. We represent this
second set by the array @need.
my @need = 0 .. @array.elems;
Raku has operators for all the common operations on sets including difference. So we can just use ∖
to get the missing numbers. (Although the examples only have 1 missing number, there can be more.) I
ran into a little difficulty getting the proper return type for the set difference operator. Given that
both the operands are arrays, you would think that the result would be one too but actually it has to be a
scalar of type Set. Also because @array came from command line arguments, its' elements are strings so they
have to be coerced to Integers for a proper comparison to take place.
my Set $missing = @need ∖ @array.map({ $_.Int });
Once we have the missing number(s), all that remains is to print them out in a nicely formatted way.
$missing.keys.join(q{, }).say;
The Perl version starts out the same way...
my @need = 0 .. scalar @array;
...but Perl doesn't have a set intersection operator so we have to do it ourselves. Luckily, the Perl documentation in perlfaq4 shows us how. A hash is declared to count the occurrence of elements in each set with the element itself as the key.
my %count;
for my $elem (@array, @need) {
$count{$elem}++;
}
At the end, any key in %count with a value less than 2 represents an element which only exists in one of
the two sets. These are the missing numbers so we can format and print them.
say join(q{, }), grep { $count{$_} < 2; } keys %count;
Challenge 2:
Penny Piles
You are given an integer,
$n > 0.Write a script to determine the number of ways of putting
$n penniesin a row of piles of ascending heights from left to right.
Example
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
I freely admit to not being very good at maths. I did have a fleeting memory of dealing with this sort of problem in my Discrete Mathematics course at university long long ago. Brief consultation with my daughter Shailaja who is a Computer Science major at the moment confirmed it and that it is called the Integer Partition problem. While I was tempted to ask her to code it for me, that would be cheating (plus they only teach Python and Java at her college -- boooo!) so I decided I must try it myself. Unfortunately though there are many web pages on this topic, they mostly seem to assume you understand maths which as I mentioned I do not. Some rummaging around did produce here which has code in C++. Below is my attempt to convert it to Raku and Perl and understand what is actually happening.
The driver of the script looks like this:
say partitions($n).elems;
my partitions() function returns the actual partitions as an array of arrays but while useful for debugging
that wasn't really necessary as the spec says we only need the count of how many partitions were found.
This is partitions().
sub partitions(Int $n) {
First we allocate an array to store the partitions which are found.
my @combos;
Another array stores the partition we are currently working on which will be a series of piles.
my @piles;
This will represent the number of piles in the current partition.
my $i = 0;
In every partition we will always have one big pile of everything so we can go ahead and add it to @piles.
@piles[$i] = $n;
Now we go into an infinite loop:
loop {
We add the current partition into @combos.
@combos.push([@piles]);
Then we generate the next partition. $remainder is the number of pennies left to allocate.
my $remainder = 0;
while ($i >= 0 && @piles[$i] == 1) {
$remainder += @piles[$i];
$i--;
}
When the partion contains all 1's we can break out of the loop.
if ($i < 0) {
last;
}
We allocate pennies to piles in amounts starting from one less than the total number. (Because we already generated the partition which consists of one pile of all the pennies.)
@piles[$i]--;
$remainder++;
while ($remainder > @piles[$i]) {
@piles[$i + 1] = @piles[$i];
$remainder = $remainder - @piles[$i];
$i++;
}
When we no longer have enough pennies for a pile of that amount, we decrease the amount by 1 and try again.
@piles[$i + 1] = $remainder;
$i++;
}
After all partitions have been found, we return them.
return @combos;
}
This is the Perl version of partitions(). It is almost exactly the same as in Raku.
sub partitions {
my ($n) = @_;
my @combos;
my @piles;
my $i = 0;
$piles[$i] = $n;
while (1) {
push @combos, [@piles];
my $remainder = 0;
while ($i >= 0 && $piles[$i] == 1) {
$remainder += $piles[$i];
$i--;
}
if ($i < 0) {
last;
}
$piles[$i]--;
$remainder++;
while ($remainder > $piles[$i]) {
$piles[$i + 1] = $piles[$i];
$remainder = $remainder - $piles[$i];
$i++;
}
$piles[$i + 1] = $remainder;
$i++;
}
return @combos;
}