Perl logo (Thanks to 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 }