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.
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:
- 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.
- If there are any rows that consist entirely of zeros, then they are grouped together at the bottom of the matrix.
- 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.
- 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
Top comments (0)