Sliding Neighbour with Raku & Perl

by Arne Sommer

Sliding Neighbour with Raku & Perl

[87] Published 14. August 2020. Updated 17. august.

This is my response to the Perl Weekly Challenge #073.

Challenge #073.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)

We need an outer loop over the starting positions of the sliding windows, as indicated here:

[(1 5 0) 2 9 3 7 6 4 8] = Min (0)
...
[1 5 0 2 9 3 7 (6 4 8)] = Min (4)

The starting position is 0. The last one is the length of the list, with the size of the window subtracted. E.g. in the example given, the last position is 7 (@A.elems - $S10 - 37).

File: min-sliding-window-plain
#! /usr/bin/env raku

unit sub MAIN (Int $S where * >= 1, *@A);  # [1]

say "(",                                   # [2]
    (0 .. @A.elems - $S).map({ @A[$_ .. $_ + $S -1].min }).join(", "),
    # [3] ############# # [4] ############################ # [5] ####
    ")";                                   # [2]

[1] The $S value comes first, and we ensure that the value is of the right type. The rest is a slurp array, holding the array. Note the missing validation on the values.

[2] Print the result as a list, manually. So we have to do the starting and ending parens ourselves.

[3] I have used map instead of a for loop as it is shorter (and cooler). We iterate over the start indices of the sliding window, as explained above.

[4] For each start index, get the sliding window (an array slice), and extract the lowest value in that list (with min).

[5] The result is a list. Print the values comma separated.

See docs.raku.org/routine/min for more information about min.

Running it (and note that the first argument is the $S value):

$ ./min-sliding-window-plain 3 1 5 0 2 9 3 7 6 4 8
(0, 0, 0, 2, 3, 3, 4, 4)

That looks reasonable.

But we really should add verbose mode to make it easier to see what is going on:

File: min-sliding-window
#! /usr/bin/env raku

unit sub MAIN (Int $S where * >= 1, *@A, :v(:$verbose));

die "Integers only" unless all(@A) ~~ Int;  # [1]

(0 .. @A.elems - $S).map({                  # [2]
  say ": (" ~
      @A[$_ .. $_ + $S -1].join(", ") ~
      ") min -> " ~
      @A[$_ .. $_ + $S -1].min
}) if $verbose;

say "(",
     (0 .. @A.elems - $S).map({ @A[$_ .. $_ + $S -1].min }).join(", "),  # [x]
    ")";

[1] Validate the content of the array. The values should be integers.

[2] The normal way of using map is to collect the values returned by it, as done by [x]. But here we silently ignore the return value, as the say statement inside the block does the job.

Running it with verbose mode:

$ ./min-sliding-window -v 3 1 5 0 2 9 3 7 6 4 8
: (1, 5, 0) min -> 0
: (5, 0, 2) min -> 0
: (0, 2, 9) min -> 0
: (2, 9, 3) min -> 2
: (9, 3, 7) min -> 3
: (3, 7, 6) min -> 3
: (7, 6, 4) min -> 4
: (6, 4, 8) min -> 4
(0, 0, 0, 2, 3, 3, 4, 4)

Any non-integer value stops the program:

./min-sliding-window -v 3 -1 5 0 2 9 3 7 6 4 8.1
Integers only
  in sub MAIN at ./min-sliding-window line 5

It is indeed correct.

A Perl Version

This is pretty much a straight forward translation from the Raku version:

File: min-sliding-window-perl
#! /usr/bin/env perl

use strict;
use feature 'say';
use Getopt::Long;
use List::Util 'min';
use Perl6::Junction 'all';

my $verbose = 0;

GetOptions("verbose"  => \$verbose);

die 'Specify $S and @A' unless @ARGV;

my ($S, @A) = @ARGV;

die '$S must be an integer >= 1' unless int($S) == $S && $S >= 1;
die '@A must contain integers only' unless all(@A) == qr/^\d+$/;

map { say ": (" .
          join(", ", @A[$_ .. $_ + $S -1]) .
          ") min -> " .
          min @A[$_ .. $_ + $S -1]
} (0 .. @A - $S) if $verbose;

say "(",
    join (", ", map { min @A[$_ .. $_ + $S -1] } (0 .. @A - $S)),
    ")";

Running it:

#! /usr/bin/env perl
$ ./min-sliding-window-perl 3 1 5 0 2 9 3 7 6 4 8
(0, 0, 0, 2, 3, 3, 4, 4)

$ ./min-sliding-window-perl -v 3 1 5 0 2 9 3 7 6 4 8
: (1, 5, 0) min -> 0
: (5, 0, 2) min -> 0
: (0, 2, 9) min -> 0
: (2, 9, 3) min -> 2
: (9, 3, 7) min -> 3
: (3, 7, 6) min -> 3
: (7, 6, 4) min -> 4
: (6, 4, 8) min -> 4
(0, 0, 0, 2, 3, 3, 4, 4)

Looking good.

Challenge #073.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.

The text marked with red was added to the challenge as clarification later on.

This program was written before this clarification:

File: smallest-neighbour-first
#! /usr/bin/env raku

unit sub MAIN (*@A where @A.elems > 0 && all(@A) ~~ Int, :v(:$verbose));

if $verbose
{
  say "index 0 -> () -> 0";
  (1 .. @A.end)
    .map({ say ": index $_ -> (" ~
       @A[0 .. $_ -1].join(", ") ~ ") -> " ~
       @A[0 .. $_ -1].min });
}

say "(0, ", (1 .. @A.end).map({ @A[0 .. $_ -1].min }).join(", "), ")";
#### [1] ### [2] ######## # [3] ############## # [4] # [5] ########## 

[1] The first value is always zero.

[2] Iterate over the following values (the indices).

[3] Get the values to the left of the index.

[4] Get the lowest of them.

[5] Print all the lowest values as a comma separated list.

Running it:

$ ./smallest-neighbour-first 7 8 3 12 10
(0, 7, 7, 3, 3)

Note the incorrect third value; 7 instead of the 0 given in the challenge.

The second example works out ok:

$ ./smallest-neighbour-first 4 6 5
(0, 4, 4)

But back to the first one. Verbose mode to the rescue:

$ ./smallest-neighbourr-first -v 7 8 3 12 10
index 0 -> () -> 0
: index 1 -> (7) -> 7
: index 2 -> (7, 8) -> 7
: index 3 -> (7, 8, 3) -> 3
: index 4 -> (7, 8, 3, 12) -> 3
(0, 7, 7, 3, 3)

[This and the next section was rewritten 17. August 2020] That looked ok to me, so I contacted Mohammad and got an email with clarification, in addition to the changes mentioned above. I quote: «For you convenience, the comparison is done between the current index element against everything to the left of the current index. If you find an element less than the current index element you pick the smallest element otherwise you put 0.»

A bettwer wording would be: the smallest number to the left of the index must be lower than the value of the number found at the index, or we use 0.

This can be expressed like this, in the revised program with verbose mode:

$ ./smallest-neighbour -v 7 8 3 12 10
: index 0 (7) -> () -> 0
: index 1 (8) -> (7) -> 7
: index 2 (3) -> (7, 8) -> 0
: index 3 (12) -> (7, 8, 3) -> 3
: index 4 (10) -> (7, 8, 3, 12) -> 3
(0, 7, 0, 3, 3)

The revised program:

File: smallest-neighbour
#! /usr/bin/env raku

unit sub MAIN (*@A where @A.elems > 0 && all(@A) ~~ Int, :v(:$verbose));

if $verbose
{
  say ": index 0 (@A[0]) -> () -> 0";
  (1 .. @A.end).map({ say ": index $_ (@A[$_]) -> ("
    ~ @A[0 .. $_ -1].join(", ") ~ ") -> "
    ~ (@A[0 .. $_ -1].min < @A[$_] ?? @A[0 .. $_ -1].min !! 0 )
  })
}

say "(0, ",
    (1 .. @A.end).map({ my $c = @A[0 .. $_ -1].min;
    $c < @A[$_] ?? $c !! 0 }).join(", "), ")";  # [1]

[1] If the minimum value is lower than the value found at the given index (@A[$_]), use zero instead of the minimum value. Note the use of a variable, so that we can avoid finding the minimum value twice.

A Perl Version

This is pretty much a straight forward translation from the Raku version:

File: smallest-neighbour-perl
#! /usr/bin/env perl

use strict;
use feature 'say';
use Getopt::Long;
use List::Util 'min';
use Perl6::Junction 'all';

my $verbose = 0;

GetOptions("verbose"  => \$verbose);

die 'Specify @A' unless @ARGV;

my (@A) = @ARGV;

die '@A must contain integers only' unless all(@A) == qr/^\d+$/;

if ($verbose)
{
  say ": index 0 (" . $A[0] . ") -> () -> 0";
  map { say ": index $_ ($A[$_]) -> (" . join(", ", @A[0 .. $_ -1]) . ") -> "
   .   (min @A[0 .. $_ -1] < $A[$_] ? min @A[0 .. $_ -1] : 0 ) } (1 .. @A -1);
}

say "(0, ",
  join (", ",
      map { my $c = min @A[0 .. $_ -1]; $c < $A[$_] ? $c : 0 } (1 .. @A -1)),
     ")";

Running it gives the exact same result as the Raku version (smallest-neighbour):

$ ./smallest-neighbour-perl 7 8 3 12 10
(0, 7, 0, 3, 3)

$ ./smallest-neighbour-perl -v 7 8 3 12 10
: index 0 (7) -> () -> 0
: index 1 (8) -> (7) -> 7
: index 2 (3) -> (7, 8) -> 0
: index 3 (12) -> (7, 8, 3) -> 3
: index 4 (10) -> (7, 8, 3, 12) -> 0
(0, 7, 0, 3, 3)

$ ./smallest-neighbour-perl 4 6 5
(0, 4, 4)

$ ./smallest-neighbour-perl -v 4 6 5
: index 0 (4) -> () -> 0
: index 1 (6) -> (4) -> 4
: index 2 (5) -> (4, 6) -> 0
(0, 4, 4)

And that's it.