This is my response to The Weekly Challenge #257.
@ints.
ints[i], count ints[j] < ints[i] where i != j.
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.
Input: @ints = (1, 2, 0, 3)
Output: (1, 2, 0, 3)
Input: @ints = (0, 1)
Output: (0, 1)
Input: @ints = (9, 4, 9, 2)
Output: (2, 1, 2, 0)
We can safely ignore where i != j, as the current value cannot be
smaller than itself.
This is straight forward:
File: smaller-than-grep
#! /usr/bin/env raku
unit sub MAIN (*@ints where @ints.elems > 1 && all(@ints) ~~ Int, # [1]
:v(:$verbose));
my @count; # [2]
for @ints -> $int # [3]
{
my @smaller = @ints.grep: * < $int; # [4]
my $count = @smaller.elems; # [5]
say ": $int - with $count smaller ({ @smaller.join(",") })" if $verbose;
@count.push: $count; # [6]
}
say "({ @count.join(", ") })"; # [7]
[1] At least one value, all of which must be integers.
[2] The result will end up here.
[3] Iterate over the input values.
[4] Get the values that are lower than the current one (from [3]). Note the colon syntax instead of wrapping the expression in parens
[5] Count them.
[6] Push that count to the result.
[7] Pretty print the result.
Running it:
$ ./smaller-than-grep 5 2 1 6
(2, 1, 0, 3)
$ ./smaller-than-grep 1 2 0 3
(1, 2, 0, 3)
$ ./smaller-than-grep 0 1
(0, 1)
$ ./smaller-than-grep 9 4 9 2
(2, 1, 2, 0)
Looking good.
With verbose mode:
$ ./smaller-than-grep -v 5 2 1 6
: 5 - with 2 smaller (2,1)
: 2 - with 1 smaller (1)
: 1 - with 0 smaller ()
: 6 - with 3 smaller (5,2,1)
(2, 1, 0, 3)
$ ./smaller-than-grep -v 1 2 0 3
: 1 - with 1 smaller (0)
: 2 - with 2 smaller (1,0)
: 0 - with 0 smaller ()
: 3 - with 3 smaller (1,2,0)
(1, 2, 0, 3)
$ ./smaller-than-grep -v 0 1
: 0 - with 0 smaller ()
: 1 - with 1 smaller (0)
(0, 1)
$ ./smaller-than-grep -v 9 4 9 2
: 9 - with 2 smaller (4,2)
: 4 - with 1 smaller (2)
: 9 - with 2 smaller (4,2)
: 2 - with 0 smaller ()
(2, 1, 2, 0)
We can write this much shorter, if we ditch verbose mode:
File: smaller-than-current
#! /usr/bin/env raku
unit sub MAIN (*@ints where @ints.elems > 1 && all(@ints) ~~ Int);
say "({ @ints.map({ @ints.grep( * < $_ ).elems }).join(", ") })";
Note that $_ refers to the current value in the
outer loop (yes, map is a loop in disguise), as the use of
the ({ and }) wrappers gives us $_. Whereas
* refers to the inner loop (the grep), as the usage
of parens only gives us *. Using both allows us to iterate
over two arrays without declaring variables to hold the current
values. Pretty neat.
Running it gives the expected result:
$ ./smaller-than-current 5 2 1 6
(2, 1, 0, 3)
$ ./smaller-than-current 1 2 0 3
(1, 2, 0, 3)
$ ./smaller-than-current 0 1
(0, 1)
$ ./smaller-than-current 9 4 9 2
(2, 1, 2, 0)
This approach is not optimal for large data sets, as it scans the entire input array for each value. We can remedy that by precomputing the values:
File: smaller-than-bag
#! /usr/bin/env raku
unit sub MAIN (*@ints where @ints.elems > 1 && all(@ints) ~~ Int,
:v(:$verbose));
my $bag = @ints>>.Int.Bag; # [1]
my $smaller = 0; # [2]
my %smaller; # [3]
for $bag.keys.sort -> $key # [4]
{
say ": $key: smaller: $smaller" if $verbose;
%smaller{$key} = $smaller; # [5]
$smaller += $bag{$key}; # [6]
}
say "({ @ints.map({ %smaller{$_} }).join(", ") })"; # [7]
[1]] Turn the input into a Bag, a hash like structure where the
keys are the (distinct) values, and the values are their frequency. This is done
only once.
See docs.raku.org/routine/Bag for more information about Bag.
[2] The current number of smaller values. We will add to this as we progress to higher values, as everything lower than e.g. 100 will also be lower than 200.
[3] Place the «smaller than» counts here. Note that we cannot just print them, as that would loose the all-important order.
[4] iterate over the values (the input values, distinct and ordered - lowest first).
[5] Save the number of values lower than this one. Initially 0, and thereafter the result of the additions in [6].
[6] Add the number of instances (count) of the current value.
[7] Pretty print the result, looking up the count for each input value.
Running it gives the same result as before, but verbose mode does not show the actual values this time.
$ ./smaller-than-bag -v 5 1 2 6
: 1: smaller: 0
: 2: smaller: 1
: 5: smaller: 2
: 6: smaller: 3
(2, 0, 1, 3)
$ ./smaller-than-bag -v 1 2 0 3
: 0: smaller: 0
: 1: smaller: 1
: 2: smaller: 2
: 3: smaller: 3
(1, 2, 0, 3)
$ ./smaller-than-bag -v 0 1
: 0: smaller: 0
: 1: smaller: 1
(0, 1)
$ ./smaller-than-bag -v 9 4 9 2
: 2: smaller: 0
: 4: smaller: 1
: 9: smaller: 2
(2, 1, 2, 0)
[
[1,0,0,1],
[0,1,0,2],
[0,0,1,3]
]
For more information check out this wikipedia article.
Example 1:
Input: $M = [
[1, 1, 0],
[0, 1, 0],
[0, 0, 0]
]
Output: 0
Input: $M = [
[0, 1,-2, 0, 1],
[0, 0, 0, 1, 3],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]
]
Output: 1
Input: $M = [
[1, 0, 0, 4],
[0, 1, 0, 7],
[0, 0, 1,-1]
]
Output: 1
Input: $M = [
[0, 1,-2, 0, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 3],
[0, 0, 0, 0, 0]
]
Output: 0
Input: $M = [
[0, 1, 0],
[1, 0, 0],
[0, 0, 0]
]
Output: 0
Input: $M = [
[4, 0, 0, 0],
[0, 1, 0, 7],
[0, 0, 1,-1]
]
Output: 0
I have specified matrices on the command line in quite a lot of challenges, last time in «weakest-row» in Weakest Split with Raku (Weekly Challenge #253).
I have chosen to write seperate procedures for each rule, and started with a dummy program like this.
File: reduced-row-dummy
#! /usr/bin/env raku
unit sub MAIN ($string = "1 0 0 1 | 0 1 0 2 | 0 0 1 3", :v(:$verbose)); # [1]
my $matrix = $string.split("|")>>.words>>.Int>>.Array; # [2]
die "The rows must have the same size" unless [==] $matrix>>.elems; # [3]
say + (rule1($matrix) && rule2($matrix) && rule3($matrix) && rule4($matrix));
# [4]
sub rule1 ($matrix)
{
return True;
}
sub rule2 ($matrix)
{
return True;
}
sub rule3 ($matrix)
{
return True;
}
sub rule4 ($matrix)
{
return True;
}
[1] A default matrix, used if the user does not supply one on the command line.
[2] Turn the matrix string into a two dimentional array.
[3] Ensure that all the rows have the same length.
[4] Print «1» if all the rules are
satisfied, and «0» if not. The numeric coercion prefix + coerces the
Boolean value to an integer for us.
See
docs.raku.org/routine/+ for
more information about the Numeric Coercion Prefix Operator +.
Running this dummy program is not very exciting, so let us skip that part...
Then I implemented the 4 rules:
sub rule1 ($matrix)
{
for ^$matrix.elems -> $row-index # [1]
{
for $matrix[$row-index] -> $value # [2]
{
next if $value == 0; # [3]
last if $value == 1; # [4]
say ": Falsified by rule 1 (on row $row-index)" if $verbose;
return False; # [5]
}
}
say ": Verified by rule 1" if $verbose;
return True; # [6]
}
[1] Iterate over the rows, by index.
[2] Iterate over the columns, also by index.
[3] Skip initial zeroes.
[4] Skip the row when we reach a 1.
[5] We have a row that falsifes rule 1. We return that failure.
[6] All is well.
sub rule2 ($matrix)
{
my $ok = [>=] $matrix.map( { $_.all == 0 ?? 0 !! 1 }); # [1]
say ": Falsified by rule 2" if $verbose && ! $ok;
say ": Verified by rule 2" if $verbose && $ok;
return $ok; # [2]
}
[1] Use the Reduction Metaoperator
[] in combination with <= (the less than or
equal operator) to ensure that rows containing only zeroes (reduced to 0
by the map) come before rows that does not (reduced to 1 by the
same map).
See
docs.raku.org/language/operators#Reduction_metaoperators for more
information about the Reduction Metaoperator [].
[2] Return the result.
sub rule3 ($matrix)
{
for ^($matrix.elems -1) -> $row-index # [1]
{
next if all($matrix[$row-index]) == 0; # [2]
next if all($matrix[$row-index + 1]) == 0; # [2a]
my $pos1 = get-one($matrix[$row-index]); # [3]
my $pos2 = get-one($matrix[$row-index +1]); # [3a]
if $pos1 >= $pos2 # [4]
{
say ": Falsified by rule 3 (Row $row-index Col $pos1 vs Row \
{ $row-index + 1 } Col: $pos2" if $verbose;
return False; # [4a]
}
}
say ": Verified by rule 3" if $verbose;
return True; # [5]
}
sub get-one (@row) # [11]
{
for ^@row.elems -> $index # [12]
{
return $index if @row[$index] == 1; # [13]
die "Not a leading 0" unless @row[$index] == 0; # [14]
}
die "No 1 in row"; # [15]
}
[1] Iterate over the row indices, except the last one (as we do a +1 in [3]).
[2] Skip if the current row or the next [2a] one contains zeroes only.
[3] Get the position of the leading 1 in the current and next rows [3a].
[4] Farther to the right? If not, return failure.
[5] Success is the absence of failure.
[11] Helper procedure returning the index of the leading 1 on a given row.
[12] Iterate over the elements in the row, by index.
[13] Return the index if we encounter a 1.
[14] Blow up iw we encounter enything but a leading zero.
[15] Blow up we we did not find a 1.
sub rule4 ($matrix)
{
for ^$matrix.elems -> $row-index # [1]
{
next if all($matrix[$row-index]) == 0; # [2]
for ^$matrix[$row-index].elems -> $col-index # [3]
{
next if $matrix[$row-index][$col-index] == 0; # [4]
unless $matrix[$row-index][$col-index] == 1 # [5]
{
say ": Falsified by rule 4 (First non-zero is not one; \
row $row-index Col: $col-index" if $verbose;
return False; # [5a]
}
my @col = $matrix[*;$col-index]; # [6]
my $col = @col.Bag; # [7]
unless $col.keys.elems == 2 && $col{1} == 1 && $col{0} > 0 # [8]
{
say ": Falsified by rule 4 (row $row-index column $col-index)"
if $verbose;
return False; # [9]
}
last; # [10]
}
}
say ": Verified by rule 4" if $verbose;
return True; # [11]
}
[1] Iterate over the rows, by index.
[2] Skip rows that contains zeroes only.
[3] Iterate over the columns, also by index.
[4] Continue as long as we encounter zeroes only.
[5] The first non-zero value should be 1. If not, rule 4 has failed.
[6] Get all the values from the column. Note the syntax:
[*;$col-index].
[7] Turn that column data into a Bag.
[8] We should have two distinct values in the Bag, one instance
of 1 and the rest of 0.
[9] If not, we have failed rule 4.
[10] Skip the rest of the inner loop, as the Bag took care of
the rest of the column values after the first 1.
[11] The absence of failure means success.
Running it, with verbose mode to see where it fails - when it fails:
$ ./reduced-row-echelon -v "1 0 0 1 | 0 1 0 2 | 0 0 1 3"
: Verified by rule 1
: Verified by rule 2
: Verified by rule 3
: Verified by rule 4
1
$ ./reduced-row-echelon -v "1 1 0 | 0 1 0 | 0 0 0"
: Verified by rule 1
: Verified by rule 2
: Verified by rule 3
: Falsified by rule 4 (row 1 column 1)
0
$ ./reduced-row-echelon -v "0 1 -2 0 1 | 0 0 0 1 3 | 0 0 0 0 0 | 0 0 0 0 0"
: Verified by rule 1
: Verified by rule 2
: Verified by rule 3
: Verified by rule 4
1
$ ./reduced-row-echelon -v "1 0 0 4 | 0 1 0 7 | 0 0 1 -1"
: Verified by rule 1
: Verified by rule 2
: Verified by rule 3
: Verified by rule 4
1
$ ./reduced-row-echelon -v "0 1 -2 0 1 | 0 0 0 0 0 | 0 0 0 1 3 | 0 0 0 0 0"
: Verified by rule 1
: Falsified by rule 2
0
$ ./reduced-row-echelon -v "0 1 0 | 1 0 0 | 0 0 0"
: Verified by rule 1
: Verified by rule 2
: Falsified by rule 3 (Row 0 Col 1 vs Row 1 Col: 0
0
$ ./reduced-row-echelon -v "4 0 0 0 | 0 1 0 7 | 0 0 1 -1"
: Falsified by rule 1 (on row 0)
0
Looking good.
A 1x1 matrix is allowed, but probably not very useful:
$ ./reduced-row-echelon -v "0"
: Verified by rule 1
: Verified by rule 2
: Verified by rule 3
: Verified by rule 4
1
$ ./reduced-row-echelon -v "1"
: Verified by rule 1
: Verified by rule 2
: Verified by rule 3
: Falsified by rule 4 (row 0 column 0)
0
$ ./reduced-row-echelon -v "2"
: Falsified by rule 1 (on row 0)
0
And that's it.