Rafraîchissoir

By Shahed Nooshmand

Perl Weekly Challenge: week 63

Make way for the champion.

Task #1

Define sub last_word($string, $regexp) that returns the last word matching $regexp found in the given string, or undef if the string does not contain a word matching $regexp.

Here’s the function definition:

sub last-word(Str $string, Regex $regex) {
	.return when $regex for $string.words.reverse
}

It stops looping as soon as it finds a word that matches. If it never finds such word, it doesn’t return anything, which evaluates to Nil. (There is no undef in Raku.)

Task #2

Given a word made up of an arbitrary number of x and y characters, that word can be rotated as follows: For the ith rotation (starting at i = 1), i % length(word) characters are moved from the front of the string to the end. Thus, for the string xyxx, the initial (i = 1) % 4 = 1 character (x) is moved to the end, forming yxxx. On the second rotation, (i = 2) % 4 = 2 characters (yx) are moved to the end, forming xxyx, and so on. […]

Your task is to write a function that takes a string of xs and ys and returns the minimum non-zero number of rotations required to obtain the original string.

This is a rather straightforward problem with a rather straightforward solution. You keep looping and modifying the string until you get back where you started — a repeat-until. But that’s not what I’m going to do. I’m going to solve this problem mathematically.

Suppose the number we’re looking for, i.e. the number of rotations necessary, is \(r\). Considering the fact that whole rotations and no roation are practically the same, by the time we’re done we’ve had made \(\sum\limits_{i=1}^r i = \frac{r(r+1)}{2}\) character transformations. Therefore, it seems that for any string of length \(n\), the number of rotations \(r\) is the smallest positive integer to satisfy \(n \mid \frac{r(r+1)}{2}\) (i.e. “\(n\) divides \(\frac{r(r+1)}{2}\)”). Knowing this, finding \(r\) is much easier.

More precisely, if a string of length \(n\) is the concatenation of \(\frac{n}{p}\) equal strings of length \(p\), it’s enough to rotate the first \(p\)-substring, because the rest of the string doesn’t need to change. So, the smallest \(r\) for \(n\) is the smallest \(r\) for the smallest \(p\).

Here’s an example:

$$xyxyxy \rightarrow yxyxyx \rightarrow yxyxyx \rightarrow xyxyxy$$

And here’s the script:

#!/usr/bin/env raku

say find-r “xyxyxy”;

sub find-r($string) {
	my $p = find-p $string;
	.return when $_ × ($_ + 1) ÷ 2 %% $p for 1..∞
}

sub find-p($string) {
	my $n = chars $string;
	.return when $string.substr(^$_) x $n ÷ $_ eq $string for |(1..$n ÷ 2).grep($n %% *), $n
}

Which gives 3.