The Same Toeplitz with Raku
[231] Published 6. April 2023.This is my response to The Weekly Challenge #211.
Challenge #211.1: Toeplitz 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
Input: @matrix = [ [1, 2, 3],
[3, 2, 1],
]
Output: false
See e.g. en.wikipedia.org/wiki/Toeplitz_matrix for more information about Toeplitz and his Matrix.
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
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.
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.