The current echelon

Weekly Challenge 257

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Smaller than Current

Task

You are given a array of integers, @ints.

Write a script to find out how many integers are smaller than current i.e. foreach ints[i], count ints[j] < ints[i] where i != j.

My solution

The second part of the condition does not need to be checked, as ints[j] will never be less than ints[i] when i and j are the same. In Python, this is a simple one liner:

def smaller_than_current(ints: list) -> list:
    return [sum(1 for j in ints if j < i) for i in ints]

which probably doesn't really need much explanation.

The Perl code is a little more complex as it doesn't easily allow a double for loop in a single line.

sub smaller_ints ( $ints, $target ) {
    return scalar( grep { $_ < $target } @$ints );
}

sub main (@ints) {
    my @results = map { smaller_ints( \@ints, $_ ) } @ints;
    say '(', join( ', ', @results ), ')';
}

Examples

$ ./ch-1.py 5 2 1 6
(2, 1, 0, 3)

$ ./ch-1.py 1 2 0 3
(1, 2, 0, 3)

$ ./ch-1.py 0 1
(0, 1)

$ ./ch-1.py 9 4 9 2
(2, 1, 2, 0)

Task 2: Reduced Row Echelon

Task

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 non-zero 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.

My solution

These are the tasks that I really like. It challenges me to take the requirements and interpret them into functioning code. I suppose today's kids just ask ChatGPT or Microsoft Co-pilot to write the code :P

As this code is a bit more complex than usual, I'll try and describe my solution as best I can. The first step is to take the JSON input, and validate the rows are all of the size.

def validate_matrix(matrix):
    rows = len(matrix)
    cols = len(matrix[0])

    for r in range(1, rows):
        # Check that all columns are of equal length
        if len(matrix[r]) != cols:
            raise ValueError(f'Row {r} has different number of columns')

The next thing I do is calculate the position of the leading (first) one in each row (or None in Python or -1 in Perl if there are no ones)

leading_one = [None if 1 not in row else row.index(1) for row in matrix]

I then iterate over each row. If the row is all zeros, there are no further checks required, so skip it. I also check that the first non-zero number is a one.

for row_num in range(len(matrix)):
    row = matrix[row_num]
    leading_one_pos = leading_one[row_num]

    if all(value == 0 for value in row):
        continue

    for value in row:
        if value == 1:
            break
        if value != 0:
            return 0

The next check I perform is to ensure that if the position of the leading one is higher than the position of the leading one of the previous row. I don't perform this check on the first row (where row_num == 0). If the previous row doesn't have any ones (i.e. is None), then the second rule (zeros at the end) isn't meet.

    if row_num != 0:
        if leading_one[row_num - 1] is None:
            return 0
        if leading_one[row_num - 1] > leading_one_pos:
            return 0

The last check I perform is to ensure that all other rows don't have a non-zero value at the position of the leading one in the current row. The easiest way to do this is to count the number of non-zero values in this column, and check if it is one (the current row).

    if sum(1 for row in matrix if row[leading_one_pos] != 0) != 1:
        return 0

If all the rows pass the checks, I'll return 1 at the end of the loop to indicate the matrix is in reduced row echelon form.

Examples

$ ./ch-2.py "[[1, 0, 0, 1], [0, 1, 0, 2], [0, 0, 1, 3]]"
1

$ ./ch-2.py "[[1, 1, 0], [0, 1, 0], [0, 0, 0]]"
0

$ ./ch-2.py "[[0, 1, -2, 0, 1], [0, 0, 0, 1, 3], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]"
1

$ ./ch-2.py "[[1, 0, 0, 4], [0, 1, 0, 7], [0, 0, 1, -1]]"
1