laurent_r

These are some answers to the Week 111 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few days (May 9, 2021). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 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

We’re only trying to know whether an integer exists in the matrix. What I would normally do in such case is transform the data structure, i.e. store all the matrix items into a hash and then simply look whether an item exists in the hash. And I’ll also present such a solution.

However, looking carefully at the working of the task, we can see that the task insists on the fact that the integers are in ascending order from left to right and from top to bottom. The task further tells us that we should use an efficient algorithm. Although this is not explicitly specified, it is quite clear that we’re expected to implement a binary search algorithm, which is an efficient algorithm with sorted data.

The first idea might be to flatten the matrix into a one-dimension array, making the dataset much easier to use with a canonical binary search algorithm. But, obviously, that’s also not really what we’re expected to do. The task author wants us to implement a binary search algorithm on a 2-D matrix. We could come up with an “approximate” binary search, i.e. an heuristic looking for the approximate mid-point between two values. For example, we could start by testing any item on the third row and then goto the 2nd or 4th row depending on the result of the test. But that’s not satisfactory: that would not scale easily to other dimensions.

So I decided to perform the binary search on a list of consecutive integers between 0 and 24, and to provide a subroutine to convert these integers into 2-D indices. For example, the sixth item in that range corresponds to indices [1][0].

Search Matrix in Raku

Using Binary Search

The A2AoA subroutine converts a flat rank into 2-D indices. We simply run a binary search on the 0..24 range and use the A2AoA subroutine to find out the correspond values in the matrix. Our test cases will be quite exhaustive, since we’ll be searching the matrix for every integer between 0 and 54.

use v6;

my @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 );

sub A2AoA ($index) {
    my ($i, $j) = $index.polymod(5).reverse;
}
sub binary ($in) {
    my ($min, $max) = 0, 24;
    while $max > $min {
        my $pivot = (($max + $min) /2).Int;
        my ($i, $j) = A2AoA $pivot;
        my $val = @matrix[$i][$j];
        # say "val = $val, $i, $j";
        return 1 if $val == $in;
        if $in > $val {
            $min = $pivot + 1;
        } else {
            $max = $pivot;
        }
    }
    return 0;
}
say "$_ => ", binary $_ for 0..54;

This program displays the following output:

$ raku ./search_item.raku
0 => 0
1 => 1
2 => 1
3 => 1
4 => 0
5 => 1
6 => 0
7 => 1
8 => 0
9 => 1
10 => 0
11 => 1
12 => 0
13 => 0
14 => 0
15 => 1
16 => 0
17 => 0
18 => 0
19 => 1
20 => 1
21 => 0
22 => 0
23 => 1
24 => 1
25 => 1
26 => 0
27 => 0
28 => 0
29 => 1
30 => 0
31 => 1
32 => 1
33 => 1
34 => 0
35 => 0
36 => 0
37 => 0
38 => 0
39 => 1
40 => 1
41 => 0
42 => 1
43 => 0
44 => 0
45 => 1
46 => 0
47 => 1
48 => 1
49 => 1
50 => 0
51 => 0
52 => 0
53 => 0
54 => 0

Note that I’m happy that I used such exhaustive test cases, since my original implementation had a relatively rare bug that I had not seen with the six or seven values I initially tested.

Using a Hash

As I said in the introduction, in the real life, I would transform the input data into a hash and simply perform hash lookup.

use v6;

my @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 );

my %hash;
for @matrix -> @row {
    %hash{$_} = 1 for @row;
}
say "$_ => ", %hash{$_} ?? 1 !! 0 for 0..54;

As it can be seen, the code is much shorter, much simpler and much less prone to errors. It produces the same output:

$ raku ./search_item2.raku
0 => 0
1 => 1
2 => 1
3 => 1
4 => 0
5 => 1
6 => 0
7 => 1
8 => 0
9 => 1
... Lines omitted for brevity...
45 => 1
46 => 0
47 => 1
48 => 1
49 => 1
50 => 1
51 => 0
52 => 0
53 => 0
54 => 0

Search Matrix in Perl

Using Binary Search

This is a port to Perl of the binary search algorithm explained in the introduction above. The A2AoA subroutine converts a flat rank into 2-D indices. We simply run a binary search on the 0..24 range and use the A2AoA subroutine to find out the correspond values in the matrix. Our test cases will be quite exhaustive, since we’ll be searching the matrix for every integer between 0 and 54.

use strict;
use warnings;
use feature "say";

my @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 ]
             );

sub A2AoA {
    my $index = shift;
    my ($i, $j) = (int $index / 5, $index % 5);
}
sub bin_search {
    my $in = shift;
    my ($min, $max) = (0, 24);
    while ($max > $min) {
        my $pivot =  int (($max + $min) /2);
        my ($i, $j) = A2AoA $pivot;
        my $val = $matrix[$i][$j];
        # say "val = $val, $i, $j";
        return 1 if $val == $in;
        if ($in > $val) {
            $min = $pivot + 1;
        } else {
            $max = $pivot;
        }
    }
    return 0;
}
say "$_ => ", bin_search $_ for 0..54;

This program displays the following output:

perl  ./search_item.pl
0 => 0
1 => 1
2 => 1
3 => 1
4 => 0
5 => 1
6 => 0
7 => 1
... lines omitted for brevity ...
45 => 1
46 => 0
47 => 1
48 => 1
49 => 1
50 => 0
51 => 0
52 => 0
53 => 0
54 => 0

Using a Hash

As mentioned above, in the real life, I would transform the input data into a hash and simply perform hash lookup. In Raku, I had to use nested for loops to populate the hash because my attempts using chained maps did not work as expected. There is certainly a way to do it with chained maps, but it is not easy to find the right syntax. No such problem with Perl where my chained maps worked perfectly on my first attempt (see below). There has to be something for which Perl is better or (more convenient) than Raku.

use strict;
use warnings;
use feature "say";

my @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 ]
             );

my %hash = map { $_ => 1 } map { @$_ } @matrix;
say "$_ => ", exists $hash{$_} ? 1 : 0 for 0..54;

This displays the same output as before:

$ perl search_item2.pl
0 => 0
1 => 1
2 => 1
3 => 1
4 => 0
... Lines omitted for brevity ...
45 => 1
46 => 0
47 => 1
48 => 1
49 => 1
50 => 1
51 => 0
52 => 0
53 => 0
54 => 0

Search Matrix in Other Languages

In Scala and Python, I’ll implement only the hash lookup strategy.

Search Matrix in Scala

In Scala, hashes are called “maps” but they behave essentuially the same way.

object SearchItem extends App {
  val matrix = Array(
    Array(1, 2, 3, 5, 7),
    Array(9, 11, 15, 19, 20),
    Array(23, 24, 25, 29, 31),
    Array(32, 33, 39, 40, 42),
    Array(45, 47, 48, 49, 50)
  )

  var hash = scala.collection.mutable.Map[Int, Int]()
  for (row <- matrix) {
    for (item <- row) {
      hash(item) = 1
    }
  }

  for (i <- 0 to 54) {
    if (hash.contains(i)) {
      println(s"$i => 1")
    } else {
      println(s"$i => 0")
    }
  }
}

Output:

0 => 0 1 => 1 2 => 1 3 => 1 4 => 0 … Lines omitted for brevity … 46 => 0 47 => 1 48 => 1 49 => 1 50 => 1 51 => 0 52 => 0 53 => 0 54 => 0

Search Matrix in Python

In Python, hashes are called dictionaries, and can be used the same way.

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 ]
         );

hash = {}
for row in matrix:
    for item in row:
        hash[item] = 1

for i in range(55):
    if i in hash:
        print(i, " => 1")
    else:
        print(i, " => 0")

Output:

$ python3 ./search_item.py
0  => 0
1  => 1
2  => 1
3  => 1
4  => 0
5  => 1
... Lines omitted for brevity ...
45  => 1
46  => 0
47  => 1
48  => 1
49  => 1
50  => 1
51  => 0
52  => 0
53  => 0
54  => 0

Task 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.

For this, I’ll use an English word list contributed to the public domain by Grady Ward as part of the Moby Lexicon project. It is a list of 113,809 crosswords, that is words that are considered valid in crossword puzzles and other word games. The list can be found on my github repository.

Ordered Letters in Raku

We don’t really need to sort the letters: we only need to know whether they are already in the alphabetical order. In Raku, we can use the [...] reduce metaoperator together with the le less than or equal to operator on the letters of the word. Checking whether a list is sorted has a smaller computational complexity than sorting the list, so this should presumably be faster (although it is so fast with my 113-k word list that it doesn’t really matter).

use v6;

my @long-words;
my $max-length = 0;

for './words.txt'.IO.lines -> $word {
    next unless [le] $word.comb;
    my $length = $word.chars;
    if  $length > $max-length {
        @long-words = $word,;
        $max-length = $length;
    } elsif $length == $max-length {
        push @long-words, $word;
    }
}
say @long-words.join(", ");

This program finds two 7-letter words satisfying the task’s criteria and displays the following output:

$ raku ./ordered-letters.raku
beefily, billowy

I do not know what these two words mean, but they are in the input list and they satisfy the criteria.

Ordered Letters in Perl

It is slightly less convenient in Perl than in Raku to check that the letters are already in the proper order, so I’ll simply sort the letters and compare the output with the input word.

use strict;
use warnings;
use feature "say";

my @long_words;
my $max_length = 0;

my $word_list = "./words.txt";
open my $IN, "<", $word_list or die "Cannot open $word_list $!";
while (my $word = <$IN>) {
    chomp $word;
    next unless $word eq join '', sort split //, $word;
    my $length = length $word;
    if  ($length > $max_length) {
        @long_words = ($word);
        $max_length = $length;
    } elsif ($length == $max_length) {
        push @long_words, $word;
    }
}
say "@long_words";

This program produces the same two words:

$ perl ordered-letters.pl
beefily billowy

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, May 16, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.