Ordered Search for Raku

This is my response to the Perl Weekly Challenge #111.

Challenge #111.1: Search Matrix

    Matrix: [  1,  2,  3,  5,  7 ]
            [  9, 11, 15, 19, 20 ]
            [ 23, 24, 25, 29, 31 ]
            [ 32, 33, 39, 40, 42 ]
            [ 45, 47, 48, 49, 50 ]

    Input: 35
    Output: 0 since it is missing in the matrix

    Input: 39
    Output: 1 as it exists in the matrix

Let us start with the matrix, as given in the challenge. We can set it up like this:

my @m = [[  1,  2,  3,  5,  7 ],
         [  9, 11, 15, 19, 20 ],
         [ 23, 24, 25, 29, 31 ],
         [ 32, 33, 39, 40, 42 ],
         [ 45, 47, 48, 49, 50 ]];

Getting a single value is easy. Just specify the row and column:

> say @m[2][3];  # -> 29

Note the expression «efficient search algorithm». We are given a 5x5 matrix, so any kind of smart search (i.e. actually using an algorithm) will be inefficient. Brute force really is efficient here.

A matrix makes searching harder, so let us flatten it to a single array of values:

> say @m.List.flat
(1 2 3 5 7 9 11 15 19 20 23 24 25 29 31 45 47 48 49 50)

(I do see the irony in getting rid of the matrix, just after creating it. But the challenge specifies a matrix, and I have chosen to adhere to that requirement.)

The flat method does not flatten arrays (as we have here), so we must turn it into a list first (with List).

See docs.raku.org/routine/flat for more information about flat.

See docs.raku.org/routine/List for more information about List.

Locating a specific value in a list (or array) is easy with an any junction:

> say any(@m.List.flat) == 12;
any(False, False, False, False, False, False, False, False, False, False,
    False, False, False, False, False, False, False, False, False, False)

> say any(@m.List.flat) == 11;
any(False, False, False, False, False, False, True, False, False, False,
    False, False, False, False, False, False, False, False, False, False)

See docs.raku.org/routine/any for more information about any.

See docs.raku.org/type/Junction for more information about junctions.

Note the return value; an «any junction». We can collapse (reduce) it to a single value with the boolean coercer so:

> say so any(@m.List.flat) == 12;  # -> False
> say so any(@m.List.flat) == 11;  # -> True

See docs.raku.org/routine/so for more information about the Boolean coercer so.

This gives «True» or «False», but the challenge wanted the decimal values «1» and «0». We can do that with an explicit ternary if:

> say (so any(@m.List.flat) == 12) ?? '1' !! '0';  # -> 0
> say (so any(@m.List.flat) == 11) ?? '1' !! '0';  # -> 1

Or we could use the numeric coercer +, as the Boolean values are 0 and 1 in numeric contect:

> say + so any(@m.List.flat) == 11;  # -> 1
> say + so any(@m.List.flat) == 12;  # -> 0

See docs.raku.org/routine/+ for more information about the numeric coercer +.

Then the program:

#! /usr/bin/env raku

unit sub MAIN (Int $input ); 

my @m = [[  1,  2,  3,  5,  7 ],
         [  9, 11, 15, 19, 20 ],
         [ 23, 24, 25, 29, 31 ],
         [ 32, 33, 39, 40, 42 ],
         [ 45, 47, 48, 49, 50 ]];

say + so any(@m>>.List.flat) == $input;

Running it:

$ ./search-matrix 11
1

$ ./search-matrix 12
0

Adding support for user specified matrices is easy(ish):

#! /usr/bin/env raku

unit sub MAIN (Int $input, Str $matrix = "1 2 3 5 7 | 9 11 15 19 20 | \
  23 24 25 29 31 | 32 33 39 40 42 | 45 47 48 49 50");   # [1]

my @m = $matrix.split("|")>>.words>>.List;              # [2]

say + (so any(@m.List.flat) == $input);

[1] Note the chosen syntax to specify the lines (the «|» character).

[1] Split on the «|» character to get the lines, and use words on each line to get the values (as an array). We slap on List to get a List, as the default behaviour of words gives a Sequence.

Running it:

$ ./search-matrix2 11
1

$ ./search-matrix2 12
0

$ ./search-matrix2 12 "1 2 3 | 12 12 12 | 1 1 1"
1

$ ./search-matrix2 4 "1 2 3 | 12 12 12 | 1 1 1"
0

$ ./search-matrix2 12 "1 2 3 | 12 12 12 | 1 1 1 a"
Cannot convert string to number: base-10 number must begin with valid digits
  or '.' in …

Note the missing check for non-numeric values. They will terminate the program anyway, so having a program crash may be ok. The missing check for the matrix size, and the fact that the numbers should be in increasing order, does not matter for the chosen brute force attack and have been left out.

Challenge #111.2: Ordered Letters

I interpret «the longest English words» as the longest word and additional words of the same length.

#! /usr/bin/env raku

unit sub MAIN (:d(:$dictionary)                   # [1]
                  where $dictionary.IO.r = "/usr/share/dict/british-english",
               :a($all));                         # [2]

my @dict = $dictionary.IO.lines                   # [3]
             .grep(* !~~ /\W/)                    # [3a]
             .map( *.lc )                         # [3b]
             .sort({ $^b.chars <=> $^a.chars });  # [3c]

my $found = 0;                                    # [4]

for @dict -> $word                                # [5]
{
  last if !$all && $word.chars < $found;          # [6]
  
  my $sorted = $word.comb.sort.join;              # [7]
  
  if $word eq $sorted                             # [8]
  {
    say $word;                                    # [8a]
    $found = $word.chars;                         # [8b]
  }
}

[1] Specify another dictionary, if the default value does not suit you.

[2] Use this option if you want all the words, and not just the longest one(s).

[3] Read the dictionary (one word per line), sort out words containing any non-letters [3a], convert them to lowercase [3b], and finally sort the list by size [3c] - the largest first.

[4] Set this one to the size, when we have a match.

[5] For each word in the dictionary (after the changes applied in [3]),

[6] We are finished if the current word is shorter than the largest one. Unless we have used the «all» option; then continue.

[7] Sort the letters in the world, and join them back to a string.

[8] Did we get the word itself in [7]? If so, print it [8a] and set the length [8b].

Running it:

$ ./ordered-letters
billowy

$ ./ordered-letters -a
billowy
abbott
bellow
deimos
abbess
abhors
accent
accept
access
accost
adders
almost
begins
bellow
billow
biopsy
cellos
chills
chilly
chimps
chinos
chintz
choosy
choppy
effort
floors
floppy
glossy
knotty
acrux
…

Let us have a go at the German dictionary, just for fun (nur zum Spaß):

$ ./ordered-letters --dictionary=/usr/share/dict/ngerman 
abflosst
beginnst
bekloppt

$ ./ordered-letters --dictionary=/usr/share/dict/ngerman -a
abflosst
beginnst
bekloppt
beginns
abbisst
abfloss
beehrst
beeilst
beginnt
begosst
beirrst
abgott
…

The number of actual words, highlighted in green:

$ ./ordered-letters --dictionary=/usr/share/dict/ngerman -a | wc
    378     378    1742

$ ./ordered-letters -a | wc
    560     560    2546

And that's it.