# 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.

## Solution

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

#### perl

`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;

@r

}

## Bonus Solution

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

#### perl

`sub shortest_distance_2 {`

my($v,$c) = (1e9,pop);

grep { $_ < 1e9 }

reverse

map { $_ ? $_ <= $v ? $_ : ++$v : ($v=0) }

reverse

map { $_ eq $c ? ($v=0) : ++$v }

split //,

pop

}

## 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]

## Solution

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..$#_`

)

#### perl

`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: