Binary Match with Raku
[376] Published 21. December 2025.This is my response to The Weekly Challenge #352.
Challenge #352.1: Match String
Write a script to return all strings that are a substring of another word in the given array in the order they occur.
Example 1:
Input: @words = ("cat", "cats", "dog", "dogcat", "dogcat", "rat",
"ratcatdogcat")
Output: ("cat", "dog", "dogcat", "rat")
Input: @words = ("hello", "hell", "world", "wor", "ellow", "elloworld")
Output: ("hell", "world", "wor", "ellow")
Input: @words = ("a", "aa", "aaa", "aaaa")
Output: ("a", "aa", "aaa")
Input: @words = ("flower", "flow", "flight", "fl", "fli", "ig", "ght")
Output: ("flow", "fl", "fli", "ig", "ght")
Input: @words = ("car", "carpet", "carpenter", "pet", "enter", "pen",
"pent")
Output: ("car", "pet", "enter", "pen", "pent")
File: match-string
#! /usr/bin/env raku
unit sub MAIN (*@words where @words.elems > 0, # [1]
:v(:$verbose),
:d(:$duplicates)); # [2]
my @ok; # [3]
for @words -> $substring # [4]
{
for @words -> $word # [5]
{
next if $substring eq $word; # [6]
if $word ~~ /.$substring/ || $word ~~ /$substring./ # [7]
{
say ":Word '$substring' is a substring of '$word'" if $verbose;
@ok.push: $substring; # [8]
last; # ]8a]
}
}
}
say $duplicates # [9]
?? "(" ~ @ok.map({ '"' ~ $_ ~ '"' }).join(", ") ~ ")" # [9a]
!! "(" ~ @ok.unique.map({ '"' ~ $_ ~ '"' }).join(", ") ~ ")"; # [9b]
[1] At least one word (or string, rather).
[2] Allow duplicates in the output with this command line option.
[3] The result will end up here.
[4] Iterate over the words, used as the substring.
[5] Iterate over the words again, this time as the word to look for.
[6] Skip the situation where both loops have the same word. This is not really needed, but it speeds up the loop slightly.
[7] Can we find the substring in the word, with either (at least) a character before or after it (or both)?
[8] If so, add the substring to the result.
[9] Pretty print the result, after getting rid of duplicates
(with unique) if not explicitly told otherwise.
See docs.raku.org/routine/unique for more information about unique.
Running it:
$ ./match-string cat cats dog dogcat dogcat rat ratcatdogcat
("cat", "dog", "dogcat", "rat")
$ ./match-string hello hell world wor ellow elloworld
("hell", "world", "wor", "ellow")
$ ./match-string a aa aaa aaaa
("a", "aa", "aaa")
$ ./match-string flower flow flight fl fli ig ght
("flow", "fl", "fli", "ig", "ght")
$ ./match-string car carpet carpenter pet enter pen pent
("car", "pet", "enter", "pen", "pent")
Looking good.
With verbose mode:
$ ./match-string -v cat cats dog dogcat dogcat rat ratcatdogcat
:Word 'cat' is a substring of 'cats'
:Word 'dog' is a substring of 'dogcat'
:Word 'dogcat' is a substring of 'ratcatdogcat'
:Word 'dogcat' is a substring of 'ratcatdogcat'
:Word 'rat' is a substring of 'ratcatdogcat'
("cat", "dog", "dogcat", "rat")
$ ./match-string -v hello hell world wor ellow elloworld
:Word 'hell' is a substring of 'hello'
:Word 'world' is a substring of 'elloworld'
:Word 'wor' is a substring of 'world'
:Word 'ellow' is a substring of 'elloworld'
("hell", "world", "wor", "ellow")
$ ./match-string -v a aa aaa aaaa
:Word 'a' is a substring of 'aa'
:Word 'aa' is a substring of 'aaa'
:Word 'aaa' is a substring of 'aaaa'
("a", "aa", "aaa")
$ ./match-string -v flower flow flight fl fli ig ght
:Word 'flow' is a substring of 'flower'
:Word 'fl' is a substring of 'flower'
:Word 'fli' is a substring of 'flight'
:Word 'ig' is a substring of 'flight'
:Word 'ght' is a substring of 'flight'
("flow", "fl", "fli", "ig", "ght")
$ ./match-string -v car carpet carpenter pet enter pen pent
:Word 'car' is a substring of 'carpet'
:Word 'pet' is a substring of 'carpet'
:Word 'enter' is a substring of 'carpenter'
:Word 'pen' is a substring of 'carpenter'
:Word 'pent' is a substring of 'carpenter'
("car", "pet", "enter", "pen", "pent")
It is possible to argue that the second «dogcat» in the first example
should be included in the result. The -d command line option will do just
that, by keeping duplicates:
$ ./match-string -v -d cat cats dog dogcat dogcat rat ratcatdogcat
:Word 'cat' is a substring of 'cats'
:Word 'dog' is a substring of 'dogcat'
:Word 'dogcat' is a substring of 'ratcatdogcat'
:Word 'dogcat' is a substring of 'ratcatdogcat'
:Word 'rat' is a substring of 'ratcatdogcat'
("cat", "dog", "dogcat", "dogcat", "rat")
Let us try a different approach, one that does not actually work. But is fun.
File: match-string-tree
#! /usr/bin/env raku
unit sub MAIN (*@words where @words.elems > 0,
:v(:$verbose));
my %h = (); # [1]
for @words -> $word # [2]
{
my $c := %h; # [3]
for $word.comb -> $letter # [4]
{
$c{$letter} //= {}; # [5]
$c := $c{$letter}; # [6]
}
}
say ": Hash: { %h.raku }" if $verbose;
my @ok; # [7]
WRD:
for @words -> $word # [8]
{
my $c := %h; # [9]
for $word.comb -> $letter # [10]
{
if $c{$letter} # [11]
{
$c := $c{$letter}; # [11a]
}
else
{
say ":Not ok: $word" if $verbose;
next WRD; # [12]
}
}
say ":OK: $word" if $verbose;
@ok.push: $word; # [13]
}
say "(" ~ @ok.map({ '"' ~ $_ ~ '"' }).join(", ") ~ ")"; # [14]
[1] We are going to build a tree (a directed graph), with one letter in each node. We can use a simple hash for this. This variable is the top, or tops rather.
[2] Iterate over the words.
[3] Start at the top.
[4] Iterate over the letters in the word.
[5] Is the letter defined as a «next letter» at this point? If not, define it (with an empty hash as value).
[6] Move the current position to that node in the graph, ready for the next iteration.
[7] The result will end up here.
[8] Iterate over the words (again).
[9] Start at the top of the tree.
[10] Iterate over the letters.
[11] Is the current letter present in the graph? If so, set it as the current position.
[12] If not, skip this word (as it is not a match).
[13] We have reached the end of the word, without failing to find a path. Success! Add it to the result.
[14] Pretty print the result.
Here is the graph for the first example:
Some observations:
- There are three start nodes («c», «d» and «r»), even if
%htries to hide the fact - There is no end-of-string marker, so no way of deciding if «cat» was a distinct word in the input (as «cats» is). This is not an issue here, as we are starting with the potential substrings when we do the lookup (tree traversal)
- All lookups start at the top, and there is no (easy) way of starting the lookup further down the tree. Or at least, the present program does not try
- Trying to optimise the tree(s) is a nighmare. Here is an examples
that fails:
As we have no way of finding out if the trailing «s» in «cats» is illegal in «dogcats» and «ratcatdogcats»
The third point means that the program does not work, as shown on the second example (which should have included «world»):
$ ./match-string-tree -v hello hell world wor ellow elloworld
: Hash: {:e(${:l(${:l(${:o(${:w(${:o(${:r(${:l(${:d(${})})})})})})})})}), \
:h(${:e(${:l(${:l(${:o(${})})})})}), \
w(${:o(${:r(${:l(${:d(${})})})})})}
:Not ok: hello
:OK: hell
:Not ok: world
:OK: wor
:OK: ellow
:Not ok: elloworld
("hell", "wor", "ellow")
This is fixable, but will lead to more complexity and code. The original (regex) program is short and concise. And it works. So I'll leave it at that.
But let us show that the program indeed can give us a tree. The fourth example does just that, but this example is easier to follow:
$ ./match-string-tree -v abc abd ade
: Hash: {:a(${:b(${:c(${}), :d(${})}), :d(${:e(${})})})}
:Not ok: abc
:Not ok: abd
:Not ok: ade
()
Challenge #352.2: Binary Prefix
0 or 1.
Define xi as the number formed by taking the first
i+1 bits of
@nums (from $nums[0] to $nums[i]) and interpreting them as a
binary number, with $nums[0] being the most significant bit.
For example:
If @nums = (1, 0, 1), then:
x0 = 1 (binary 1)
x1 = 2 (binary 10)
x2 = 5 (binary 101)
For each i, check whether xi is divisible by 5.
@answer where $answer[i] is true
if xi is divisible by 5, otherwise false.
Example 1:
Input: @nums = (0,1,1,0,0,1,0,1,1,1)
Output: (true, false, false, false, false, true, true, false, false,
false)
Binary numbers formed (decimal values):
0: 0
01: 1
011: 3
0110: 6
01100: 12
011001: 25
0110010: 50
01100101: 101
011001011: 203
0110010111: 407
Input: @num = (1,0,1,0,1,0)
Output: (false, false, true, true, false, false)
1: 1
10: 2
101: 5
1010: 10
10101: 21
101010: 42
Input: @num = (0,0,1,0,1)
Output: (true, true, false, false, true)
0: 0
00: 0
001: 1
0010: 2
00101: 5
Input: @num = (1,1,1,1,1)
Output: (false, false, false, true, false)
1: 1
11: 3
111: 7
1111: 15
11111: 31
Input: @num = (1,0,1,1,0,1,0,0,1,1)
Output: (false, false, true, false, false, true, true, true, false,
false)
1: 1
10: 2
101: 5
1011: 11
10110: 22
101101: 45
1011010: 90
10110100: 180
101101001: 361
1011010011: 723
File: binary-prefix
#! /usr/bin/env raku
unit sub MAIN (*@nums where @nums.elems > 0 && all(@nums) == 0 | 1, # [1]
:v(:$verbose));
my $bin = ""; # [2]
my @divisible; # [3]
for @nums -> $digit # [4]
{
$bin ~= $digit; # [5]
my $decimal = $bin.parse-base(2); # [6]
my $is-div = $decimal %% 5; # [7]
say ":Binary $bin Decimal $decimal { $is-div ?? "divisible by 5" !! "" } "
if $verbose;
@divisible.push: $is-div; # [8]
}
say "({ @divisible.join(", ") })"; # [9]
[1] Ensure at least 1 value, and they must (all) be either 0 or 1.
[2] The current binary value, added to in the loop below.
[3] Are the values divisible (the %% operator) by 5, i.e.
the result to print.
See docs.raku.org/routine/%% for more information about the Divisibility Operator %%.
[4] Iterate over the digits.
[5] Add the digit to the current binary value.
[6] Convert the binary value to decimal (or rather,
the internal format) with Parse-base(2).
See docs.raku.org/routine/parse-base for more information about parse-base.
[7] Is the (decimal) value divisible by 5 (%% 5)?
[8] Add the Boolean value to the result.
[9] Pretty print the result.
Running it:
$ ./binary-prefix 0 1 1 0 0 1 0 1 1 1
(True, False, False, False, False, True, True, False, False, False)
$ ./binary-prefix 1 0 1 0 1 0
(False, False, True, True, False, False)
$ ./binary-prefix 0 0 1 0 1
(True, True, False, False, True)
$ ./binary-prefix 1 1 1 1 1
(False, False, False, True, False)
$ ./binary-prefix 1 0 1 1 0 1 0 0 1 1
(False, False, True, False, False, True, True, True, False, False)
Looking good.
With verbose mode:
$ ./binary-prefix -v 0 1 1 0 0 1 0 1 1 1
:Binary 0 Decimal 0 divisible by 5
:Binary 01 Decimal 1
:Binary 011 Decimal 3
:Binary 0110 Decimal 6
:Binary 01100 Decimal 12
:Binary 011001 Decimal 25 divisible by 5
:Binary 0110010 Decimal 50 divisible by 5
:Binary 01100101 Decimal 101
:Binary 011001011 Decimal 203
:Binary 0110010111 Decimal 407
(True, False, False, False, False, True, True, False, False, False)
$ ./binary-prefix -v 1 0 1 0 1 0
:Binary 1 Decimal 1
:Binary 10 Decimal 2
:Binary 101 Decimal 5 divisible by 5
:Binary 1010 Decimal 10 divisible by 5
:Binary 10101 Decimal 21
:Binary 101010 Decimal 42
(False, False, True, True, False, False)
$ ./binary-prefix -v 0 0 1 0 1
:Binary 0 Decimal 0 divisible by 5
:Binary 00 Decimal 0 divisible by 5
:Binary 001 Decimal 1
:Binary 0010 Decimal 2
:Binary 00101 Decimal 5 divisible by 5
(True, True, False, False, True)
$ ./binary-prefix -v 1 1 1 1 1
:Binary 1 Decimal 1
:Binary 11 Decimal 3
:Binary 111 Decimal 7
:Binary 1111 Decimal 15 divisible by 5
:Binary 11111 Decimal 31
(False, False, False, True, False)
$ ./binary-prefix -v 1 0 1 1 0 1 0 0 1 1
:Binary 1 Decimal 1
:Binary 10 Decimal 2
:Binary 101 Decimal 5 divisible by 5
:Binary 1011 Decimal 11
:Binary 10110 Decimal 22
:Binary 101101 Decimal 45 divisible by 5
:Binary 1011010 Decimal 90 divisible by 5
:Binary 10110100 Decimal 180 divisible by 5
:Binary 101101001 Decimal 361
:Binary 1011010011 Decimal 723
(False, False, True, False, False, True, True, True, False, False)
And that's it.