with Raku

This is my response to The Weekly Challenge #248.

You are given

Write a script to return an array of integers of size same as length of the given string such that:

`a string`

and `a character`

in the given
string.
Write a script to return an array of integers of size same as length of the given string such that:

- distance[i] is the distance from index i to the closest occurence of the given character in the given string.
- The distance between two indices i and j is abs(i - j).

Input: $str = "loveleetcode", $char = "e"
Output: (3,2,1,0,1,0,0,1,2,2,1,0)
The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance
is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance
is abs(1 - 3) = 2.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at
index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5)
= 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance
is abs(8 - 6) = 2.

Example 2:
Input: $str = "aaab", $char = "b"
Output: (3,2,1,0)

Let us do the *inelegant* solution first; with two passes.

#! /usr/bin/env raku
unit sub MAIN ($str = "loveleetcode", # [1]
$char where $char.chars == 1 = "e", # [1a]
:v(:$verbose));
my @input = $str.comb; # [2]
my @output; # [3]
my $distance = Inf; # [4]
for @input -> $i # [5]
{
$distance = 0 if $i eq $char; # [6]
@output.push: $distance; # [7]
$distance++; # [8]
}
say ":From left: ({ @output.join(",") })" if $verbose;
$distance = Inf; # [9]
for @input.end ... 0 -> $index # [10]
{
$distance = 0 if @input[$index] eq $char; # [11]
@output[$index] = $distance if $distance < @output[$index]; # [12]
$distance++; # [13]
}
say "({ @output.join(",") })"; # [14]

[1] First the string, with a default value. Then a single character, also with a default value [1a].

[2] Get the individual characters, as a list, with
`comb`

.

See docs.raku.org/routine/comb for more information about `comb`

.

[3] The output (distances) will end up here.

[4] The current distance. We are looking for the shortest,
and `Inf`

(infinity) is a suitable default error value when we have
not found it yet.

See docs.raku.org/type/Num#index-entry-Inf_(definition) for more information about the Infinity value `Inf`

.

[5] Iterate over the input characters, left to right. (This is the first pass.)

[6] Set the distance to zero, if we have the character we are looking for.

[7] Add the distance to the result. Note that `Inf`

will end up
here if we have not found the character. (But that is ok, as the
second pass will rectify that.)

[8] Increase the distance counter, ready for the next iteration.
Note that adding «1» to `Inf`

does not change that value. Any
other not-found-so-far value (e.g. «-1») would need special care
here.

[9] Reset the distance before the second pass.

[10] Iterate from right to left, this time over the indices as the output array exists 8and we are going to modify some of the values). (This is the second pass.)

[11] The same as [6].

[12] Update the distance in the output array, buy only if the new
distance is shorter than the old one. (It may be `Inf`

, so missing
distances work out beautifully).

[13] The same as [8].

[14] Pretty print the resulting distances.

Running it:

$ ./shortest-distance-leftright
(3,2,1,0,1,0,0,1,2,2,1,0)
$ ./shortest-distance-leftright loveleetcode e
(3,2,1,0,1,0,0,1,2,2,1,0)
$ ./shortest-distance-leftright aaab b
(3,2,1,0)

Looking good.

Specifying a character not in the string gives an infinitely interesting result, so to speak:

$ ./shortest-distance-leftright loveleetcode x
(Inf,Inf,Inf,Inf,Inf,Inf,Inf,Inf,Inf,Inf,Inf,Inf)

Verbose mode shows the intermediary result, after the first pass:

$ ./shortest-distance-leftright -v
:From left: (Inf,Inf,Inf,0,1,0,0,1,2,3,4,0)
(3,2,1,0,1,0,0,1,2,2,1,0)
$ ./shortest-distance-leftright -v aaab b
:From left: (Inf,Inf,Inf,0)
(3,2,1,0)

Then we can have a go at a single pass version.

File: shortest-distance#! /usr/bin/env raku
unit sub MAIN ($str = "loveleetcode",
$char where $char.chars == 1
&& $str.contains($char) = "e", # [1]
:v(:$verbose));
my @input = $str.comb;
my $end = @input.end;
my @output;
my @todo; # [2]
for 0 .. $end -> $index # [3]
{
if @input[$index] eq $char # [4]
{
@output[$index] = 0; # [5]
@todo.push: ($index, -1) if $index > 0; # [6]
@todo.push: ($index, +1) if $index < $end; # [7]
say ":Index: $index (match) -> zero" if $verbose;
}
}
while @todo # [8]
{
say ":Todo: { @todo.raku }" if $verbose;
my ($pos, $offset) = @todo.shift; # [9]
my $index = $pos + $offset; # [10]
if ! @output[$index].defined # [11]
{
@output[$index] = $offset.abs; # [12]
my $new-offset = $offset < 0 ?? $offset -1 !! $offset +1; # [13]
@todo.push: ($pos, $new-offset) if 0 <= $pos + $new-offset <= $end; # [14]
say ":Index:$index (from:$pos,$offset) -> { $offset.abs }" if $verbose;
}
elsif $verbose
{
say ":Index:$index (from:$pos,$offset) - already set" if $verbose;
}
}
say "({ @output.join(",") })";

[1] Ensure that the string `contains`

the
character.

See docs.raku.org/routine/contains for more information about `contains`

.

[2] A buffer (first in, first out) of steps to consider.

[3] Iterate over the indices.

[4] Have we found the specified character?

[5] If so, set the distance to zero in the output.

[6] And add the position to the **left** to the end of the buffer,
if the position exists.

[7] Ditto for the position on the **right**.

The buffer (or queue) has entries with two values. The
**first** is the original position (index) of the character we search
for. The **second** is the offset (to that index). We need this value
when we update the output, as it is the distance to the character
(albeit with a possible minus in front of it).

[8] As long as we have unfinished business.

[9] Get the first entry from the buffer.

[10] The index of the character we are currently inspecting.

[11] Do nothing if we already have a value in the output, as we then have a shorter distance (or possibly the same) already. Further work in the same direction will not reach positions without a shortest distance.

[12] Get the distance without the sign (if any) with
`abs`

.

See docs.raku.org/routine/abs for more information about `abs`

.

[13] Increase the offset with «1» (in the right direction) or «-1» (in the left direction).

[14] Add the new position to the buffer of it is within bounds.

It is possible to argue that this program is not really single pass (because of the loop in [3] in addition to the so-called single pass itself in [8]), and feel free to do just that...

Running it gives the same result as before:

$ ./shortest-distance loveleetcode e
(3,2,1,0,1,0,0,1,2,2,1,0)
$ ./shortest-distance aaab b
(3,2,1,0)

But verbose mode gives a quite different result:

$ ./shortest-distance -v loveleetcode e
:Index: 3 (match) -> zero
:Index: 5 (match) -> zero
:Index: 6 (match) -> zero
:Index: 11 (match) -> zero
:Todo: [(3, -1), (3, 1), (5, -1), (5, 1), (6, -1), (6, 1), (11, -1)]
:Index:2 (from:3,-1) -> 1
:Todo: [(3, 1), (5, -1), (5, 1), (6, -1), (6, 1), (11, -1), (3, -2)]
:Index:4 (from:3,1) -> 1
:Todo: [(5, -1), (5, 1), (6, -1), (6, 1), (11, -1), (3, -2), (3, 2)]
:Index:4 (from:5,-1) - already set (to:1)
:Todo: [(5, 1), (6, -1), (6, 1), (11, -1), (3, -2), (3, 2)]
:Index:6 (from:5,1) - already set (to:0)
:Todo: [(6, -1), (6, 1), (11, -1), (3, -2), (3, 2)]
:Index:5 (from:6,-1) - already set (to:0)
:Todo: [(6, 1), (11, -1), (3, -2), (3, 2)]
:Index:7 (from:6,1) -> 1
:Todo: [(11, -1), (3, -2), (3, 2), (6, 2)]
:Index:10 (from:11,-1) -> 1
:Todo: [(3, -2), (3, 2), (6, 2), (11, -2)]
:Index:1 (from:3,-2) -> 2
:Todo: [(3, 2), (6, 2), (11, -2), (3, -3)]
:Index:5 (from:3,2) - already set (to:0)
:Todo: [(6, 2), (11, -2), (3, -3)]
:Index:8 (from:6,2) -> 2
:Todo: [(11, -2), (3, -3), (6, 3)]
:Index:9 (from:11,-2) -> 2
:Todo: [(3, -3), (6, 3), (11, -3)]
:Index:0 (from:3,-3) -> 3
:Todo: [(6, 3), (11, -3)]
:Index:9 (from:6,3) - already set (to:2)
:Todo: [(11, -3),]
:Index:8 (from:11,-3) - already set (to:2)
(3,2,1,0,1,0,0,1,2,2,1,0)
$ ./shortest-distance -v aaab b
:Index: 3 (match) -> zero
:Todo: [(3, -1),]
:Index:2 (from:3,-1) -> 1
:Todo: [(3, -2),]
:Index:1 (from:3,-2) -> 2
:Todo: [(3, -3),]
:Index:0 (from:3,-3) -> 3
(3,2,1,0)

The «Todo» entries show the current buffer content. If you have not already gotten the idea; we take on step in each direction from the found characters until we reach an already computed distance. We take 1 step from each one, before the second steps, and so on.

Specifying a character not present in the string will now be catched, courtesy of the added code in [1]:

$ ./shortest-distance loveleetcode x
Usage:
./shortest-distance [-v|--verbose[=Any]] [<str>] [<char>]

Note that the first solution, though *inelegant*,
is probably the most efficient. It is shorter.

You are given a

Write a script to construct a

`NxM`

matrix `A`

of integers.
Write a script to construct a

`(N-1)x(M-1)`

matrix `B`

having elements that are the sum over the `2x2`

submatrices of
`A`

,
b[i,k] = a[i,k] + a[i,k+1] + a[i+1,k] + a[i+1,k+1]

Example 1:
Input: $a = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
]
Output: $b = [
[14, 18, 22],
[30, 34, 38]
]

Example 2:
Input: $a = [
[1, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1]
]
Output: $b = [
[2, 1, 0],
[1, 2, 1],
[0, 1, 2]
]

The code to specify a matrix on the command line (#1 and #2 below), has been used before, see e.g. Challenge #242.1: Missing Members in Missing Matrix with Raku.

File: submatrix-sum#! /usr/bin/env raku
unit sub MAIN (Str $matrix = "1 2 3 4 | 5 6 7 8 | 9 10 11 12", # [1]
:v(:$verbose));
my @a = $matrix.split("|")>>.words>>.Int>>.Array; # [2]
my $rows = @a.elems; # [3]
my $cols = @a[0].elems; # [4]
die "The rows must have the same size" unless [==] @a>>.elems; # [5]
die "Integers only" unless all(@a[*;*]) ~~ Int; # [6]
say ": Matrix: { @a.raku }" if $verbose;
my @b; # [7]
for 0 .. $rows -2 -> $r # [8]
{
for 0 .. $cols -2 -> $c # [9]
{
@b[$r][$c] = @a[$r][$c] + @a[$r][$c+1] +
@a[$r+1][$c] + @a[$r+1][$c+1]; # [10]
}
}
say "["; # [11]
@b.map({ say " [" ~ @_>>.join(", ") ~ "]" }); # [11a]
say "]"; # [11b]

[1] The default matrix, and also an example of how to specify it on the command line.

[2] Get the matrix. Note the `>>.Int`

part in the middle
that gets rid of the `Str`

types we get courtesy of
`words`

. This will convert non-integer numeric values to integers,
which may actually be the wrong thing to do...

[3] Get the number of rows.

[4] The number of columns, taken from the first row.

[5] Ensure that all the rows have the same size.

[6] Ensure integers only. Non-numeric input will cause program termination here.

[7] The output matrix.

[8] Iterate over the indices for the new matrix; this one takes the rows.

[9] And this takes the columns.

[10] Compute and assign the value for this position.

[11] Pretty print the result.

Running it:

$ ./submatrix-sum "1 2 3 4 | 5 6 7 8 | 9 10 11 12"
[
[14, 18, 22]
[30, 34, 38]
]
$ ./submatrix-sum "1 0 0 0 | 0 1 0 0 | 0 0 1 0 | 0 0 0 1"
[
[2, 1, 0]
[1, 2, 1]
[0, 1, 2]
]

Looking good.

Verbose mode will show the input matrix as well, but it should be just as you'd expect - no surprises there.

$ ./submatrix-sum -v "1 2 3 4 | 5 6 7 8 | 9 10 11 12"
: Matrix: [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
[
[14, 18, 22]
[30, 34, 38]
]
$ ./submatrix-sum -v "1 0 0 0 | 0 1 0 0 | 0 0 1 0 | 0 0 0 1"
: Matrix: [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]
[
[2, 1, 0]
[1, 2, 1]
[0, 1, 2]
]

And that's it.