The weekly challenge 251 - Task 2: Lucky Numbers

 1 #!/usr/bin/perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-251/#TASK2
 3 #
 4 # Task 2: Lucky Numbers
 5 # =====================
 6 #
 7 # You are given a m x n matrix of distinct numbers.
 8 #
 9 # Write a script to return the lucky number, if there is one, or -1 if not.
10 #
11 ## A lucky number is an element of the matrix such that it is
12 ## the minimum element in its row and maximum in its column.
13 #
14 ## Example 1
15 ##
16 ## Input: $matrix = [ [ 3,  7,  8],
17 ##                    [ 9, 11, 13],
18 ##                    [15, 16, 17] ];
19 ## Output: 15
20 ##
21 ## 15 is the only lucky number since it is the minimum in its row
22 ## and the maximum in its column.
23 #
24 ## Example 2
25 ##
26 ## Input: $matrix = [ [ 1, 10,  4,  2],
27 ##                    [ 9,  3,  8,  7],
28 ##                    [15, 16, 17, 12] ];
29 ## Output: 12
30 #
31 ## Example 3
32 ##
33 ## Input: $matrix = [ [7 ,8],
34 ##                    [1 ,2] ];
35 ## Output: 7
36 #
37 ############################################################
38 ##
39 ## discussion
40 ##
41 ############################################################
42 #
43 # For a lucky number, we know:
44 # Since the minimum in a row is at the same time the maximum in
45 # a column, there is no number bigger in that column, so in all
46 # other rows, there is a number that is smaller than the current
47 # number, so the minimum in that other row has to be smaller or
48 # equal to this number; being smaller, it can't be bigger than any
49 # of the numbers in the original row, so it's can't be a lucky number
50 # as well.
51 # So we know we have at most one lucky number.
52 # Finding it is simple: In each row, find the minimum number, then
53 # check whether it is as well the maximum number in its column.
54 
55 use strict;
56 use warnings;
57 use List::Util qw(min max);
58 
59 lucky_numbers([ [ 3,  7,  8], [ 9, 11, 13], [15, 16, 17] ]);
60 lucky_numbers([ [ 1, 10,  4,  2], [ 9,  3,  8,  7], [15, 16, 17, 12] ]);
61 lucky_numbers([ [7 ,8], [1 ,2] ]);
62 lucky_numbers([ [7 ,8], [10 ,2] ]);
63 
64 sub lucky_numbers {
65    my $matrix = shift;
66    print "Input: [\n";
67    foreach my $row (@$matrix) {
68       print "        [" . join(", ", @$row) . "],\n";
69    }
70    print "       ];\n";
71    my $rows = scalar(@$matrix);
72    my $columns = scalar(@{$matrix->[0]});
73    my $row_min = [];
74    my $column_max = [];
75    foreach my $column (0..$columns-1) {
76       my @column_elements = ();
77       foreach my $row (0..$rows-1) {
78          push @column_elements, $matrix->[$row]->[$column];
79       }
80       push @$column_max, max(@column_elements);
81    }
82    foreach my $i (0..$rows-1) {
83       push @$row_min, min(@{$matrix->[$i]});
84       foreach my $j (0..$columns-1) {
85          my $elem = $matrix->[$i]->[$j];
86          if($elem == $row_min->[$i] && $elem == $column_max->[$j]) {
87             print "Output: $elem\n";
88             return;
89          }
90       }
91    }
92    print "Output: -1\n";
93 }
94 
95