This is my response to The Weekly Challenge #248.
a string and a character in the given
string.
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.
Input: $str = "aaab", $char = "b"
Output: (3,2,1,0)
Let us do the inelegant solution first; with two passes.
File: shortest-distance-leftright
#! /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.
NxM matrix A of integers.
(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]
Input: $a = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
]
Output: $b = [
[14, 18, 22],
[30, 34, 38]
]
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.