The weekly challenge 257 - Task 2: Reduced Row Echelon

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-257/#TASK2
  3 #
  4 # Task 2: Reduced Row Echelon
  5 # ===========================
  6 #
  7 # Given a matrix M, check whether the matrix is in reduced row echelon form.
  8 #
  9 # A matrix must have the following properties to be in reduced row echelon form:
 10 #
 11 # 1. If a row does not consist entirely of zeros, then the first
 12 #    nonzero number in the row is a 1. We call this the leading 1.
 13 # 2. If there are any rows that consist entirely of zeros, then
 14 #    they are grouped together at the bottom of the matrix.
 15 # 3. In any two successive rows that do not consist entirely of zeros,
 16 #    the leading 1 in the lower row occurs farther to the right than
 17 #    the leading 1 in the higher row.
 18 # 4. Each column that contains a leading 1 has zeros everywhere else
 19 #    in that column.
 20 #
 21 # For example:
 22 #
 23 # [
 24 #    [1,0,0,1],
 25 #    [0,1,0,2],
 26 #    [0,0,1,3]
 27 # ]
 28 #
 29 # The above matrix is in reduced row echelon form since the first nonzero
 30 # number in each row is a 1, leading 1s in each successive row are farther to
 31 # the right, and above and below each leading 1 there are only zeros.
 32 #
 33 # For more information check out this wikipedia article.
 34 #
 35 ## Example 1
 36 ##
 37 ##     Input: $M = [
 38 ##                       [1, 1, 0],
 39 ##                       [0, 1, 0],
 40 ##                       [0, 0, 0]
 41 ##                 ]
 42 ## Output: 0
 43 #
 44 ## Example 2
 45 ##
 46 ##     Input: $M = [
 47 ##                       [0, 1,-2, 0, 1],
 48 ##                       [0, 0, 0, 1, 3],
 49 ##                       [0, 0, 0, 0, 0],
 50 ##                       [0, 0, 0, 0, 0]
 51 ##                 ]
 52 ## Output: 1
 53 #
 54 ## Example 3
 55 ##
 56 ##     Input: $M = [
 57 ##                       [1, 0, 0, 4],
 58 ##                       [0, 1, 0, 7],
 59 ##                       [0, 0, 1,-1]
 60 ##                 ]
 61 ## Output: 1
 62 #
 63 ## Example 4
 64 ##
 65 ##     Input: $M = [
 66 ##                       [0, 1,-2, 0, 1],
 67 ##                       [0, 0, 0, 0, 0],
 68 ##                       [0, 0, 0, 1, 3],
 69 ##                       [0, 0, 0, 0, 0]
 70 ##                 ]
 71 ## Output: 0
 72 #
 73 ## Example 5
 74 ##
 75 ##     Input: $M = [
 76 ##                       [0, 1, 0],
 77 ##                       [1, 0, 0],
 78 ##                       [0, 0, 0]
 79 ##                 ]
 80 ## Output: 0
 81 #
 82 ## Example 6
 83 ##
 84 ##     Input: $M = [
 85 ##                       [4, 0, 0, 0],
 86 ##                       [0, 1, 0, 7],
 87 ##                       [0, 0, 1,-1]
 88 ##                 ]
 89 ## Output: 0
 90 #
 91 ############################################################
 92 ##
 93 ## discussion
 94 ##
 95 ############################################################
 96 #
 97 # Check all of the conditions one by one. Return the correct
 98 # result.
 99 
100 use strict;
101 use warnings;
102 
103 reduced_row_echelon( [ [1, 1, 0], [0, 1, 0], [0, 0, 0] ] );
104 reduced_row_echelon( [ [0, 1,-2, 0, 1], [0, 0, 0, 1, 3], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0] ] );
105 reduced_row_echelon( [ [1, 0, 0, 4], [0, 1, 0, 7], [0, 0, 1,-1] ] );
106 reduced_row_echelon( [ [0, 1,-2, 0, 1], [0, 0, 0, 0, 0], [0, 0, 0, 1, 3], [0, 0, 0, 0, 0] ] );
107 reduced_row_echelon( [ [0, 1, 0], [1, 0, 0], [0, 0, 0] ] );
108 reduced_row_echelon( [ [4, 0, 0, 0], [0, 1, 0, 7], [0, 0, 1,-1] ] );
109 
110 sub reduced_row_echelon {
111    my $M = shift;
112    # set some variables for better handling
113    my @matrix_rows = @$M;
114    my $rows = @matrix_rows;
115    my $columns = length($matrix_rows[0]);
116    # check that all rows are of the same length, otherwise this isn't a matrix
117    foreach my $i (0..$rows-1) {
118       if(length($matrix_rows[$i]) != $columns) {
119          print "Not a matrix: Not all rows have the same number of columns!\n";
120          return;
121       }
122    }
123    # print the input matrix
124    print "Input: [\n";
125    foreach my $row (@matrix_rows) {
126       print "         [" . join(", ", @$row) . "],\n";
127    }
128    print "       ]\n";
129    # initialize a few helper variables
130    my $last_starting_one = -1;
131    my $row_num = -1;
132    my $found_all_zeroes = 0;
133    # for each row, check all the conditions
134    foreach my $row (@matrix_rows) {
135       $row_num++;
136       my @row_ = @$row;
137       # find first non-zero number in row
138       my $first_non_zero = -1;
139       foreach my $i (0..$#row_) {
140          if($row_[$i] != 0) {
141             if($row_[$i] == 1) {
142                $first_non_zero = $i;
143             } else {
144                # we found the first non-zero number, but it's != 1
145                # first condition not met
146                print "Output: 0\n";
147                return;
148             }
149             last;
150          }
151       }
152       if($first_non_zero == -1) {
153          # this row consists entirely of zeroes
154          $found_all_zeroes = 1;
155       }
156       if($found_all_zeroes && $first_non_zero != -1) {
157          # we found a row with all zeroes before, but now we have a non-zero element in the row
158          # condition 2 not met
159          print "Output: 0\n";
160          return;
161       }
162       if($first_non_zero != -1 && $first_non_zero <= $last_starting_one) {
163          # our first non-zero element is before the first non-zero in the previous row
164          # condition 3 not met
165          print "Output: 0\n";
166          return;
167       }
168       $last_starting_one = $first_non_zero; # for the next round
169       foreach my $j (0..$#matrix_rows) {
170          next if $j == $row_num;
171          if($matrix_rows[$j]->[$first_non_zero] != 0 && $first_non_zero >= 0) {
172             # we found a row that has a non-zero value in the column that matches
173             # the first non-zero column in the row we're currently considering
174             # condition 4 not met
175             print "Output: 0\n";
176             return;
177          }
178       }
179    }
180    print "Output: 1\n";
181 }