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.