Perl Weekly Challenge 64 solution

Second week in a row. So far so good!

This week's challenges were actually very fun to do and a bit harder than the last week: https://perlweeklychallenge.org/blog/perl-weekly-challenge-064.

Challenge #1: Minimum sum path

This is the classic pathfinding problem, but much easier because of no obstacles and no dead ends. Good for me, as I usually sucked at this type of algorithms. The key to good solution here is to avoid recursion, which in this particular case is quite easy to do. I think the easiest way is to reverse the matrix, which is also cloning it in the process. The reversed matrix is better because we want to start looping at the field we want to get to:

my @pathfinder = reverse map { [reverse $_->@*] } $matrix->@*;

We're also using Perl 5.24 postfix dereferencing here, which can be both uglier and prettier than standard dereferencing. Arguably @$_ looks better, but I wanted to be consistent.

With the reversed matrix, we can start looping through it. The basic idea is to assign a value to each field that will be the sum of the best path available for that field. Since we can only move right and down, we only have two alternate options for each field. For border fields that can be also one option or no options for the destination field. We'll be reducing the alternatives with the min function, available in List::Util core module:

foreach my $path_x (keys @pathfinder) {
   foreach my $path_y (keys $pathfinder[$path_x]->@*) {
      my @alternatives;

      push @alternatives, $pathfinder[$path_x][$path_y - 1]
         if $path_y - 1 >= 0;
      push @alternatives, $pathfinder[$path_x - 1][$path_y]
         if $path_x - 1 >= 0;

      if (@alternatives > 0) {
         $pathfinder[$path_x][$path_y] += min @alternatives;
      }
   }
}

After the pathfinder matrix is filled, the task is complete. The correct pathfinding value is available on the field that we want to start on. Since we start in the top left corner, that will be the very last field of the pathfinder matrix. All we have to do is return it:

return $pathfinder[-1][-1];

Challenge #2: Word break

This is a pretty straightforward task of matching an array against a string. We have to check if and in what order the words from an array match the string.

There is one nasty trap one might fall into if not careful, and it is only visible if some words are prefixes of other words. If we have for example both he and help as words to match it can sometimes lead to incorrect matching. To avoid this, the words need to be sorted by their lengths in the descending order:

@words = sort { length $b <=> length $a } @words;

After successfully avoiding that trap, the rest is like a walk in the park. In my solution I arrange the words in order in a new array @found and remove them from the string once matched, so that I always match against the head of the string. Once the string is empty it's necessary to check if we got as many words as in the input - otherwise an empty string will not report an error by returning 0:

my @found;

WORD_LOOP:
while (length $string > 0) {
   for my $word (@words) {

      if (substr($string, 0, length $word) eq $word) {
         $string = substr $string, length $word;
         push @found, $word;
         next WORD_LOOP;
      }
   }

   last;
}

return 0 if @found != @words;
return
   join ", ",
   map { '"' . $_ . '"' }
   @found
;

And that's that!

Comments? Suggestions? Send to feedback@bbrtj.eu
Published on 2020-06-08