Challenge, My solutions

TASK #1 › Search Matrix

Task

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.

My solution

For this task there are two things to consider. The first is how to accept an input of a matrix and the target answer. Since we know the grid is 5 × 5, we know the input must be exactly 26 numbers. So I simply slurp in all the numbers from the command line, and pop the last value as the $target value.

The second consideration is how to use an 'efficient search algorithm'. Given that it is only 25 numbers, I would think the most efficient method is slurping all 25 numbers in an array (which I mentioned above), and then use List::Util's any method. It uses a compiled call (unless you're using the Pure Perl version), so would be as fast as possible in a Perl program. And in the real world, I probably would do it that way.

This of course means that we may make up to 25 comparisons with the target number. Since we know the list is already sorted, to make the least number of calls (which is my definition of 'efficient search algorithm' for this challenge) is to perform a binary search. We start with the middle number. If the target is found, bingo! If the target is lower, we take the middle number from the 0 and 11 (the 6th element), if it is higher, we take the middle number from 13 - 24 (the 18th) element. We repeat this pattern until the target number is found, or no number is found. This method means that no more than 5 values in the matrix will be compared.

The upside of doing it this way is if the grid changes size, no modification is required to the code.

Examples

» ./ch-1.pl "[  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 ]" 25
Answer is 1, in 1 check(s)

» ./ch-1.pl "[  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 ]" 35
Answer is 0, in 5 check(s)

» ./ch-1.pl "[  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 ]" 39
Answer is 1, in 5 check(s)

TASK #2 › Ordered Letters

Task

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.

My solutions

The good news that most Linux systems have a dictionary file (and in my case, it's English), and on both Debian and RHEL based distributions can be found at /usr/share/dict/words. To make this task easier, I'm only using words that contain the English alphabet (a-z), so ignoring those with numbers or punctuation marks. I'm also making lower case comparisons too.

I read this file line by line, and skip words that are not ordered. We can find this by comparing the words against join '', sort split '', $word which will order each letter alphabetically.

I then store the maximum length of the word in $max_length and all words of that length in the @words array. If we find a new $max_length, I reset the array.

If the dictionary file is in a different location (or you simply want to use a different word list), you can optionally specify the file name as a command line option.

Example

In RHEL based systems

$ ./ch-2.pl 
Longest words are: aegilops

In Debian based systems

» ./ch-2.pl
Longest words are: billowy

YMMV.