Peter
Peter Campbell Smith

Closest sum

Weekly challenge 248 — 18 December 2023

Week 248: 18 Dec 2023

Task 2

Task — Submatrix sum

You are given a NxM matrix A of integers. Write a script to construct a (N-1)x(M-1) matrix B having elements that are the sum over the 2x2 submatrices of A:

b[i,k] = a[i,k] + a[i,k+1] + a[i+1,k] + a[i+1,k+1]

Examples


Example 1
Input: $a = [
              [1,  2,  3,  4],
              [5,  6,  7,  8],
              [9, 10, 11, 12]
            ]

Output: $b = [
               [14, 18, 22],
               [30, 34, 38]
             ]

Example 2
Input: $a = [
              [1, 0, 0, 0],
              [0, 1, 0, 0],
              [0, 0, 1, 0],
              [0, 0, 0, 1]
            ]

Output: $b = [
               [2, 1, 0],
               [1, 2, 1],
               [0, 1, 2]
             ]

Analysis

I couldn't think of anything better than just iterating over rows and columns of the output matrix, calculating the values one by one.

I chose to represent both matrices as references to an array of references to arrays. So an element is accessed, for example, as $ref->[$r]->[$c]. It would be also be possible to use Perl's (approximation to) two-dimensional arrays, for example as
$arr[$r][$c]: it isn't obvious to me whether either method would be faster than the other.

Perhaps the hardest part of this task is printing out the arrays so that they line up nicely.

Try it 

Try running the script with any input:



example: [1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]

Script


#!/usr/bin/perl

use v5.16;    # The Weekly Challenge - 2023-12-18
use utf8;     # Week 242 task 2 - Submatrix sum
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

submatrix_sum([1,  2,  3,  4],
              [5,  6,  7,  8],
              [9, 10, 11, 12]);
submatrix_sum([37, 99, 43, 87, 22, 77,  0, 51, 20],
              [18,  5, 67, 39, 52, 40, 39, 77,  1],
              [93, 45, 34, 87, 12, 34, 15, 90, 22],
              [11, 84, 45, 36, 75, 83, 40, 58, 89]);

sub submatrix_sum {
    
    my ($in, $cols, $rows, $c, $r, $out, $chars, $max);
    
    # initialise
    $in = \@_;
    $cols = @{$in->[0]} - 1;
    $rows = @$in - 1;
    $max = 0;
    
    # loop over rows and columns calculating sum
    for $r (0 .. $rows - 1) {
        for $c (0 .. $cols - 1) {
            $out->[$r]->[$c] = $in->[$r]->[$c] + $in->[$r + 1]->[$c] + 
                $in->[$r]->[$c + 1] + $in->[$r + 1]->[$c + 1];
            $chars = length($out->[$r]->[$c]);
            $max = $chars if $chars > $max;
        }
    }
    
    # output the required data
    print_matrix('Input:  [', $in, $max);
    print_matrix('Output: [', $out, $max);
}


sub print_matrix {
    
    my ($legend, $matrix, $j, $out, $max);

    ($legend, $matrix, $max) = @_;
    
    # format rows of matrix with numbers of equal width
    $out = '';
    for $j (0 .. @$matrix - 1) {
        $out .= qq[$legend] . join(', ', @{$matrix->[$j]}) . qq(]\n);
        $legend = '        [';
    }
    $out =~ s|(\d+)|sprintf("%${max}d", $1)|ge;
    say $out;
}
        

Output


Input:  [ 1,  2,  3,  4]
        [ 5,  6,  7,  8]
        [ 9, 10, 11, 12]

Output: [14, 18, 22]
        [30, 34, 38]

Input:  [ 37,  99,  43,  87,  22,  77,   0,  51,  20]
        [ 18,   5,  67,  39,  52,  40,  39,  77,   1]
        [ 93,  45,  34,  87,  12,  34,  15,  90,  22]
        [ 11,  84,  45,  36,  75,  83,  40,  58,  89]

Output: [159, 214, 236, 200, 191, 156, 167, 149]
        [161, 151, 227, 190, 138, 128, 221, 190]
        [233, 208, 202, 210, 204, 172, 203, 259]

 

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