Add solution 257.

Signed-off-by: Thomas Köhler <jean-luc@picard.franken.de>

1 files changed, 165 insertions, 0 deletions

diff --git a/challenge-257/jeanluc2020/python/ch-2.py b/challenge-257/jeanluc2020/python/ch-2.py
new file mode 100755
index 0000000000..2594d56ea8
--- /dev/null
+++ b/challenge-257/jeanluc2020/python/ch-2.py
@@ -0,0 +1,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] ] );
+