laurent_r

These are some answers to the Week 251, Task 2, of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few days from now (on January 14, 2024 at 23:59). This blog post provides some solutions to this challenge. Please don’t read on if you intend to complete the challenge on your own.

Task 2: Lucky Number

You are given a m x n matrix of distinct numbers.

Write a script to return the lucky number, if there is one, or -1 if not.

A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.

Example 1

Input: $matrix = [ [ 3,  7,  8],
                   [ 9, 11, 13],
                   [15, 16, 17] ];
Output: 15

15 is the only lucky number since it is the minimum in its row and the maximum in its column.

Example 2

Input: $matrix = [ [ 1, 10,  4,  2],
                   [ 9,  3,  8,  7],
                   [15, 16, 17, 12] ];
Output: 12

Example 3

Input: $matrix = [ [7 ,8],
                   [1 ,2] ];
Output: 7

An important point here is that the input matrix may contain only distinct numbers. This means that we may always find one and only one minimum item in the rows and one maximum item in the columns. So we don't have to worry about having several minimum (or maximum) values.

If the input matrix may contain negative numbers, there is a possibility that - 1 is the lucky number for that matrix. When we receive - 1 as a return value, we may not be able to know whether this value is the lucky number for that matrix, or whether the subroutine has returned that value because it wasn't able to find a lucky number. To avoid that problem, we will add to the specification that the matrix may contain only distinct positive integers.

Lucky Number in Raku

The idea is to iterate over the rows of the input matrix and, for each row, to find the index of the minimum value, using the built-in min function. Note that, as of the 2023.08 Rakudo compiler release, it is possible to use the :k named argument to get directly the index of minimum value. But I can't use this here, since my version of Rakudo is only v2023.06. So, instead, I used a callable argument introduced by the :by named argument. Once the index of the minimum value of a row, we check whether it is the maximum value of its column. If so, we return that value. And we return -1 at the end if we were not able to find a lucky number.

sub lucky-number (@in) {
    ROW-LABEL:
    for 0..@in.end -> $row {
        my $min_i = min(0..@in[$row].end, :by( {@in[$row][$_] }));
        my $min_val = @in[$row][$min_i];
        for 0..@in.end -> $i {
            next ROW-LABEL if @in[$i][$min_i] > $min_val;
        }
        return $min_val;
    }
    return -1
}


for ( <3 7 8>, <9 11 13>, <15 16 17>),
    ( <1 10 4 2>, <9 3 8 7>, <15 16 17 12>),
    ( <7 8>, <1 2> ) -> @test {

    printf "%-40s => ", @test.gist;
    say lucky-number @test;
}

This program displays the following output:

$ raku ./lucky-number.raku
((3 7 8) (9 11 13) (15 16 17))           => 15
((1 10 4 2) (9 3 8 7) (15 16 17 12))     => 12
((7 8) (1 2))                            => 7

Lucky Number in Perl

This is a port to Perl of the above Raku program, except that dealing with nested arrays tends to be slightly more complicated in Perl because we have to deal with array references everywhere. The method to find the lucky number is the same, so you can check the explanations in the section above if needed. An additional change is that we had to write our own min subroutine to find the index of the minimum value in a given input list or array.

use strict;
use warnings;
use feature 'say';

sub min {
    my @in = @_;
    my $min = $in[0];
    my $min_i = 0;
    for my $i (0..$#in) {
        if ($in[$i] < $min) {
            $min_i = $i;
            $min = $in[$i];
        }
    }
    return $min_i;
}

sub lucky_number {
    my @in = @_;
    ROW_LABEL:
    for my $row (0..$#in) {
        my $min_i = min @{$in[$row]};
        my $min_val = $in[$row][$min_i];
        for my $i (0..$#in) {
            next ROW_LABEL if $in[$i][$min_i] > $min_val;
        }
        return $min_val;
    }
    return -1
}

for my $test ( [ [<3 7 8>], [<9 11 13>], [<15 16 17>] ],
      [ [<1 10 4 2>], [<9 3 8 7>], [<15 16 17 12>] ],
      [ [<7 8>], [<1 2>] ]) {

    my @gist = map { " [@$_]" } @$test;
    printf "%-40s => ", "@gist ";
    say lucky_number @$test;
}

This program displays the following output:

$ perl  ./lucky-number.pl
 [3 7 8]  [9 11 13]  [15 16 17]          => 15
 [1 10 4 2]  [9 3 8 7]  [15 16 17 12]    => 12
 [7 8]  [1 2]                            => 7

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on January 21, 2024. And, please, also spread the word about the Perl Weekly Challenge if you can.