| 23 February 2024 | Challenge 257 |
Ranked Echelons
Task 1: Smaller than Current
Submitted by: Mohammad Sajid Anwar
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.
Example 1
Input: @ints = (5, 2, 1, 6)
Output: (2, 1, 0, 3)
For $ints[0] = 5, there are two integers (2,1) smaller than 5.
For $ints[1] = 2, there is one integer (1) smaller than 2.
For $ints[2] = 1, there is none integer smaller than 1.
For $ints[3] = 6, there are three integers (5,2,1) smaller than 6.
Example 2
Input: @ints = (1, 2, 0, 3)
Output: (1, 2, 0, 3)
Example 3
Input: @ints = (0, 1)
Output: (0, 1)
Example 4
Input: @ints = (9, 4, 9, 2)
Output: (2, 1, 2, 0)
Solution
This task is the same as task 1 in challenge 244. Looking for a different approach.
At first let’s assume the list elements were unique.
Considering example 2. We start with an index sort on the list.
L: [1, 2, 0, 3] => IS: [2, 0, 1, 3]
We may read this as: The element L[IS[i]] is the i-th element in the sorted list and thus there are i elements smaller than L[IS[i]].
Pairing the elements in IS with their index yields:
[
[2, 0],
[0, 1],
[1, 2],
[3, 3]
]
Sorting by the first column reveals the requested result in the second column:
[
[0, 1],
[1, 2],
[2, 0],
[3, 3]
]
Obviously this fails, when the elements are not unique, as equal values have different positions in the sorted list.
This may be compensated by a “local enumeration”, where equal values in a sorted list are assigned a sequence number.
PDL has a function enumvec that performs just this task.
So with PDL we may write this as:
use PDL;
use PDL::NiceSlice;
sub stc {
my $l = long @_;
my $si = $l->qsorti;
cat($si, sequence($l) - $l->($si)->dummy(0)->enumvec)
->xchg(0,1)->qsortvec->((1));
}
See the full solution.
Task 2: Reduced Row Echelon
Submitted by: Ali Moradi
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 nonzero 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.
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}(https://en.wikipedia.org/wiki/Row_echelon_form) 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
Solution
There are some tests to be performed on the given matrix.
- find all ones in the matrix and get their indices
- limit the index list to those elements that represent the first
1in a row. - check that the columns from the “first ones” are strictly ascending
- check that are no nonzero elements before and above each of the “first ones”
1s - identify all zero rows
- check that the last row having a leading
1comes before the first zero row - check that the number of rows with a leading
1plus the number of zero rows matches the total number of rows - if all these checks have succeeded, the matrix is in reduced echelon form.
As Perl/PDL code:
use PDL;
use PDL::NiceSlice;
sub is_reduced_echelon {
my $m = pdl @_;
my $allones = whichND($m == 1);
my $firstidx = which($allones->(1)->enumvec == 0);
my $firstones = $allones->dice('X', $firstidx);
return unless $firstones->dim(1) < 2 ||
all $firstones((0),0:-2) < $firstones((0),1:-1);
for my $firstone ($firstones->dog) {
my ($col, $row) = $firstone->list;
return unless 1 == sum $m->dice('X', $row)->(0:$col) != 0;
return unless 1 == sum $m->dice($col, 'X')->(,0:$row) != 0;
}
my $zeros = which $m->orover == 0;
return unless !$firstones->ngood || !$zeros->ngood ||
$firstones->((1))->max < $zeros->min;
return unless $zeros->dim(0) + $firstidx->dim(0) == $m->dim(1);
1;
}
See the full solution.