Open the Window Just a Little Bit so Your Smallest Smaller Neighbor Can Get In

Wherein the least we can do becomes the most important thing, and looking backwards it seems it always has been

THE WEEKLY CHALLENGE – PERL & RAKU #73

---

TASK #1 › Min Sliding Window

Submitted by: Mohammad S Anwar

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)

Method

The essence of the task here is to take an array of numbers and look at it a little differently, as a collection of sub-arrays, in much the same way we can look inside a string as a collection of substrings. The “window” specified is a sub-array of length S whose lower boundary element starts at given index. By iterating over the indices, we can examine each window in turn, in this case to determine which of the elements is the smallest.

This idea of looking at only a subset of the elements in an array is a integral aspect of the array data structure itself, in both Perl and Raku. It has its own notation and name, an array slice. An array slice, given an arbitrary sequence of indices, will reference the original array in that given order. The index sequence can be described by constants, variables, arrays or ranges, or any combination thereof. An array slice can even be assigned to as an lvalue, selectively altering individual elements of the original array. Using array slices allows us to construct the “windows” of the given size in a few short strokes. The smallest index of the first window will start at 0, and the largest index of our last window will lie at the end of the array.

Perl Solution

In Perl 5, we can create our slices from an index by computing the range required by our given window size. We start at 0 and $S-1 for the lower and upper bounds of our first window, and increment upwards from there by one until the upper bound reaches the end of the array. Once we have our slice we’ll then hand it off to a minimum function, where, you guessed it, we’ll determine the minimum value for elements of the slice. We could just pull in the min function from the List::Util package, but why not roll our own? Maybe because List::Util is written in C and is way faster? Ok, that’s a pretty good reason, to be honest. But we’re still going to do it the hard way, by iterating through the list, comparing the found value to our current minimum and updating should we find a lower value. Because reasons, you know? Someday I will lend my primary focus on efficiency and speed, like I was, you know, tuning up a codebase or such. Today is not that day. Some days you just like to feel the texture of the bits between your fingers.

[colincrain:~/PWC]$  perl 73_1_open_the_window.pl 3 1 5 0 2 9 3 7 6 4 8
input:   1 5 0 2 9 3 7 6 4 8    window size 3
output:  0 0 0 2 3 3 4 4

use warnings;
use strict;
use feature ":5.26";

## ## ## ## ## MAIN:


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

$S = 3;
@A = (1, 5, 0, 2, 9, 3, 7, 6, 4, 8);

my $end = @A - $S;
my @output;

for ( 0..$end ){
    my $min = minimum( @A[$_..$_+$S-1] );
    push @output, $min;
}
say "@output";

## ## ## ## ## SUBS:

sub minimum {
    my $min = "inf";
    $_ < $min and $min = $_ for @_;
    return $min;
}

Raku Solution

Raku greatly expands on our ability to dissect and directly manipulate collections of array elements, providing a rotor method that will automatically partition our input array according to a defining rule. In this case we are selecting segments of length S, with a skip backwards from the end of each segment of S-1 elements. Thus the start of each selection moves forward one element per iteration until we reach the end of the array with our last complete selection. This returns a list of overlapping windows of length S, each incrementing the selected indices by one. Mapping the min function over this list then produces our output.

, unit sub MAIN (Int $S where $S > 0 = 3, *@A );

## default array
@A = 1, 5, 0, 2, 9, 3, 7, 6, 4, 8 if @A.elems == 0;


my @windows = @A.rotor($S=>-$S+1);
my @output = @windows.map( *.min );


## output phase
say "input:   ", @A, "    window size $S";
say "windows: ", |@windows;
put "output:  ", @output;

---

TASK #2 › Smallest Neighbour

Submitted by: Mohammad S Anwar

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]      
    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.

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] 
    in (4) is 4, so we put 4.
For index 2, the smallest number to the left of $A[2] 
    in (4, 6) is 4, so we put 4 again.

Method

“Smallest Neighbor” is a somewhat misleading title for this challenge, as we are not in fact looking for the smallest element to the left of a given index, but rather the smallest element to the left of the index that is smaller than that element.

m ∈ A |m = ⊥ {A[0], A[1], … , A[n-1]} , m < A[n]

Or stated another way, the minimum value of the slice $A[0..$i-1] that is itself less than $A[$i].

When we put it like that the challenge really resembles the previous, only in this case the size of the window is dynamic and there is some additional comparison going on. But the process is very similar: iterate acrosss the field, selecting a slice for each index, and determine the minimum value within that slice. Instead of just taking the minimum value, though, we can add some additional processing when we hand over the partition.

As 0 is a real value that is right in the middle of the potential range (as negative values are not disallowed), using it to label a target miss could be a bit confusing. With that in mind i have taken the liberty to substitute the null set sign ‘∅’ instead, which looks a lot like ‘0’ in my preferred coding font, but isn’t; doing this makes understanding what’s happening just a little bit easier. There’s no computation involved with this value and it is simply assigned, so what we choose to use can be 0, ∅, or really pretty much anything.

Perl Solution

As there are never any elements to the left of index 0, the first element will always be ∅ and hence can be inserted from the get-go. After that, starting at index 1, the slice from 0 to the current index is passed to our smallest_neighbor() function, where the indexed value is immediately popped off the end. The minimum of the remaining slice is found, and if that value is less than the index value it is returned, else ∅. There is no need to make more than one pass to prefilter the list, as the minimum will still be the minimum no matter its value.

[colincrain:~/PWC]$  perl 73_2_smallest_smaller_neighbor.pl 
Input:  7 8 -3 12 -10
Output: ∅, 7, ∅, -3, ∅

use warnings;
use strict;
use feature ":5.26";

## ## ## ## ## MAIN:

my @input = @ARGV;
@input = (7, 8, -3, 12, -10);
my @output = ('∅');

for (1..@input-1) {
    my @slice = @input[0..$_];
    my $smallest = smallest_neighbor( @slice );
    push @output, $smallest;
}

say "@input";
say join ', ', @output;

## ## ## ## ## SUBS:

sub smallest_neighbor {
## find the minimum value to the left and return it if 
## min < given value, else ∅
    my $value = pop @_;
    my $min   = "inf";
    $_ < $min and $min = $_ for @_;
    $min < $value ? $min : '∅';
}

Raku Solution

In Raku again we have a much expanded variety of ways to directly manipulate collections of array elements, so instead of taking slices we can directly create the sublists to be examined as required. To do this we will apply the “triangular comma”, a metaoperator combining produce (as <\>) with the <,> list constructor operator. This produces a list of lists, each with one more element of the original array appended. Which, incidentally, is exactly what we need. Well almost, because each element is a list, rather than an array. By coercing it as such before we hand it off to our smallest_neighbor() sub we can then pop off the rightmost value and compute the output from there, using min and a comparison check to see whether the value of the minimum is less than the last element.

unit sub MAIN () ;

my @input = (7, 8, -3, 12, -10);
my @output;

for [\,] @input  {                 ## triangular produce operator
    push @output, smallest_neighbor( $_.Array );     # $_ is List
}

sub smallest_neighbor( @slice ) {
## find the minimum value to the left of last value not inclusive
## return it if less than last, else ∅
    my $val = @slice.pop;
    my $min = @slice.min;
    $min < $val ?? $min !! '∅';
}

@input .put;
@output.put;