This is my response to The Weekly Challenge #299.
IMG: Library of Congress
Input: @words = ("cat", "bat", "rat")
$sentence = "the cattle was rattle by the battery"
Output: "the cat was rat by the bat"
Input: @words = ("a", "b", "c")
$sentence = "aab aac and cac bab"
Output: "a a a c b"
Input: @words = ("man", "bike")
$sentence = "the manager was hit by a biker"
Output: "the man was hit by a bike"
#! /usr/bin/env raku
unit sub MAIN ($sentence where $sentence.chars > 0, # [1]
*@words where @words.elems > 0, # [2]
:v(:$verbose));
my @output; # [3]
WORD: # [8a]
for $sentence.words -> $word # [4]
{
for @words -> $replace # [5]
{
if $word.starts-with($replace) # [6]
{
@output.push: $replace; # [7]
say ": Replace '$word' with '$replace'" if $verbose;
next WORD; # [8]
}
}
@output.push: $word; # [9]
}
say @output.join(" "); # [10]
[1] Ensure a sentence of at least one character.
[2] Ensure at least one word.
[3] The resulting words will end up here.
[4] Split the sentence into words (with words),
and iterate over them.
See docs.raku.org/routine/words for more information about words.
[5] Iterate over the replacement words.
[6] If the current word (from the sentence)
starts with (with starts-with) the replacement word,
See docs.raku.org/routine/starts-with for more information about starts-with.
[7] • Add the replacement word to the output.
[8] • Continue with the next word ([8a]).
[9] No replacement? Then add the unadulterated word to the output.
[10] Pretty print the result.
Running it:
$ ./replace-words "the cattle was rattle by the battery" cat bat rat
the cat was rat by the bat
$ ./replace-words "aab aac and cac bab" a b c
a a a c b
$ ./replace-words "the manager was hit by a biker" man bike
the man was hit by a bike
Looking good.
With verbose mode:
$ ./replace-words -v "the cattle was rattle by the battery" cat bat rat
: Replace 'cattle' with 'cat'
: Replace 'rattle' with 'rat'
: Replace 'battery' with 'bat'
the cat was rat by the bat
$ ./replace-words -v "aab aac and cac bab" a b c
: Replace 'aab' with 'a'
: Replace 'aac' with 'a'
: Replace 'and' with 'a'
: Replace 'cac' with 'c'
: Replace 'bab' with 'b'
a a a c b
$ ./replace-words -v "the manager was hit by a biker" man bike
: Replace 'manager' with 'man'
: Replace 'biker' with 'bike'
the man was hit by a bike
Note that punctuation character(s) at the end of replaced words will be lost. The examples do not have any, so we are perhaps good:
$ ./replace-words -v "the manager, was.. hit.. by.. a biker." man bike
: Replace 'manager,' with 'man'
: Replace 'biker.' with 'bike'
the man was.. hit.. by.. a bike
Duplicate replacement words are ignored; the first will be used:
$ ./replace-words -v "the manager was hit by a biker" man bike bi
: Replace 'manager' with 'man'
: Replace 'biker' with 'bike'
the man was hit by a bike
Input: @chars = (['A', 'B', 'D', 'E'],
['C', 'B', 'C', 'A'],
['B', 'A', 'A', 'D'],
['D', 'B', 'B', 'C'])
$str = 'BDCA'
Output: true
Input: @chars = (['A', 'A', 'B', 'B'],
['C', 'C', 'B', 'A'],
['C', 'A', 'A', 'A'],
['B', 'B', 'B', 'B'])
$str = 'ABAC'
Output: false
Input: @chars = (['B', 'A', 'B', 'A'],
['C', 'C', 'C', 'C'],
['A', 'B', 'A', 'B'],
['B', 'B', 'A', 'A'])
$str = 'CCCAA'
Output: true
File: word-search
#! /usr/bin/env raku
unit sub MAIN (:m(:$matrix) = die("No matrix"), # [1]
:w(:$word) = die("No word"), # [2]
:a(:$all), # [3]
:v(:$verbose) = $all);
my @matrix = $matrix ~~ /\|/ # [4]
?? $matrix.split("|")>>.words # [4a]
!! $matrix.words>>.comb; # [4b]
die "Uneven row length" unless [==] @matrix>>.elems; # [5]
my $rows = @matrix.elems; # [6]
my $cols = @matrix[0].elems; # [7]
my $first = $word.substr(0,1); # [8]
my $chars = $word.chars; # [9]
my @todo; # [10]
my $found = False; # [11]
for ^$rows -> $row # [12]
{
for ^$cols -> $col # [12a]
{
if @matrix[$row][$col] eq $first # [12b]
{
@todo.push: "$row,$col"; # [12c]
say ": [$row,$col] == $first" if $verbose;
}
}
}
while (@todo.elems) # [13]
{
my @path = @todo.shift.flat; # [14]
my $length = @path.elems; # [15]
if $length == $chars # [16]
{
say ": Found Path: { @path.raku }" if $verbose;
$found = True; # [16a]
last unless $all; # [16b]
}
else # [17]
{
my $row-col = @path.tail; # [18]
my ($row, $col) = $row-col.split(","); # [19]
my $new-char = $word.substr(@path.elems, 1); # [20]
MOVE: # [25b]
for (0, -1), (-1, 0), (0, +1), (+1, 0) -> ($r,$c) # [21]
{
my $new-row = $row + $r; # [22]
my $new-col = $col + $c; # [23]
my $nrnc = "$new-row,$new-col"; # [24]
for @path -> $pos # [25]
{
next MOVE if $pos eq $nrnc; # [25a]
}
if 0 <= $new-col < $cols && 0 <= $new-row < $rows # [26]
{
if $new-char eq @matrix[$new-row][$new-col] # [27]
{
my @new-path = @path.clone; # [28]
@new-path.push: "$new-row,$new-col"; # [29]
say ": [$new-row,$new-col] == $new-char Path: {@new-path.raku } \
-> { $word.substr(0, @path.elems +1) }" if $verbose;
@todo.unshift: @new-path; # [30]
}
}
}
}
}
say $found; # [31]
[1] The matrix as a string. I choose named arguments this time, as
the order (matrix vs. word) is not obvious. Note the defalt value of
die that kicks in (and terminates the program) if the value
is not supplied.
[2] The word, also as a named argument.
[3] Use this option if you want all the paths. This one will enable verbose mode as well.
[4] Split the matrix into a two dimentional array. I felt that my «matrix as a string» format (as e.g. used in Maximal Right with Raku caused excessive typing, so I devised a new format [4b]. The program supports the old format as well [4a], courtesy of the regex check:
$./word-search -w=CCCAA -m="BABA CCCC ABAB BBAA"
$./word-search -w=CCCAA -m="B A B A | C C C C | A B A B | B B A A"
[5] Ensure that all the rows have the same length.
[6] Get the number of rows,
[7] and the number of columns (from the first row).
[8] Get the first character in the word.
[9] Get the length of the word.
[10] Unfinished paths will be stored here.
[11] We have not found a valid path yet.
[12] Iterate over all the row indices, and column indices [12a]. If the character at this position is the first character in the word [12b], add the position to the list of unfinished paths [12c].
I have chosen to pack a position as a single value, as the
@todo data structure is quite complicated. Now we only
have a two dimentional array...
[13] As long as we have unfinished paths to finish.
[14] Get the first unfinished path.
[15] Get the length of this path.
[16] Are we finished? If so, take note [16a] and terminate the search if we did not explicitly asked for all the paths [16b].
The finished check is done here, and not between [29] and [30], so that a word consisting of a single character will work without checking for this in [12c].
[17] Not finished:
[18] Get the last element in the path (with tail),
See docs.raku.org/routine/tail for more information about tail.
[19] and extract the row and column values.
[20] Get the next character in the word. This is based on the length of the path. If the path has a length of 2, we get the character with offset 2 in the string.
[21] Iterate over the index deltas for the four legal moves (left, up, right, down).
[22] Get the new row index,
[23] and the column index,
[24] and the combined position (the comma separated value).
[25] Check the entire path. Skip this direction if we have already
visited the current position [25a]. Note the use of the «MOVE»
label [25b], so that we break out of the outer for loop.
[26] Do we have a row and column that is inside the matrix?
[27] Do we have the nexty caharacter in the word at this position?
[28] Copy (with clone) the path, so that we do
not mess with the original.
See docs.raku.org/routine/clone for more information about clone.
[29] Add the current position to the copied path.
[30] Add the new path to the list of unfinished paths.
Note the use of unshift to add the path at the beginning instead
of push that would have added it at the end. The result is that
we treat @todo as a stack, and not as a buffer. This ensures depth
first search, which may be more efficient here. Depending on the matrix.
Unsure if the stack idea is a good one? Amend the program
with a new commnand line option, and choose between push and
unshift depending on it.
Note that the program is not really a true stack believer, as it does the initial first character search for the entire matrix in queue mode.
[31] Have we found any path(s)?
Running it:
$ ./word-search -m="ABDE CBCA BAAD DBBC" -w=BDCA
True
$ ./word-search -m="AABB CCBA CAAA BBBB" -w=ABAC
False
$ ./word-search -m="BABA CCCC ABAB BBAA" -w=CCCAA
True
Looking good.
With verbose mode:
$ ./word-search -m="ABDE CBCA BAAD DBBC" -w=BDCA -v
: [0,1] == B
: [1,1] == B
: [2,0] == B
: [3,1] == B
: [3,2] == B
: [0,2] == D Path: ["0,1", "0,2"] -> BD
: [1,2] == C Path: ["0,1", "0,2", "1,2"] -> BDC
: [1,3] == A Path: ["0,1", "0,2", "1,2", "1,3"] -> BDCA
: [2,2] == A Path: ["0,1", "0,2", "1,2", "2,2"] -> BDCA
: Found Path: ["0,1", "0,2", "1,2", "2,2"]
True
$ ./word-search -m="AABB CCBA CAAA BBBB" -w=ABAC -v
: [0,0] == A
: [0,1] == A
: [1,3] == A
: [2,1] == A
: [2,2] == A
: [2,3] == A
: [0,2] == B Path: ["0,1", "0,2"] -> AB
: [1,2] == B Path: ["1,3", "1,2"] -> AB
: [0,3] == B Path: ["1,3", "0,3"] -> AB
: [2,2] == A Path: ["1,3", "1,2", "2,2"] -> ABA
: [3,1] == B Path: ["2,1", "3,1"] -> AB
: [1,2] == B Path: ["2,2", "1,2"] -> AB
: [3,2] == B Path: ["2,2", "3,2"] -> AB
: [1,3] == A Path: ["2,2", "1,2", "1,3"] -> ABA
: [3,3] == B Path: ["2,3", "3,3"] -> AB
False
$ ./word-search -m="BABA CCCC ABAB BBAA" -w=CCCAA -v
: [1,0] == C
: [1,1] == C
: [1,2] == C
: [1,3] == C
: [1,1] == C Path: ["1,0", "1,1"] -> CC
: [1,2] == C Path: ["1,0", "1,1", "1,2"] -> CCC
: [2,2] == A Path: ["1,0", "1,1", "1,2", "2,2"] -> CCCA
: [3,2] == A Path: ["1,0", "1,1", "1,2", "2,2", "3,2"] -> CCCAA
: Found Path: ["1,0", "1,1", "1,2", "2,2", "3,2"]
True
Can we get to the string by difcferent paths? Let us check, with the «-a» option:
$ ./word-search -m="ABDE CBCA BAAD DBBC" -w=BDCA -v -a
: [0,1] == B
: [1,1] == B
: [2,0] == B
: [3,1] == B
: [3,2] == B
: [0,2] == D Path: ["0,1", "0,2"] -> BD
: [1,2] == C Path: ["0,1", "0,2", "1,2"] -> BDC
: [1,3] == A Path: ["0,1", "0,2", "1,2", "1,3"] -> BDCA
: [2,2] == A Path: ["0,1", "0,2", "1,2", "2,2"] -> BDCA
: Found Path: ["0,1", "0,2", "1,2", "2,2"]
: Found Path: ["0,1", "0,2", "1,2", "1,3"]
: [3,0] == D Path: ["2,0", "3,0"] -> BD
: [3,0] == D Path: ["3,1", "3,0"] -> BD
True
$ ./word-search -m="BABA CCCC ABAB BBAA" -w=CCCAA -v -a
: [1,0] == C
: [1,1] == C
: [1,2] == C
: [1,3] == C
: [1,1] == C Path: ["1,0", "1,1"] -> CC
: [1,2] == C Path: ["1,0", "1,1", "1,2"] -> CCC
: [2,2] == A Path: ["1,0", "1,1", "1,2", "2,2"] -> CCCA
: [3,2] == A Path: ["1,0", "1,1", "1,2", "2,2", "3,2"] -> CCCAA
: Found Path: ["1,0", "1,1", "1,2", "2,2", "3,2"]
: [1,0] == C Path: ["1,1", "1,0"] -> CC
: [1,2] == C Path: ["1,1", "1,2"] -> CC
: [1,3] == C Path: ["1,1", "1,2", "1,3"] -> CCC
: [0,3] == A Path: ["1,1", "1,2", "1,3", "0,3"] -> CCCA
: [1,1] == C Path: ["1,2", "1,1"] -> CC
: [1,3] == C Path: ["1,2", "1,3"] -> CC
: [1,0] == C Path: ["1,2", "1,1", "1,0"] -> CCC
: [2,0] == A Path: ["1,2", "1,1", "1,0", "2,0"] -> CCCA
: [1,2] == C Path: ["1,3", "1,2"] -> CC
: [1,1] == C Path: ["1,3", "1,2", "1,1"] -> CCC
: [0,1] == A Path: ["1,3", "1,2", "1,1", "0,1"] -> CCCA
True
The first example has two paths.
And that's it.