Peter
Peter Campbell Smith

Striped arrays
and balanced splits

Weekly challenge 211 — 3 April 2023

Week 211: 3 Apr 2023

Task 1

Task — 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.

Analysis

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.

Try it 

Example: [[3, 4, 5], [2, 3, 4], [1, 2, 3]]

Script


#!/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');
}


Output


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