laurent_r

These are some answers to the Week 73 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few days from now (on Aug. 16, 2020). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 1: 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)

[(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)

Min Sliding Window in Raku

Not very much to comment. I’ve decided pass the size of the sliding window as an argument to the program (with a value defaulted to 3 if no argument is passed). Raku has a built-in min function which we can use on every sliding window. Otherwise, this task is a nice opportunity to use the gather ... take construct

use v6;

my @a = 1, 5, 0, 2, 9, 3, 7, 6, 4, 8;
my $s =  @*ARGS[0] // 3;

my @result = gather {
    for 0..@a.elems - $s  -> $i {
        take min @a[$i..^$i + $s];
    }
}
say @result;

This script duly outputs the correct result with the default value (3):

$ raku sliding.raku
[0 0 0 2 3 3 4 4]

The result is also fine when passing a parameter (5):

$ raku sliding.raku 5
[0 0 0 2 3 3]

Min Sliding Window in Perl

Perl doesn’t have a built-in min function. We would obviously use the min subroutine provided by the List::Util module, but, as usual, for a coding challenge, I don’t want to use a ready-made solution and prefer to show how this can be done “by hand” in pure Perl. Besides that, the program is quite similar to the Raku program, except that I replaced the use of the gather ... take construct by a simple push into the previously declared @result array:

use strict;
use warnings;
use feature qw/say/;

sub min {
    my $min = shift;
    for (@_) {
        $min = $_ if $_ < $min;
    }
    $min;
}

my @a = (1, 5, 0, 2, 9, 3, 7, 6, 4, 8);
my $s =  shift // 3;
my @result;
for my $i (0..@a - $s) {
    push @result, min @a[$i..$i + $s - 1];
}
say "@result";

This displays the correct results:

$ perl sliding.pl
0 0 0 2 3 3 4 4

$ perl sliding.pl 5
0 0 0 2 3 3

Task #2: Smallest Neighbor

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.

Note that what we are supposed to do is not clear when the smallest element to the left is equal to the current element. I’ll consider that the smallest element to the left has to be strictly less than the current element. Choosing the other interpretation would be a minor change to the code anyway.

Smallest Neighbor in Raku

I don’t want to recompute every time the minimum element of an ever-increasing list, so I prefer to maintain a $min variable to keep track of the smallest item seen so far during the loop overt the input array. Also, rather than having to deal with an edge case for the first element, I decided to pre-populate the @result array with 0 (the first item of the resulting list is always bound to be 0), to assign the first input item to $min and t remove it from the input array.

use v6;

my @a = 7, 8, 3, 12, 10;
my @result = 0,;
my $min = shift @a;
for @a -> $item {
    if $item < $min {
        push @result, 0;
        $min = $item;
    } else {
        push @result, $min;
    }
}
say @result;

This displays the following output:

$ raku smallest_n.raku
[0 7 0 3 3]

Smallest Neighbor in Perl

This is a straight port to Perl of the Raku program above:

use strict;
use warnings;
use feature qw/say/;

my @a = (7, 8, 3, 12, 10);
my @result = (0);
my $min = shift @a;
for my $item (@a) {
    if ($item < $min) {
        push @result, 0;
        $min = $item;
    } else {
        push @result, $min;
    }
}
say "@result";

This displays the following output:

$ perl smallest_n.pl
0 7 0 3 3

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, August 23, 2020. And, please, also spread the word about the Perl Weekly Challenge if you can.