by Arne Sommer

The Same Toeplitz with Raku

[231] Published 6. April 2023.

This is my response to The Weekly Challenge #211.

Challenge #211.1: Toeplitz Matrix

You are given a matrix `m x n`.

Write a script to find out if the given matrix is `Toeplitz Matrix`.

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.

Example 1: ```Input: @matrix = [ [4, 3, 2, 1], [5, 4, 3, 2], [6, 5, 4, 3], ] Output: true ``` Example 2: ```Input: @matrix = [ [1, 2, 3], [3, 2, 1], ] Output: false ```

I have chosen to look for values that do not match (and exit with «false»). If we do not find any errors at the end of the program, we have a Toeplitz Matrix.

My approach can be explained like this:

 The original matrix from example 1

The first diagonal:

 Start at the first row, with the last entry (1; marked with blue) and save that as the current diagonal value (1; black border). Remove the value, and check for the next diagonal. It is outside of the matrix (pink box), so this diagonal is finished. (One element in the diagonal, which trivially has the same value as itself.)

The second diagonal:

 Start at the first row, with the last entry (2; marked with blue) and save that as the current diagonal value (2; black border). Remove that value, and check the next diagonal (2; marked with blue). The value is correct, so we go on. Remove that value, and check the next diagonal. It is outside of the matrix (pink box), so this diagonal is finished. (We had two elements in this diagonal, and they all have the same value of 2.)

The third diagonal:

 Start at the first row, with the last entry (3; marked with blue) and save that as the current diagonal value (3; black border) Remove that value, and check the next diagonal (3; marked with blue). The value is correct, so we go on. Remove that value, and check the next diagonal (3; marked with blue). The value is correct, so we go on. Remove that value, and check the next diagonal. It is outside of the matrix (pink box), so this diagonal is finished. (We had three elements in this diagonal, and they all have the same value of 3.)

The fourth diagonal:

 Start at the first row, with the last entry (4; marked with blue) and save that as the current diagonal value (4; black border). Remove that value, and check the next diagonal (4; marked with blue). The value is correct, so we go on. Remove that value, and check the next diagonal (4; marked with blue). The value is correct, so we go on. Remove that value, and check the next diagonal. It is outside of the matrix (pink box), so this diagonal is finished. (We had three elements in this diagonal, and they all have the same value of 4.)

The former first row is empty, so has been removed.

The fifth diagonal:

 Start at the first row, with the last entry (5; marked with blue) and save that as the current diagonal value (5; black border) Remove that value, and check the next diagonal (5; marked with blue). The value is correct, so we go on Remove that value, and check the next diagonal. it is outside of the matrix (pink box), so this diagonal is finished. (We had two elements in this diagonal, and they all have the same value of 5.)

The sixth and final diagonal:

 A single value, which is ok. (It is trivially the same as itself.)

You may have noticed that the diagonal indices (counted from 1 to 6) correspond with the values. This is an unintended benefit of counting the diagonals from the right.

It is possible to do this traversal without chopping off values, but that requires some more bookkeeping.

Then the program doing this:

File: toeplitz-matrix ```#! /usr/bin/env raku unit sub MAIN (Str \$matrix = "4 3 2 1 | 5 4 3 2 | 6 5 4 3", # [1] :v(:\$verbose)); my @matrix = \$matrix.split("|")>>.words>>.Array; # [2] my @size = @matrix>>.elems; # [3] die "Must have at least 2 rows" unless @size.elems >= 2; # [4] die "The rows must have the same size" unless [==] @size; # [5] while @matrix.elems # [6] { @matrix.shift if @matrix[0].elems == 0; # [7] last unless @matrix.elems; # [8] my \$row = 0; # [9] my \$col = @matrix[\$row].end; # [10] my \$value = @matrix[\$curr-row].pop; # [11] say ": Row:0 { @matrix.raku } -> \$value (last value removed from row)" if \$verbose; loop # [12] { \$curr-row++; # [13] \$curr-col++; # [13a] last unless defined @matrix[\$curr-row]; # [14] last unless defined @matrix[\$curr-row][\$curr-col]; # [15] my \$new = @matrix[\$curr-row].pop; # [16] say ": Row:\$curr-row { @matrix.raku } -> \$new (last value \ removed from row)" if \$verbose; unless \$value eq \$new # [17] { say 'false'; # [17a] exit; # [17b] } } } say 'true'; # [18] ```

[1] A default matrix, with «|» to separate the rows, and spaces to separate the individual values.

[2] Split the matrix string into a two dimentional array. The `split` sets up an array of row strings, and `>>.words` transforms each row into individual values. The rows are sequence objects, which we cannot manipulate (i.e. remove items from them) later on, so we coerce them to arrays with `>>.Array`.

[3] Get the number of rows.

[4] Insist on at least two rows.

[5] All the rows must have the same size, and the Reduction Metaoperator `[]` in combination with `==` checks this for us.

See docs.raku.org/language/operators#Reduction_metaoperators for more information about the Reduction Metaoperator `[]`.

[6] As long as we have more rows, and thus diagonals.

[7] Empty first row? Remove it. This is a possible result of `pop` (in [12] or [16]), which leaves an empty array when we remove the very last item in it.

[8] Check for the end (empty matrix), which we get if we just removed the last row in [7].

[9] Start at the first row.

[10] Start at the end of that first row, and we get the index with `end`.

See docs.raku.org/routine/end for more information about `end`.

[11] Get the current value (and remove it from the end of the matrix row) with `pop`.

See docs.raku.org/routine/pop for more information about `pop`.

[12] Then a loop without exit conditions up front.

[13] Move the pointer to the next row and column [13a].

[14] Have we gone below the matrix? If so, then we are done with this diagonal.

[15] Have we gone to the right of the row? if so, we are done with this diagonal.

[16] Get the value at the new position (and remove it from the matrix).

[17] Did we get the wxpected value? If not, print «false» and exit the program.

[18] If we have not failed when we reach this point, then we have a Toeplitz Matrix. Say so.

Running it:

```\$ ./toeplitz-matrix true \$ ./toeplitz-matrix "1 2 3 | 3 2 1" false ```

Verbose mode is sort of helpful:

```\$ ./toeplitz-matrix -v : Row:0 [["4", "3", "2"], ["5", "4", "3", "2"], ["6", "5", "4", "3"]] -> 1 (last value removed from row) : Row:0 [["4", "3"], ["5", "4", "3", "2"], ["6", "5", "4", "3"]] -> 2 (last value removed from row) : Row:1 [["4", "3"], ["5", "4", "3"], ["6", "5", "4", "3"]] -> 2 (last value removed from row) : Row:0 [["4"], ["5", "4", "3"], ["6", "5", "4", "3"]] -> 3 (last value removed from row) : Row:1 [["4"], ["5", "4"], ["6", "5", "4", "3"]] -> 3 (last value removed from row) : Row:2 [["4"], ["5", "4"], ["6", "5", "4"]] -> 3 (last value removed from row) : Row:0 [[], ["5", "4"], ["6", "5", "4"]] -> 4 (last value removed from row) : Row:1 [[], ["5"], ["6", "5", "4"]] -> 4 (last value removed from row) : Row:2 [[], ["5"], ["6", "5"]] -> 4 (last value removed from row) : Row:0 [[], ["6", "5"]] -> 5 (last value removed from row) : Row:1 [[], ["6"]] -> 5 (last value removed from row) : Row:0 [[],] -> 6 (last value removed from row) true \$ ./toeplitz-matrix -v "1 2 3 | 3 2 1" : Row:0 [["1", "2"], ["3", "2", "1"]] -> 3 (last value removed from row) : Row:0 [["1"], ["3", "2", "1"]] -> 2 (last value removed from row) : Row:1 [["1"], ["3", "2"]] -> 1 (last value removed from row) false ```

We are not restricted to integers, or even numeric values:

```\$ ./toeplitz-matrix -v "A B * | 1 A B" : Row:0 [["A", "B"], ["1", "A", "B"]] -> * (last value removed from row) : Row:0 [["A"], ["1", "A", "B"]] -> B (last value removed from row) : Row:1 [["A"], ["1", "A"]] -> B (last value removed from row) : Row:0 [[], ["1", "A"]] -> A (last value removed from row) : Row:1 [[], ["1"]] -> A (last value removed from row) : Row:0 [[],] -> 1 (last value removed from row) true ```

Challenge #211.2: Split Same Average

You are given an array of integers.

Write a script to find out if the given can be split into two separate arrays whose average are the same.

Example 1: ```Input: @nums = (1, 2, 3, 4, 5, 6, 7, 8) Output: true We can split the given array into (1, 4, 5, 8) and (2, 3, 6, 7). The average of the two arrays are the same i.e. 4.5. ``` Example 2: ```Input: @list = (1, 3) Output: false ```

File: split-same-average ```#! /usr/bin/env raku unit sub MAIN (*@int where @int.elems > 1 && @int.all ~~ UInt && @int.all > 0, :v(:\$verbose)); # [1] for @int.permutations.unique -> @candidate # [2] { say ": Candidate: @candidate[]" if \$verbose; my @right = @candidate.clone; # [3] my @left; # [4] while @right.elems > 1 # [5] { @left.push: @right.shift; # [6] my \$left-avg = @left.sum / @left.elems; # [7] my \$right-avg = @right.sum / @right.elems; # [8] say ": - Comparing @left[] (avg: \$left-avg) <=> @right[] \ (avg: \$right-avg)" if \$verbose; if \$left-avg == \$right-avg # [9] { say 'true'; # [9a] exit; # [9b] } } } say 'false'; # [10] ```

[1] Ensure at least two elements (so that we can split them), they must all be unsigned integers, and also be larger than zero.

[2] Iterate over all the unique permutations (i.e. different sorting order of the values).

[3] The right part of the split, starting off with everything. The `clone` is there so that we can change the array afterwards.

[4] The left part, starting off by stealing the first value from the right part.

[5] As long as we have more than 1 element left in the right part:

[6] • Move one element from the right to the left.

[7] • Compute the left average.

[8] • Compute the right average.

[9] • Are they equal? If so print «true» [9a] and exit [9b].

[10] We have tried all the permutations, without success. Then we have failed. Say so.

Running it:

```\$ ./split-same-average 1 2 3 4 5 6 7 8 true \$ ./split-same-average 1 3 false ```

Verbose mode is to the point, albeit very verbose for the first one (so I have removed about 480 rows of output):

```\$ ./split-same-average -v 1 2 3 4 5 6 7 8 : Candidate: 1 2 3 4 5 6 7 8 : - Comparing 1 (avg: 1) <=> 2 3 4 5 6 7 8 (avg: 5) : - Comparing 1 2 (avg: 1.5) <=> 3 4 5 6 7 8 (avg: 5.5) : - Comparing 1 2 3 (avg: 2) <=> 4 5 6 7 8 (avg: 6) : - Comparing 1 2 3 4 (avg: 2.5) <=> 5 6 7 8 (avg: 6.5) : - Comparing 1 2 3 4 5 (avg: 3) <=> 6 7 8 (avg: 7) : - Comparing 1 2 3 4 5 6 (avg: 3.5) <=> 7 8 (avg: 7.5) : - Comparing 1 2 3 4 5 6 7 (avg: 4) <=> 8 (avg: 8) : Candidate: 1 2 3 4 5 6 8 7 : - Comparing 1 (avg: 1) <=> 2 3 4 5 6 8 7 (avg: 5) : - Comparing 1 2 (avg: 1.5) <=> 3 4 5 6 8 7 (avg: 5.5) : - Comparing 1 2 3 (avg: 2) <=> 4 5 6 8 7 (avg: 6) : - Comparing 1 2 3 4 (avg: 2.5) <=> 5 6 8 7 (avg: 6.5) : - Comparing 1 2 3 4 5 (avg: 3) <=> 6 8 7 (avg: 7) : - Comparing 1 2 3 4 5 6 (avg: 3.5) <=> 8 7 (avg: 7.5) : - Comparing 1 2 3 4 5 6 8 (avg: 4.142857) <=> 7 (avg: 7) ... : Candidate: 1 2 3 6 7 5 8 4 : - Comparing 1 (avg: 1) <=> 2 3 6 7 5 8 4 (avg: 5) : - Comparing 1 2 (avg: 1.5) <=> 3 6 7 5 8 4 (avg: 5.5) : - Comparing 1 2 3 (avg: 2) <=> 6 7 5 8 4 (avg: 6) : - Comparing 1 2 3 6 (avg: 3) <=> 7 5 8 4 (avg: 6) : - Comparing 1 2 3 6 7 (avg: 3.8) <=> 5 8 4 (avg: 5.666667) : - Comparing 1 2 3 6 7 5 (avg: 4) <=> 8 4 (avg: 6) : - Comparing 1 2 3 6 7 5 8 (avg: 4.571429) <=> 4 (avg: 4) : Candidate: 1 2 3 6 7 8 4 5 : - Comparing 1 (avg: 1) <=> 2 3 6 7 8 4 5 (avg: 5) : - Comparing 1 2 (avg: 1.5) <=> 3 6 7 8 4 5 (avg: 5.5) : - Comparing 1 2 3 (avg: 2) <=> 6 7 8 4 5 (avg: 6) : - Comparing 1 2 3 6 (avg: 3) <=> 7 8 4 5 (avg: 6) : - Comparing 1 2 3 6 7 (avg: 3.8) <=> 8 4 5 (avg: 5.666667) : - Comparing 1 2 3 6 7 8 (avg: 4.5) <=> 4 5 (avg: 4.5) true \$ ./split-same-average -v 1 3 : Candidate: 1 3 : - Comparing 1 (avg: 1) <=> 3 (avg: 3) : Candidate: 3 1 : - Comparing 3 (avg: 3) <=> 1 (avg: 1) false ```

Note that even though we got rid of duplicates, we still have a lot of left and right arrays that have the same values (but not the same internal order).

And that's it.