Striped arrays

and balanced splits

Weekly challenge 211 — 3 April 2023

Week 211: 3 Apr 2023

Task 1

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.

A matrix M is Toeplitz if, for every element M(r, c):

- if r >= c then M(r, c) == M(r-c, 0), and
- if r < c then M(r, c) == M(0, c-r)

You can see that easily here:

0 1 2 3 4 +-------------- 0 | . x . . . 1 | + . x . . 2 | . + . x . 3 | . . + . x

- For the x at (2, 3): c > r and there is also an x at (0, 1), and
- for the + at (3, 2): c < r and there is also a + at (1, 0).

We have to check that this is the case for every element of the matrix using two nested loops.

Then, almost the hardest part is printing the input matrix in the format specified by Mohammad, allowing for negative and fractional elements.

Even for quite a large matrix, say 50 x 50, I don't think this will take a significant amount of time, but for a huge matrix - say 1000 by 1000 - it would probably be worth starting by storing the (r, 0) and (0, c) values each in a simple array.

#!/usr/bin/perl use v5.16; # The Weekly Challenge - 2023-04-03 use utf8; # Week 211 task 1 - Toeplitz matrix use strict; # Peter Campbell Smith use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge toeplitz_matrix( [[4, 3, 2, 1], [5, 4, 3, 2], [6, 5, 4, 3]] ); toeplitz_matrix( [[4, 3, 2, 1], [5, 4, 3, 2], [6, 5, 4, 7]] ); toeplitz_matrix( [[37.1, 114, 0, -23.65, 5, 3], [-40, 37.1, 114, 0, -23.65, 5], [-19, -40, 37.1, 114, 0, -23.65], [3, -19, -40, 37.1, 114, 0], [55, 3, -19, -40, 37.1, 114], [0, 55, 3, -19, -40, 37.1], [999, 0, 55, 3, -19, -40]] ); toeplitz_matrix( [[6, 0, 0, 0, 6], [0, 0, 6, 0, 0], [6, 0, 0, 0, 6]] ); sub toeplitz_matrix { my($m, $r, $c, $x, $good); $m = $_[0]; # loop over rows and then columns ROW: for $r (1 .. scalar @$m - 1) { for $c (1. .. scalar @{$m->[0]} - 1) { # check each element against the appropriate edge element $x = $m->[$r]->[$c]; if ($r >= $c) { $good = $x == $m->[$r - $c]->[0] ? 1 : 0; last ROW unless $good; } else { $good = $x == $m->[0]->[$c - $r] ? 1 : 0; last ROW unless $good; } } } # format the output my ($w, $width, $rubric, $prefix, $spaces); # find maximum width of element (as printed by Perl) $w = 0; for $r (0 .. scalar @$m - 1) { for $c (0. .. scalar @{$m->[0]} - 1) { $width = length($m->[$r]->[$c]); $w = $width if $width > $w; } } # construct and output each row of matrix $rubric = ''; $prefix = qq{\nInput: \@matrix = [ [ }; for $r (0 .. scalar @$m - 1) { $rubric .= $prefix; for $c (0. .. scalar @{$m->[0]} - 1) { $spaces = $w + 1 - length($m->[$r]->[$c]); $rubric .= (' ' x $spaces) . $m->[$r]->[$c] . ','; } $rubric =~ s|.$| ]|s; $rubric .= ' ]' if $r == scalar @$m - 1; say $rubric; $rubric = ''; $prefix = ' [ '; } say qq[Output: ] . ($good ? 'true' : 'false'); }

Input: @matrix = [ [ 4, 3, 2, 1 ] [ 5, 4, 3, 2 ] [ 6, 5, 4, 3 ] ] Output: true Input: @matrix = [ [ 4, 3, 2, 1 ] [ 5, 4, 3, 2 ] [ 6, 5, 4, 7 ] ] Output: false Input: @matrix = [ [ 37.1, 114, 0, -23.65, 5, 3 ] [ -40, 37.1, 114, 0, -23.65, 5 ] [ -19, -40, 37.1, 114, 0, -23.65 ] [ 3, -19, -40, 37.1, 114, 0 ] [ 55, 3, -19, -40, 37.1, 114 ] [ 0, 55, 3, -19, -40, 37.1 ] [ 999, 0, 55, 3, -19, -40 ] ] Output: true Input: @matrix = [ [ 6, 0, 0, 0, 6 ] [ 0, 0, 6, 0, 0 ] [ 6, 0, 0, 0, 6 ] ] Output: false

Any content of this website which has been created by Peter Campbell Smith is in the public domain