RogerBW's Blog

I’ve been doing the Perl Weekly Challenges. The latest involved search optimisations and word sorting. (Note that this is open until 9 May 2021.)

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.

The optimisations are fairly clear: the target can only be in a row with first value <= target and last value >= target. If we get to a row that doesn't qualify on the first count, no future row will qualify either. (In the Raku version I did try simply flattening the input matrix and checking whether the search term was in it, to see if this wasn't premature optimisation, but that slowed things down by about 2.5×.)

sub sm {
  my ($matrix,$search)=@_;
  my $f=0;
  foreach my $row (@{$matrix}) {

Check for row validity:

    if ($row->[0] <= $search) {
      if ($row->[-1] >= $search) {

Then if the row is a potential candidate, shift it into a hash and check for key existence. I could have done a chop search on the individual row but at this size it doesn't seem worth it.

        if (exists {map {$_ => 1} @{$row}}->{$search}) {
          $f=1;
        }
        last;
      }
    } else {
      last;
    }
  }
  return $f;
}

Raku is much the same except that I don't need the hash; I can just use

        if ($search ∈ @row) {

and other languages are similar (Python if search in row, Ruby if row.include?(search), Rust if row.contains(&search)).

Python gets awkward because of the fall-through logic: if the current search row was valid based on first and last numbers, it's the only valid row in the list, so after we've tested for the presence of the target we want to drop out of the loop. But because I have no end-block indication apart from indenting, I find it quite unclear just what's going on.

    if row[0] <= search:
      if row[len(row)-1] >= search:
        if search in row:
          f=1
        break
    else:
      break

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.

The obvious approach is to take each word in a dictionary file, sort its letters, and compare with the original word. Some optimisation is possible by only examining words at least as long as the longest we've already got. Raku:

my $ml=0;
my @r;
for lines() {
  my $l=chars($_);
  if ($l >= $ml) {
    if ($_.comb.sort.join('') eq $_) {
      if ($l > $ml) {
        @r=();
        $ml=$l;
      }
      push @r,$_;
    }
  }
}

say $_ for @r;

and Perl and Ruby are similar. Note the latching system: if max is higher than current, clear the list and set max to current. Then, whether or not it was higher, push the new entry onto the list. This ends up with a list containing only the entries with the highest value for max, and is a pattern I find myself using quite a bit.

In Python and Rust I used a temporary array instead of re-joining the string, in Rust because there's no single operation to produce a new sorted vector from a vector, in Python because of the whole prefix-suffix ugliness that forces operations out of order:

            let ll: Vec<char>=line.chars().collect::<Vec<_>>();
            let mut ls=ll.clone();
            ls.sort();
            if ll == ls {

With OSPD2+ I get:

• beefily (in a beefy manner)
• billowy (swelling or swollen into large waves)

and SOWPODS adds:

• addeems (adjudges, tries, tests)
• chikors (partridges native to central Asia, Alectoris chukar)
• dikkops (birds of the family Burhinidae)
• gimmors (pieces of mechanism; mechanical devices or contrivances)

Full code on github.