09 October 2026

Challenge 394

Regular Alternations

Task 1: Alternate Case
Task 2: Alternating Vowels Consonants

Task 1: Alternate Case

You are given a string containing an equal number of uppercase and lowercase English letters.

Write a script to the minimum number of adjacent character swaps needed to turn the given string into an alternate case string.

Example 1

Input: $str = "aAbB"
Output: 0

Example 2

Input: $str = "AAbb"
Output: 1

Swap 1: "AbAb"

Example 3

Input: $str = "AAAbbb"
Output: 3

Swap 1: "AAbAbb"
Swap 2: "AbAAbb"
Swap 3: "AbAbAb"

Example 4

Input: $str = "aABb"
Output: 1

Swap 1: "aAbB"

Example 5

Input: $str = "bBBAaa"
Output: 2

Swap 1: "BbBAaa"
Swap 2: "BbBaAa"

Solution

After fixing the target case for the string’s first letter, each letter may be classified as having the correct case or the opposite case. Identifying the correct case with a 1 and the opposite case with a 0 leads to a binary identification string in the same lengths as the original string.

Swapping two adjacent letters in the string affects the identification string as follows:

When the corresponding characters in the identification string are 00, the result is 11. Both positions are correct afterwards and this is the most desired action.
When the correspondig characters in the identification string are 10 or 01, the swap has no effect on the identification string. Such an action is useless.
When the corresponding characters in the identification string are 11, the result is 00. Though this looks undesirable, it is a useful action if the two 1’s are adjacent to a 0: The “old” zero may be combined with a “new” zero, resulting in the move of a 0 by two places (preferably in the directions towards another 0).

This means that two 0’s that are separated by an even number of 1’s can be corrected by one more swaps than the number of intermediate 1’s and it becomes clear that a pair of 0’s that are separated by an odd number of 1’s cannot be corrected.

The number of required swaps thus can be found by repeatedly correcting even-separated faults.

In the above considerations, the target case was arbitrarily fixed. I don’t see an obvious a priori indication of the preferred target case.

Therefore converting the string into both variants and take the smaller number of required swaps.

Perl

Using bitwise string xor ^. to flip 0 <-> 1 at every other position.

use strict;
use warnings;
use List::Util 'min';
use feature 'bitwise';
use experimental 'signatures';

sub alternate_case ($str) {
    state sub alt ($s) {
        my $c = 0;
        $c += length($&) - 1 while $s =~ s/0(?:11)*0/'1' x length($&)/e;
        die "invalid string" if $s =~ /0/;
        $c;
    }

    $str =~ tr/a-zA-Z//c && die 'non-letter character';
    my $m = $str =~ tr/a-z/0/r
            =~ tr/A-Z/1/r
            =~ s/../$& ^. "\0\1"/ger;

    min alt($m), alt($m =~ tr/01/10/r);
}

See the full solution to task 1.

J

Though J has an adverb rxapply that acts like Perl’s s///egr, there is no direct equivalent without the g modifier. Therefore performing the match “manually” within the verb step:

find the first match
record the number of swaps
replace the matched string with 1’s

The verb is designed to be run in a u^:_ loop.

require 'regex'

alternate_case =: _(adverb define)
  uc =. a. {~ 65+i.26
  fail =. '01' {~ 1 (1 b.)`(6 b.)"0 uc e.~ ]
  flip =. '10' {~ '01' i. ]
  step =. {{
    'cnt str' =. y
    match =. '0(?:11)*0' rxmatch str
    if. 0 > (<0 0) { match do. y return. end.
    len =. (<0 1) { match
    ones =. < len # '1'
    swaps =. <: len
    (cnt + swaps) ; (ones match rxmerge str)
  }}
  alt =. 0 {:: [: (step^:_) 0 ; ]
  ([: <./ [: alt"1 flip ,: ]) @ fail f. : [:
)

Example 5:

   alternate_case 'bBBAaa'
2

See the full solution.

Task 2: Alternating Vowels Consonants

Submitted by: Mohammad Sajid Anwar

You are given three strings containing English alphabetic characters.

Find all the longest contiguous substrings common to all three strings that strictly alternate between vowels and consonants.

Example 1

Input: @str = ("relocate", "delocate", "allocate")
Output: ("locate")

Example 2

Input: @str = ("apple", "banana", "cherry")
Output: ()

Example 3

Input: @str = ("navigate", "cavity", "gravity")
Output: ("avi")

Example 4

Input: @str = ("pedalgia", "pedalboard", "pedantic")
Output: ("peda")

Example 5

Input: @strings = ("schoolmaster", "schoolhouse", "schooling")
Output: ("ho", "ol")

Solution

Generalizing the task to two or more words.

After joining the given words with newlines, the following regular expression (in Perl notation) will capture the first alternating substring common to all words:

qr{
    (
        (?&VOW)(?:(?&CONS)(?&VOW))*(?&CONS)?
        |
        (?&CONS)(?:(?&VOW)(?&CONS))*(?&VOW)?
    )
    .*+
    (?: \n .*? \1 .*+)++ $
    (?(DEFINE)
        (?<VOW>[aeiou])
        (?<CONS>[^aeiou\n])
    )
}xi;

It captures an alternating substring in the first word and matches it in all of the following words.

Depending on the programming language there are different ways to extend the pattern matching process to find all common alternating substrings and to restrict these to unique substrings of maximum length.

Perl

After matching one common alternating substring, the content of the capture group may be gathered and the regex engine can be forced to backtracking. This will detect all common alternating substrings.

This approach has one major issue and a minor flaw:

after the first word is exhausted, the match would continue in the second word and thus would detect common alternating substrings in all but the first word etc.
after matching one common alternating substring, backtracking would go through all prefixes of the matched substring in decreasing length. The prefixes will match too, but are shorter and therefore cannot contribute to the solution.

To solve the first issue, the capture group may be extended by a branch that terminates the process on a newline at the current point.

For the second flaw, the position after the first matched letter in the capture group may be marked as the backtracking target after a full match was found.

After gathering all alternating substrings, restrict to unique strings of maximum length.

I’ve never used any of the verbs (*MARK:name), (*SKIP:name) and (*COMMIT) before. Frankly, I didn’t even really understand their function. With this task, while looking for some special functionalities, I rediscovered them as a convenient solution.

This leads to the following implementation:

use strict;
use warnings;
use List::Gather;
use List::Util 'uniqstr';
use List::UtilsBy 'max_by';

sub alt_vow_cons {
    $_[0] =~ tr/a-zA-Z//c && die 'non-letter character';

    max_by {length} uniqstr gather {
        join("\n", @_) =~ m{
            (
                (?&VOW)(*MARK:NEXT)(?:(?&CONS)(?&VOW))*(?&CONS)?
                |
                (?&CONS)(*MARK:NEXT)(?:(?&VOW)(?&CONS))*(?&VOW)?
                |
                \n(*COMMIT)(*FAIL)
            )
            .*+
            (?: \n .*? \1 .*+)++ $
            (*SKIP:NEXT)
            (?{take $1})
            (*FAIL)
            (?(DEFINE)
                (?<VOW>[aeiou])
                (?<CONS>[^aeiou\n])
            )
        }xi;
    };
}

See the full solution to task 2.

J

Operating on a similar regex.

The regex matching has to be wrapped in a loop again, as (?{*code*}) is not available in J.

Some details:

The verb all_alt has exactly the same function as the expression gather {...} in the Perl solution. Basically it provides a loop around first_alt as a substitute for the verbs (*MARK:name), (*SKIP:name) and (*FAIL) in combination with (?{code}).
max_len corresponds to max_by {length}.
first_alt returns the first matched maximal alternating common substring together with the string’s suffix starting one character after the first matched. It must be run in a “Fold” loop.

require 'regex'

rcvc =: rxcomp 0 : 0
(?xi-ms)
  (
    (?&VOW)(?:(?&CONS)(?&VOW))*(?&CONS)?
    |
    (?&CONS)(?:(?&VOW)(?&CONS))*(?&VOW)?
    |
    \n(*COMMIT)(*FAIL)
  ) #
  .*+
  (?: \n .*? \1 .*+)++ $
  (?(DEFINE)
    (?<VOW>[aeiou])
    (?<CONS>[^aeiou\n])
  ) #
)

alt_vow_cons =: _(adverb define)
  NB. find the first common alternating subsequence
  first_alt =. {{
    in =. 0 {:: y
    match =. rcvc rxmatch in
    NB. terminate loop if not matching
    _2 Z: 0 > (<0 0){match
    NB. get next string to process from match x and
    NB. current string y
    next =. >:@{.@[ }. ]
    NB. return next string and captured
    NB. common alternating subsequence
    (1{match) (next ; rxfrom) in
  }}
  NB. join words with NL,
  NB. find all common alternating subsequences and
  NB. return empty on error
  all_alt =. ([: ({: F: first_alt) [: < LF joinstring ]) :: a:
  NB. find all entries having the maximum length
  max_len =. ([: I. >./ = ])@(# S:0) { ]

  NB. find all common alternating subsequences,
  NB. restrict to unique values and
  NB. select maximal lengths
  (max_len @ ~. @ all_alt) f. : [:
)

Example 5:

   alt_vow_cons ;:'schoolmaster schoolhouse schooling'
┌──┬──┐
│ho│ol│
└──┴──┘

Interleaved words:

alt_vow_cons ;:'dehinotu inotudehin ehinot'
┌────┬────┐
│ehin│inot│
└────┴────┘

See the full solution.

The Bear's Den

Enter at your own risk

Regular Alternations

Task 1: Alternate Case

Example 1

Example 2

Example 3

Example 4

Example 5

Solution

Perl

J

Task 2: Alternating Vowels Consonants

Example 1

Example 2

Example 3

Example 4

Example 5

Solution

Perl

J