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]->[0] > $search){
            my @matrix_reduced = @{$matrix}[0 .. $half - 1];
            matrix_search(\@matrix_reduced, $search);    
        }  
        elsif($matrix->[$half]->[0] < $search){
            my @matrix_reduced = @{$matrix}[$half .. @{$matrix} - 1];
            matrix_search(\@matrix_reduced, $search);    
        }  
        elsif($matrix->[$half]->[0] == $search){
            return true;  
        } 
    }
    else{
        return row_search($matrix->[0], $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

Notes

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

References

Challenge 111

Binary Search

posted at: 23:58 by: Adam Russell | path: /perl | permanent link to this entry