The Weekly Challenge 374

CRC Home

The Weekly Challenge 374

Andrea Piseri

andrea.piseri@gmail.com

19/05/2026

I had some fun solving The Weekly Challenge #374, here’s how it went.

Table of Contents

Task 1

Ok but like, how does it work?

Better solution

Parallel solution?

How is this parallel?

Task 1

asks us to find all vowel substrings of a given string, where a vowel substring is any substring that:

only contains vowels, and

contains all vowels. [1]

I’m solving in K, and the first tempting approach is to just find all substrings and<br>filter by the appropriate predicate. Is it short? Yes. Fast? Depends on the string’s length, but I’m tempted to say no.

solve: ({~|/(|/^?)/'1|:\(x;"aeiou")}')#,/,\'|',\|:

solve "aeiou"<br>solve "aaeeeiioouu"<br>solve "aeiouuaxaeiou"<br>solve "uaeiou"<br>solve "aeioaeioa"

Ok but like, how does it work?

For the reader in a hurry, if you’re only interested in good and readable solutions skip ahead to the next section. I promise it gets better.

,/,\'|',\|: is "all substrings": it works by composing a bunch of operations, right to left.

| is reverse, but for k grammar reasons it needs to be spelled |: in this context to disambiguate with its binary use

,\ is a scan with an operation of concatenation, so it gives all prefixes (but we’re reversed, so it’s actually the reverses of all suffixes)

|' is reverse each, so now we have all suffixes

,\' same as before, but on each: we have all prefixes of each suffix

,/ is fold with concatenation, so we have all prefixes of all suffixes. Hooray!

{~|/(|/^?)/'1|:\(x;"aeiou")} is the vowel-string predicate:

{ } introduce a unary function where x is the argument.

1|:\(x;"aeiou") generates the two pairs (x;"aeiou") and ("aeiou";x)

(|/^?)/' for each pair, checks if any elements of the right element are not in the left element, so if there’s anything in the set-wise difference

~|/ checks if both results are false.

({~|/(|/^?)/'1|:\(x;"aeiou")}')#,/,\'|',\|: keeps from all substrings only those for which the predicate is true.

Not really sophisticated, but it works. Now for solving the problem efficiently, which is the actually fun challenge:

Better solution

We’re aiming for a solution that is as close to being linear in both time and space as possible, however that’s not possible in this case<br>because the output itself might be larger than that. For example the string "aeiou…​u" has an all vowel substring for each length<br>between 5 and the total length of the input. "a…​aeiou…​u" has a quadratic number of substrings, and the sum of their lengths is<br>cubic in the length of the argument. Ok, we allow ourselves a linear factor in the total size of the result.

The core of this solution is to find, for each position where a substring could end, for which starting positions the<br>resulting substrings are all-vowel substrings. It’s easy to see that this is a contiguous range.

Suppose we are at position \(i\) in the string: let \(j_c\) be the latest position of a consonant before or at \(i\), and<br>\(j_a,j_e,j_i,j_o,j_u\) the latest positions of each respective vowel before or at \(i\).<br>then it follows that any substring ending after the letter at \(i\) must start strictly after \(j_c\) and at or before all of the<br>\(j_a,j_e,j_i,j_o,j_u\). This would give a fairly straight-forward sequential implementation like:

void substrings(char const *s) {<br>static char const v[] = "aeiou";<br>int j[6] = {-1,-1,-1,-1,-1,-1};<br>for (int i = 0; s[i]; ++i) {<br>int k = strchrnul(v,s[i]) - v;<br>j[k] = i;<br>printf("%c |%2d %2d %2d %2d %2d %2d",s[i],j[0],j[1],j[2],j[3],j[4],j[5]);<br>if (k 5) {<br>// can't contain a consonant<br>int begin = j[5] + 1;<br>// must contain all vowels<br>int end = fold_min(j, 5) + 1;<br>for (; begin end; ++begin) {<br>printf(" %.*s", i + 1 - begin, s + begin);<br>putchar('\n');

We can see the values of the j variable track the last seen occurrence of each character class, forming this table as we scan across the<br>string "aeiouuaxaeiou".

a | 0 -1 -1 -1 -1 -1<br>e | 0 1 -1 -1 -1 -1<br>i | 0 1 2 -1 -1 -1<br>o | 0 1 2 3 -1 -1<br>u | 0 1 2 3 4 -1 aeiou<br>u | 0 1 2 3 5 -1 aeiouu<br>a | 6 1 2 3 5 -1 aeiouua eiouua<br>x | 6 1 2 3 5 7<br>a | 8 1 2 3 5 7<br>e | 8 9 2 3 5 7<br>i | 8 9 10 3 5 7<br>o | 8 9 10 11 5 7<br>u | 8 9 10 11 12 7 aeiou

But sequential is not what we’re going for here, so what can we do? let’s write some K.

Parallel solution?

x: "aeiouuaxaeiou"

First, we would like to classify (?) all characters as either one of the vowels, or a consonant.<br>we prepend (,) one element for each of the character classes for good measure, we’ll see later how that<br>helps.

class: "aeiou"?"aeiouz",x

0 1 2 3 4 0N 0 1 2 3 4 4 0 0N 0 1 2 3 4

Then we make a dictionary (=) out of that, so that we have the sorted list of<br>positions at which each class occurs. we know the order of the keys because we prepended the elements earlier, so we<br>can just take the values. Also our positions are relative to the padded string, so we subtract the length of the prefix.<br>Remember the first five position lists are for the vowels,...