by Arne Sommer

Currently Reduced with Raku

[277] Published 25. February 2024.

This is my response to The Weekly Challenge #257.

Challenge #257.1: Smaller than Current

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) ```

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) ```

Challenge #257.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 ```

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:

Rule 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.
File: reduced-row-echelon (partial) ```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.

Rule 2

If there are any rows that consist entirely of zeros, then they are grouped together at the bottom of the matrix.
File: reduced-row-echelon (partial) ```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.

Rule 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.
File: reduced-row-echelon (partial) ```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.

Rule 4

Each column that contains a leading 1 has zeros everywhere else in that column.
File: reduced-row-echelon (partial) ```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.