# Rafraîchissoir

By Shahed Nooshmand

# Perl Weekly Challenge: week 63

Make way for the champion.

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

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.