by Arne Sommer

# Ordered Search for Raku

[127] Published 4. May 2021.

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

## Challenge #111.1: Search Matrix

You are given 5x5 matrix filled with integers such that each row is sorted from left to right and the first integer of each row is greater than the last integer of the previous row.

Write a script to find a given integer in the matrix using an efficient search algorithm.

Example: ``` 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`.

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:

File: search-matrix ```#! /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):

File: search-matrix2 ```#! /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

Given a word, you can sort its letters alphabetically (case insensitive). For example, “beekeeper” becomes “beeeeekpr” and “dictionary” becomes “acdiinorty”.

Write a script to find the longest English words that don’t change when their letters are sorted.

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

File: ordered-letters ```#! /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.