Perl Weekly Challenge 111: Search Matrix

by Abigail

Challenge

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.

Example

Matrix: [  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 ]

Input: 35
Output: 0 since it is missing in the matrix

Input: 39
Output: 1 as it exists in the matrix

Discussion

This challenge confuses me. We're basically asked to find a number in a sorted list. Which in languages without hashes one would solve with binary search (yielding an \(\mathcal{O} (\log N)\) solution), and in languages with hashes you'd use a hash (yielding an \(\mathcal{O} (1)\) (expected) time solution). Sure, the hash takes linear preprocessing time, but since we're asked to write a script, we're spending linear time reading in the data anyway.

Perhaps the intend was a subroutine which takes a matrix and a target number, but that was not what is being asked. The challenge explicitly asks for a script, which means we have to spend a linear amount of time reading data anyway. So, that's what you get.

The only part where we use the fact we are given a matrix is for the input: the first five lines are assumed to contain the matrix. The rest of the input is taken as numbers to search for.

Only for language lacking hashes/maps/dictionaries/tables, we will make use of the fact the input is sorted. For the majority of languages, the fact input is sorted does not offer additional benefits.

Solutions

All the solutions first read the matrix (five rows with five integers, separated by white space) from standard input. The rest of the input is taken as numbers to search for — one integer per line.

Perl

For our Perl solution, we offer two ways to solve this.

First is a simple hash based solution:

my $MATRIX_SIZE = 5;
my %matrix;
@matrix {<> =~ /-?[0-9]+/g} = () for 1 .. $MATRIX_SIZE;

chomp, say exists $matrix {$_} || 0 while <>;

Here, we read in five lines of data, which we store in a hash. Then for the rest of the input, we print 1 or 0 depending on whether the number is in the matrix or not.

Our second solution has a subroutine which takes two arguments: a 5 x 5 matrix (a reference to a two dimensional array), and a number to search for. We're using a bog standard binary search to find the number. Binary search uses a one dimensional structure to search, but we can trivially map a one dimensional coordinate to a two dimensional one by using integer division, and the modulus operation.

my sub bsearch ($matrix, $target) {
    my ($min, $max) = (0, $MATRIX_SIZE * $MATRIX_SIZE);
    while ($min < $max) {
        use integer;
        my $mid = ($min + $max) / 2;
        #
        # To map a 1-d coordinate c to a 2-d pair x, y, we use
        # x = floor (c / size), y = c % size.
        #
        my $cmp = $$matrix [$mid / $MATRIX_SIZE]
                           [$mid % $MATRIX_SIZE] <=> $target;
        if    ($cmp < 0) {$min = $mid + 1}
        elsif ($cmp > 0) {$max = $mid}
        else  {return 1}
    }
    return (0)
}

Find the full program on GitHub.

AWK

In AWK, arrays are associative, taking both integers and strings as indices. As such, we can do \(\mathcal{O} (1)\) (expected) time lookups.

By default, AWK splits input lines on white space, which makes reading in the data easy. First five ($MATRIX_SIZE) lines are the matrix to search in:

NR <= MATRIX_SIZE {
    for (i = 1; i <= NF; i ++) {
        matrix [$i] = 1
    }
}

The rest of the input are numbers to search for:

NR > MATRIX_SIZE {
    print (matrix [$0] ? 1 : 0)
}

Find the full program on GitHub.

Bash

Bash also has associative arrays, which we can declare by using the -A option to declare.

We can then read in five ($MATRIX_SIZE) lines of data. Using read with the -a option reads a line from standard input, splits it on white space, and places the fields in an array (called line in our case). We then add place each field in the associative array matrix:

declare -A matrix
MATRIX_SIZE=5
for   ((i = 1; i <= $MATRIX_SIZE; i ++))
do    read -a line
      for n in ${line[@]}
      do  matrix[$n]=1
      done
done

We can now read the rest of the input, and print whether or not the read element is in the matrix:

while read number
do    echo $((matrix[$number] ? 1 : 0))
done

Find the full program on GitHub.

C

C does not have native support for hashes or associative arrays. So, for our C solution, we will make use of binary search — which is supported by the standard library.

First order of business is to read 25 integers into an array named matrix:

# define MATRIX_SIZE 5
# define NR_OF_ELEMENTS (MATRIX_SIZE * MATRIX_SIZE)

int * matrix;

if ((matrix = (int *) malloc (NR_OF_ELEMENTS * sizeof (int))) == NULL) {
    perror ("Malloc failed");
    exit (1);
}

/*
 * Read in the matrix
 */
for (int i = 0; i < NR_OF_ELEMENTS; i ++) {
    if (scanf ("%d", &matrix [i]) != 1) {
        perror ("Scanf failed");
        exit (1);
    }
}

We will do the binary search by making use of the bsearch library call. It does need a comparison function, which takes two arguments and which returns a negative value if the first argument is less than the second, zero if the arguments are equal, and positive if the first argument is larger than the second. This is the function we will be using:

static int compare (const void * a, const void * b) {
    return * (int *) a - * (int *) b;
}

We're now ready to search for the values:

int target;
while (scanf ("%d", &target) == 1) {
    printf ("%d\n", bsearch (&target, matrix, NR_OF_ELEMENTS,
                              sizeof (int), compare) == NULL ? 0 : 1);
}

Find the full program on GitHub.

Lua

Lua has tables, which work like associative arrays. It has also a feature to read a number from standard input: read ("*number"), which is quite handy for this challenge:

local MATRIX_SIZE = 5

local matrix = {}

-- 
-- Read in the matrix
--
for i = 1, MATRIX_SIZE * MATRIX_SIZE do 
    matrix [io . read ("*number")] = 1
end

--
-- Read in the rest, printing 1/0 depending on
-- whether the number is present in the matrix or not.
--
while true do
    local target = io . read ("*number")
    if   target == nil then break end
    if   matrix [target]
    then print (1)
    else print (0)
    end
end

Find the full program on GitHub.

Node.js

In Node.js, we first slurp in the entire input, and extract the numbers:

let MATRIX_SIZE = 5

let numbers = 
  require      ("fs")
. readFileSync (0)                     // Read all.
. toString     ()                      // Turn it into a string.
. match        (/-?[0-9]+/g)

Then we create the matrix structure:

let matrix = {}
for (let i = 0; i < MATRIX_SIZE * MATRIX_SIZE; i ++) {
    matrix [numbers [i]] = 1
}

Now we can check the rest of the numbers if they are present:

for (let j = MATRIX_SIZE * MATRIX_SIZE; j < numbers . length; j ++) {
    console . log (matrix [numbers [j]] ? 1 : 0)
}

Find the full program on GitHub.

Pascal

For our Pascal solution, we make use of Binary Search. We start off with defining a bsearch method, which takes a matrix (an array of integers), and a number to search with as arguments, and which returns 1 or 0 depending on whether the number is present or not.

const
    matrix_size = 5;

type
    matrix_type = Array [1 .. matrix_size * matrix_size] of Longint;

function bsearch (matrix: matrix_type; target: Longint) : Integer;
    var
        min, mid, max: Integer;
    begin
        bsearch := 0; 
        min     := 1;
        max     := matrix_size * matrix_size + 1;
        while min < max do
        begin
            mid := (min + max) div 2;
            if matrix [mid] = target then
            begin   
                bsearch := 1;
                min     := max;
            end;
            if matrix [mid] < target then
            begin
                min     := mid + 1;
            end
            else begin  
                max     := mid;
            end
        end
    end;

Reading in the data, and calling the bsearch function:

begin
    (* Read in the matrix *)
    for i := 1 to matrix_size * matrix_size do
    begin
        read (matrix [i]);
    end;

    (* The rest of the input are numbers we want to search *)
    while not eof () do
    begin
        readln  (target);
        writeln (bsearch (matrix, target));
    end;
end.

Find the full program on GitHub.

Python

MATRIX_SIZE = 5

import fileinput
import re

matrix = {}
for i in range (MATRIX_SIZE):
    for n in re . findall (r'-?[0-9]+', input ()):
        matrix [n] = 1

for line in fileinput . input ():
    if line . strip () in matrix:
        print ("1")
    else:
        print ("0")

Find the full program on GitHub.

Ruby

matrix_size = 5

matrix = {}
(1 .. matrix_size) . each do
    ARGF . readline . scan(/-?[0-9]+/) do
        |number|
        matrix [number] = 1
    end
end

ARGF . each_line do
    |number|
    puts (matrix [number . strip] ? 1 : 0)
end

Find the full program on GitHub.


Please leave any comments as a GitHub issue.