This is my response to the Perl Weekly Challenge #073.
@A and sliding window size $S.
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 - $S → 10 - 3 → 7).
#! /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.
#! /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.
@A.
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.
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.
#! /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.