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:

https://theweeklychallenge.org/