No music again this week. I don’t know why, it’s just not coming to me.
Onward to Perl Weekly Challenge 257!
Task 1: Smaller than Current
You are given an 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)
Approach
Something tells me there’s a clever way to accomplish this, but I’m just going to plow ahead and do this as a double loop.
Raku
sub smallerThan(@ints) {
my @counts;
for 0 .. @ints.end -> $i {
@counts[$i] = 0;
for 0 .. @ints.end -> $j {
next if $i == $j;
@counts[$i]++ if @ints[$j] < @ints[$i];
}
}
return @counts;
}
View the entire Raku script for this task on GitHub.
Perl
As usual, the Perl version is almost identical to the Raku version except for the sigils and looping.
sub smallerThan(@ints) {
my @counts;
foreach my $i (0 .. $#ints) {
@counts[$i] = 0;
foreach my $j (0 .. $#ints) {
next if $i == $j;
$counts[$i]++ if $ints[$j] < $ints[$i];
}
}
return @counts;
}
View the entire Perl script for this task on GitHub.
Python
The biggest thing I needed to remember for Python was to append elements to the counts list, because in Python you can’t extend an array just by assigning to a previously non-existent array index. I did, however, look up that Python has one-line if statements.
def smallerThan(ints):
counts = []
for i in range(len(ints)):
counts.append(0)
for j in range(len(ints)):
if i != j and ints[j] < ints[i]: counts[i] += 1
return counts
View the entire Python script for this task on GitHub.
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
Approach
Again, there may be a clever way to do this, but I figure the easiest way is to just plow through the conditions. If we fail one, we can return early.
Raku
At first, I thought of adding all the values in a row using Raku’s Reduction Metaoperator to see if they were all zeroes, but then I noticed that examples 2 and 4 thwart that method, because 0+1-2+0+1=0. So I switched to a loop.
sub rowIsEntirelyZeros(@row) {
for @row -> $n {
next if $n == 0;
return 0;
}
return 1;
}
sub rowHasLeadingOne(@row) {
for @row -> $n {
next if $n == 0;
return $n == 1;
}
}
sub leadingOnePosition(@row) {
for 0 .. @row.end -> $i {
next if @row[$i] == 0;
return $i;
}
}
sub columnHasZerosBesidesLeadingOne(@matrix, $col) {
my $count = 0;
for @matrix -> @row {
next if @row[$col] == 0; # skip zeroes
return 0 if @row[$col] != 1; # fail if not one
$count++; # count ones
}
return $count == 1;
}
sub isReducedRowEchelon(@matrix) {
my $foundAllZeroRow = 0;
my $lastLeadingOnePos = -1; # avoid comparison with undef
for @matrix -> @row {
if (! rowIsEntirelyZeros(@row)) {
# 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.
return 0 unless rowHasLeadingOne(@row);
# 2. If there are any rows that consist entirely of zeros,
# then they are grouped together at the bottom of the
# matrix.
return 0 if $foundAllZeroRow;
# 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.
my $thisLeadingOnePos = leadingOnePosition(@row);
return 0 if $lastLeadingOnePos > $thisLeadingOnePos;
$lastLeadingOnePos = $thisLeadingOnePos;
# 4. Each column that contains a leading 1 has zeros
# everywhere else in that column.
return 0 unless columnHasZerosBesidesLeadingOne(
@matrix, $thisLeadingOnePos
);
}
else {
$foundAllZeroRow = 1;
}
}
return 1;
}
View the entire Raku script for this task on GitHub.
Perl
Unlike Raku, in Perl you can’t have an array parameter followed by a scalar, so I switched them to be scalars that held array references.
sub rowIsEntirelyZeros(@row) {
foreach my $n (@row) {
next if $n == 0;
return 0;
}
return 1;
}
sub rowHasLeadingOne(@row) {
foreach my $n (@row) {
next if $n == 0;
return $n == 1;
}
}
sub leadingOnePosition(@row) {
foreach my $i (0 .. $#row) {
next if $row[$i] == 0;
return $i;
}
}
sub columnHasZerosBesidesLeadingOne($matrix, $col) {
my $count = 0;
foreach my $row (@$matrix) {
next if $row->[$col] == 0; # skip zeroes
return 0 if $row->[$col] != 1; # fail if not one
$count++; # count ones
}
return $count == 1;
}
sub isReducedRowEchelon(@matrix) {
my $foundAllZeroRow = 0;
my $lastLeadingOnePos = -1; # avoid comparison with undef
foreach my $row (@matrix) {
if (! rowIsEntirelyZeros(@$row)) {
# 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.
return 0 unless rowHasLeadingOne(@$row);
# 2. If there are any rows that consist entirely of zeros,
# then they are grouped together at the bottom of the
# matrix.
return 0 if $foundAllZeroRow;
# 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.
my $thisLeadingOnePos = leadingOnePosition(@$row);
return 0 if $lastLeadingOnePos > $thisLeadingOnePos;
$lastLeadingOnePos = $thisLeadingOnePos;
# 4. Each column that contains a leading 1 has zeros
# everywhere else in that column.
return 0 unless columnHasZerosBesidesLeadingOne(
\@matrix, $thisLeadingOnePos
);
}
else {
$foundAllZeroRow = 1;
}
}
return 1;
}
View the entire Perl script for this task on GitHub.
Python
Now that I know Python has one-line if statements, it’s easy to translate the postfix if/unless statements!
def rowIsEntirelyZeros(row):
for n in row:
if not n == 0: return 0
return 1
def rowHasLeadingOne(row):
for n in row:
if not n == 0: return n == 1
def leadingOnePosition(row):
for i in range(len(row)):
if not row[i] == 0: return i
def columnHasZerosBesidesLeadingOne(matrix, col):
count = 0
for row in matrix:
if not row[col] == 0: # skip zeroes
if row[col] != 1: return 0 # fail if not one
count += 1 # count ones
return count == 1
def isReducedRowEchelon(matrix):
foundAllZeroRow = 0
lastLeadingOnePos = -1 # avoid comparison with undef
for row in matrix:
if not rowIsEntirelyZeros(row):
# 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.
if not rowHasLeadingOne(row): return 0
# 2. If there are any rows that consist entirely
# of zeros, then they are grouped together at
# the bottom of the matrix.
if foundAllZeroRow: return 0
# 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.
thisLeadingOnePos = leadingOnePosition(row)
if lastLeadingOnePos > thisLeadingOnePos: return 0
lastLeadingOnePos = thisLeadingOnePos
# 4. Each column that contains a leading 1 has
# zeros everywhere else in that column.
if not columnHasZerosBesidesLeadingOne(
matrix, thisLeadingOnePos
): return 0
else:
foundAllZeroRow = 1
return 1
View the entire Python script for this task on GitHub.
Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-257/packy-anderson