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