Today, let me demonstrate and comment my solutions to the Perl Weekly Challenge tasks from Week 073.
Min Sliding Window
You are given an array of integers @a and 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)
For this task, there exists a very useful building block in Raku: the rotor routine. When it gets a Pair as its argument, it produces overlapping lists from the given data. For our example case, we need the series of three elements:
@a.rotor(3 => -2);
Here, 3 is the width of the window and -2 is the overlapping distance. This is what you get for the example input:
((1 5 0) (5 0 2) (0 2 9) (2 9 3) (9 3 7) (3 7 6) (7 6 4) (6 4 8))
It is a Sequence of Lists. There is nothing left as to apply the min routine to it. The whole program looks like this:
my @a = 1, 5, 0, 2, 9, 3, 7, 6, 4, 8; my $s = 3; .min.say for @a.rotor($s => 1 - $s);
The output for the given input values is:
$ raku ch-1.raku 0 0 0 2 3 3 4 4
Smallest Neighbour
You are given an array of integers @a. Write a script to create an array that represents the smaller element to the left of each corresponding index. If none found then use 0.
The examples reveal a tiny nuance that you may miss from the description.
Example
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] is none, so we put 0.
- For index 1, the smallest number to the left of @a[1] in (7), is 7 so we put 7.
- For index 2, the smallest number to the left of @a[2] in (7, 8) is none, so we put 0.
- For index 3, the smallest number to the left of @a[3] in (7, 8, 3) is 3, so we put 3.
- For index 4, the smallest number to the left of @a[4] is (7, 8, 3, 12) is 3, so we put 3 again.
Notice that for the third element, which is 3, the elements on the left are 7 and 8, and the element itself is smaller than both of them. So you need to print 0 and not the minimum of 7 an 8. So, 7 is an incorrect result here.
Here is the possible one-liner solution:
my @a = 7, 8, 3, 12, 10; say @a[$_] < min(@a[^$_]) ?? 0 !! min(@a[^$_]) for ^@a;
It prints the desired output:
$ raku ch-2.raku 0 7 0 3 3
This solution works but is not that efficient as it can be, as min is not only called twice for the same element, but it is computed many times for each items on the left side of the current position.
Here is a better solution in terms of O.
my @a = 7, 8, 3, 12, 10;
my $min = Inf;
for @a -> $v {
say $v < $min ?? 0 !! $min;
$min = $v if $v < $min;
}
There output is the same.
→ GitHub repository
→ Navigation to the Raku challenges post series