Perl Weekly Challenge: Week 73
Challenge 1:
Min Sliding Window
You are given an array of integers
@Aand sliding window size$S.Write a script to create an array of min from each sliding window.
Example
Input: @A = (1, 5, 0, 2, 9, 3, 7, 6, 4, 8) and $S = 3
Output: (0, 0, 0, 2, 3, 3, 4, 4)
[(1 5 0) 2 9 3 7 6 4 8] = Min (0)
[1 (5 0 2) 9 3 7 6 4 8] = Min (0)
[1 5 (0 2 9) 3 7 6 4 8] = Min (0)
[1 5 0 (2 9 3) 7 6 4 8] = Min (2)
[1 5 0 2 (9 3 7) 6 4 8] = Min (3)
[1 5 0 2 9 (3 7 6) 4 8] = Min (3)
[1 5 0 2 9 3 (7 6 4) 8] = Min (4)
[1 5 0 2 9 3 7 (6 4 8)] = Min (4)
I'll start with Raku.
It's very simple, all we need to do is to repeatedly take a slice of @A consisting of $S elements
moving forward one element forward each time until we get to the (array length) - $Sth element. In
each slice, we get the smallest element using the .min() method and push it into an array. When the loop
is done, we print out that array.
my @output;
for (0 .. @A.elems - $S) -> $i {
@output.push(@A[$i ..^ $i + $S].min);
}
@output.join(q{ }).say;
The same algorithm is used for Perl. The only complication is that there is no built in min() so we have to roll our own like this:
sub min {
my @A = @{ $_[0] };
my $least = $A[0];
for my $i (1 .. scalar @A - 1) {
if ($A[$i] < $least) {
$least = $A[$i];
}
}
return $least;
}
Challenge 2:
Smallest Neighbour
You are given an array of integers
@A.Write a script to create an array that represents the smallest element to the left of each corresponding index. If none found then use 0.
Example 1
Input: @A = (7, 8, 3, 12, 10)
Output: (0, 7, 0, 3, 3)
For index 0, the smallest number to the left of $A[0] i.e. 7 is none, so we put 0.
For index 1, the smallest number to the left of $A[1] as compare to 8, in (7) is 7 so we put 7.
For index 2, the smallest number to the left of $A[2] as compare to 3, in (7, 8) is none, so we put 0.
For index 3, the smallest number to the left of $A[3] as compare to 12, in (7, 8, 3) is 3, so we put 3.
For index 4, the smallest number to the left of $A[4] as compare to 10, in (7, 8, 3, 12) is 3, so we put 3 again.
Example 2
Input: @A = (4, 6, 5)
Output: (0, 4, 4)
For index 0, the smallest number to the left of $A[0] is none, so we put 0.
For index 1, the smallest number to the left of $A[1] as compare to 6, in (4) is 4, so we put 4.
For index 2, the smallest number to the left of $A[2] as compare to 5, in (4, 6) is 4, so we put 4 again.
Raku first again. And again, we are going through a loop and using the .min() method to find the smallest number
in an array slice. The difference to the first problem is that the size of the slice is not fixed but grows with each
iteration of the loop and we have to filter the slice to get only the elements smaller than the current element before we
can find the minimum. One thing I stumbled on is that .min() returns ∞ if the array slice is empty not Nil as I expected.
my @output;
for (0 ..^ @A.elems) -> $i {
my $lowest = @A[0 .. $i - 1].grep({ $_ < @A[$i]; }).min;
@output.push($lowest == ∞ ?? 0 !! $lowest);
}
@output.join(q{ }).say;
For comparison, this is the Perl version. I had to use the min() function from challenge 1 here too. Also, it should be noted
that my function returns the more sensible undef if the array passed to it is empty.
my @output;
for my $i (0 .. (scalar @A) - 1) {
my $lowest = min([ grep { $_ < $A[$i]; } @A[0 .. $i - 1] ]);
push @output, $lowest // 0;
}
say join q{ }, @output;