Closest sum

Weekly challenge 248 — 18 December 2023

Week 248 - 18 Dec 2023

Task 2

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]

Example 1Input: $a = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12] ] Output: $b = [ [14, 18, 22], [30, 34, 38] ]Example 2Input: $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] ]

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.

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

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]

Peter Campbell Smith is hereby placed in the public domain