Programming challenges

The Weekly Challenge - 248 (December 18th 2023)

Task #1: Shortest Distance

You are given a string and a character in the given string. Write a script to return an array of integers of size same as length of the given string such that: distance[i] is the distance from index i to the closest occurence of the given character in the given string.


There are many different ways to solve this problem – but I’m going to demonstrate and O(n) solution.

Part 1 – Sweep right

We first create an array which is the distance of the current letter to the last seen “target” letter. Or very large if none to the left.

Part 2 – Sweep left

Now to go back again we start from the right hand side and sweep left. If the value of the entry is greater than 1+ value of the entry to the right we then set it to 1 + value of the entry to the right… And keep on going.

We then have the answer we are looking for – and it is in O(n) steps


sub shortest_distance {
my($v,$c) = (1e9,pop);
## sweep right....
my @r = map { $_ eq $c ? $v=0 : ++$v} split //, $_[0];
return if $v>=1e9; ## No matches...
## sweep left....
( $r[$_-1] > $r[$_]+1 ) && ( $r[$_-1]=$r[$_]+1 ) for reverse 1..$#r;

Bonus Solution

Now there is a one-liner – but I’ll leave this up to you to work out why this works…


sub shortest_distance_2 {
my($v,$c) = (1e9,pop);
grep { $_ < 1e9 }
map { $_ ? $_ <= $v ? $_ : ++$v : ($v=0) }
map { $_ eq $c ? ($v=0) : ++$v }
split //,

Task #2: 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 2×2 submatrices of A, b[i,k] = a[i,k] + a[i,k+1] + a[i+1,k] + a[i+1,k+1]


There isn’t much to write about this – it’s simply a map of a map to handle the convolution.

Just note that instead of using $_ & $_+1 and starting at 0 and going to size-2 we can use $_-1 & $_ and go from 1 .. size -1 (or in Perl parlance 1..$#_)


sub submatrix_sum {
map { my $o=$_; [
map { $_[$o][$_ ]+$_[$o-1][$_ ]+
$_[$o][$_-1]+$_[$o-1][$_-1] } 1..$#{$_[0]}
]} 1..$#_

About The Weekly Challenge

The weekly challenge was set up Mohammad Anwar approximately 5 years ago - each Monday two problems are set for the "team" to solve.

These are posted at: