# RabbitFarm

### 2021-05-09

#### Efficient Matrix Search: The Weekly Challenge 111

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

## Part 1

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.

### Solution

``````
use strict;
use warnings;

use boolean;
use constant MATRIX_SIZE => 5;

sub matrix_search{
my(\$matrix, \$search) = @_;
unless(@{\$matrix} == 1){
my \$half = int(@{\$matrix} / 2);
if(\$matrix->[\$half]-> > \$search){
my @matrix_reduced = @{\$matrix}[0 .. \$half - 1];
matrix_search(\@matrix_reduced, \$search);
}
elsif(\$matrix->[\$half]-> < \$search){
my @matrix_reduced = @{\$matrix}[\$half .. @{\$matrix} - 1];
matrix_search(\@matrix_reduced, \$search);
}
elsif(\$matrix->[\$half]-> == \$search){
return true;
}
}
else{
return row_search(\$matrix->, \$search);
}
}

sub row_search{
my (\$row, \$search) = @_;
unless(@{\$row} == 1){
my \$half = int(@{\$row} / 2);
if(\$row->[\$half] > \$search){
my @row_reduced = @{\$row}[0 .. \$half - 1];
row_search(\@row_reduced, \$search);
}
elsif(\$row->[\$half] < \$search){
my @row_reduced = @{\$row}[\$half .. @{\$row} - 1];
row_search(\@row_reduced, \$search);
}
elsif(\$row->[\$half] == \$search){
return true;
}
}
else{
return false;
}
}

MAIN:{
my \$N = [[  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 \$search = 35;
print matrix_search(\$N, \$search) . "\n";
\$search = 39;
print matrix_search(\$N, \$search) . "\n";
}
``````

### Sample Run

``````
\$ perl perl/ch-1.pl
0
1
``````

The most efficient way to search through this sorted matrix is with a binary search. Here the binary search is implemented recursively and split into two subroutines. The first search for the right row, the second performs a binary search within the row.

## Part 2

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

### Solution

``````
use strict;
use warnings;

sub max_sorted{
my(\$words) = @_;
my \$max = -1;
my @length_words;
for my \$word (@{\$words}){
my \$sorted_word = join("", sort { \$a cmp \$b } split(//, \$word));
if(\$word eq \$sorted_word && length(\$word) >= \$max){
\$length_words[length(\$word)] = [] if(!\$length_words[length(\$word)]);
push @{\$length_words[length(\$word)]}, \$word;
\$max = length(\$word);
}
}
return \$length_words[\$max];
}

MAIN:{
my @words;
while(<>){
chomp;
push @words, lc(\$_);
}
print join("\n", @{max_sorted(\@words)}) . "\n";
}

``````

### Sample Run

``````
\$ perl perl/ch-2.pl < /usr/share/dict/words
alloquy
beefily
begorry
billowy
egilops
``````

### Notes

This code expects input on STDIN. Here the system dictionary is used. For this file the maximum length of words meeting the criteria is seven. There are six such words, as shown in the output.

Challenge 111

Binary Search