Perl Weekly Challenge 63 solution

I've been aware of the Perl Weekly Challenge for some time now, but haven't really considered participating until now.

Given that I like puzzles (for the most part) and Perl, it seems to be a good opportunity to mix them regularly. I can't make any promises though! Sometimes I'm just too lazy to do anything productive.

This week challenges are pretty straightforward, so this will be rather short. The link to the challenges is here: https://perlweeklychallenge.org/blog/perl-weekly-challenge-063.

Challenge #1: Last Word

The task is to find the last word of a string that matches the regular expression. The regex can by anything, so it can easily match multiple words at once. Checking the regex against the entire string doesn't say anything about matching it with any individual word. The compiled regex can be treated as a string in Perl, but analyzing its contents (possibly with other regexes) will likely produce ugly code.

My solution is very simple and straightforward: split the string by whitespace to get all the words, reverse the order of the word list and return the first word that matches the regex. The only thing that worries me here is the creation of a full wordlist, while in reality we could really need just the first one. My optimization attempt was to replace the word spliting with extracting the next word from the string using a regex with the /g flag. While that would only use as much memory as the longest word does, it's two times slower than just splitting the list and traversing its reverse. Also, the implementation would be less appealing.

my ($string, $regexp) = @_;
my @words = split /\s+/, $string;

foreach (reverse @words) {
        return $_ if /$regexp/;
}

The code is easy enough to skip the explanation.

Challenge #2: Rotate String

This task involves rotating a string in-place (moving characters from its front to its back). The details are somewhat complicated, so just take a look at the challenges link above for explanation.

This one actually got me thinking for a little while. I was seeking a numerical way to determine the outcome, but to no avail. The maximum number of rotations is easy to determine by just summing the mathematical sequence of numbers up to (but excluding) the number of characters in string. Take a look at this train of thoughts:

  • let x be the length of the string
  • let seq be the sequence of numbers from 1 to x - 1
  • The sum of seq is (x - 1) * ((x - 1) + 1) / 2, which can be written as (x - 1) * x / 2
  • if x is odd, then this sum is divisible by x, because (x - 1) is even, and will "eat up" the number 2 from the divider. x will then be a factor of the sum
  • if x is even, then this sum is not divisible by x, and we need to multiply by 2 to make it divisible

This means that the absolute maximum of rotations to get the same string is x - 1 for odd x and 2 * x - 1 for even x. This is because if we rotate as many characters as the length of the string (or any multiple of it) it's as if we didn't rotate it at all. But then, if the string is composed of just one character, like xxxxx, we always need just one rotation (because it has to be non-zero).

I think this is one of those problems where it's better to just be straightforward and not search for an optimized solution. Every little optimization I've thought of was still requiring producing the rotated strings, so what's the point? And even if there is an optimized solution, the maximum limit of rotations that any string needs to rotate itself back to its original form is linear, so that's not worth the hassle in my opinion. Here is my "be dumb and check everything" solution:

my ($string) = @_;
my $original = $string;
my $length = length $string;

my $rotate = sub {
        substr shift() x 2, $_, $length
};

my $rotation = 0;
while (1) {
        for (1 .. $length) {
                $rotation += 1;
                $string = $rotate->($string);

                return $rotation if $original eq $string;
        }
}

The infinite loop is okay here because we've already proven mathematically that the exit condition is never further than 2 * $length inner loop circles ahead. One thing to note here is that $rotate coderef is using a global variable $_, but since it is anonymous it just shortens its body (no need to handle arguments other than the shift()) and we needn't worry about it surprising anyone in our code (was it to ever be used outside this short example).

See you next week!

Comments? Suggestions? Send to bbrtj.pro@gmail.com
Published on 2020-06-01