The weekly challenge 270 - Task 1: Special Positions

 1 #!/usr/bin/perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-270/#TASK1
 3 #
 4 # Task 1: Special Positions
 5 # =========================
 6 #
 7 # You are given a m x n binary matrix.
 8 #
 9 # Write a script to return the number of special positions in the given binary matrix.
10 #
11 ## A position (i, j) is called special if $matrix[i][j] == 1 and all other elements in the row i and column j are 0.
12 #
13 ## Example 1
14 ##
15 ## Input: $matrix = [ [1, 0, 0],
16 ##                    [0, 0, 1],
17 ##                    [1, 0, 0],
18 ## ]
19 ## Output: 1
20 ##
21 ## There is only one special position (1, 2) as $matrix[1][2] == 1
22 ## and all other elements in row 1 and column 2 are 0.
23 #
24 ## Example 2
25 ##
26 ## Input: $matrix = [ [1, 0, 0],
27 ##                    [0, 1, 0],
28 ##                    [0, 0, 1],
29 ## ]
30 ## Output: 3
31 ##
32 ## Special positions are (0,0), (1, 1) and (2,2).
33 #
34 ############################################################
35 ##
36 ## discussion
37 ##
38 ############################################################
39 #
40 # We walk the matrix and for each position we check whether
41 # the position is special.
42 # For this we use a function that just checks the same column
43 # in all rows, and checks the same row for all columns. If
44 # row and column are the target row and column, we conclude the
45 # point is not special if it isn't 1, for all other values we
46 # conclude the point is not special if it isn't 0. If we reach
47 # the end and we didn't eliminate the point as not special, then
48 # we conclude this point is special.
49 
50 use strict;
51 use warnings;
52 
53 special_positions( [ [1, 0, 0], [0, 0, 1], [1, 0, 0], ] );
54 special_positions( [ [1, 0, 0], [0, 1, 0], [0, 0, 1], ] );
55 
56 sub special_positions {
57    my $matrix = shift;
58    my @rows = @$matrix;
59    my $num_rows = scalar(@rows);
60    my $num_columns = scalar(@{$rows[0]});
61    my $special = 0;
62    foreach my $i (0..$num_rows-1) {
63       foreach my $j (0..$num_columns-1) {
64          if(is_special($i, $j, $num_rows, $num_columns, $matrix)) {
65             $special++;
66          }
67       }
68    }
69    print "Output: $special\n";
70 }
71 
72 sub is_special {
73    my ($i, $j, $num_rows, $num_columns, $matrix) = @_;
74    foreach my $row (0..$num_rows-1) {
75       if($i == $row) {
76          return 0 if $matrix->[$row]->[$j] != 1;
77       } else {
78          return 0 if $matrix->[$row]->[$j] != 0;
79       }
80    }
81    foreach my $column (0..$num_columns-1) {
82       if($j == $column) {
83          return 0 if $matrix->[$i]->[$column] != 1;
84       } else {
85          return 0 if $matrix->[$i]->[$column] != 0;
86       }
87    }
88    return 1;
89 }
90