This is my response to The Weekly Challenge #394.
Input: $str = "aAbB"
Output: 0
Input: $str = "AAbb"
Output: 1
Swap 1: "AbAb"
Input: $str = "AAAbbb"
Output: 3
Swap 1: "AAbAbb"
Swap 2: "AbAAbb"
Swap 3: "AbAbAb"
Input: $str = "aABb"
Output: 1
Swap 1: "aAbB"
Input: $str = "bBBAaa"
Output: 2
Swap 1: "BbBAaa"
Swap 2: "BbBaAa"
#! /usr/bin/env raku
unit sub MAIN ($str where ($str ~~ /^ <[a..zA..Z]>+ $/)
&& ($str.comb.grep(/<[a..z]>/).elems * 2
== $str.chars),
:v(:$verbose));
sub is-lower(Str $c) { $c.lc eq $c }
my $best-count = Inf;
my @best-steps;
my $best-start;
for 0, 1 -> $start
{
my @chars = $str.comb;
my $count = 0;
my @steps;
for ^@chars.elems -> $i
{
my $want-lower = ($i % 2) == $start;
next if is-lower(@chars[$i]) == $want-lower;
my $j = $i + 1;
$j++ while is-lower(@chars[$j]) != $want-lower;
while $j > $i
{
my $tmp = @chars[$j - 1];
@chars[$j - 1] = @chars[$j];
@chars[$j] = $tmp;
$j--;
$count++;
@steps.push: @chars.join;
}
}
if $count < $best-count
{
$best-count = $count;
@best-steps = @steps;
$best-start = $start;
}
}
if $verbose
{
my @pattern = map { ($_ % 2) == $best-start ?? "L" !! "U" },
^$str.chars;
say ": Target: " ~ @pattern.join(" ");
for 1 .. @best-steps.elems -> $n
{
say ": Swap $n: { @best-steps[$n - 1] }";
}
}
say $best-count;[3] English characters only, and exactly half of them lowercase.
[8] Helper procedure telling us if the input is lowercase (with lc).
See docs.raku.org/routine/lc for more information about lc.
[10] The lowest number of swaps for the best one.
[11] The actual swaps.
[12] The best start (see [14]).
[14] We can start the result with either a lowercase or uppcase letter, so have to check both cases (pun intended). 0=lowercase (index 0,2,4,..) and 1=uppercase (index 1,3,5,..).
[16] The number of characters.
[17] The number of swaps.
[18] The actual swaps.
[20] Iterate over all the character indices.
[22] Do we want a lowercase letter here?
[24] Do nothing if we have what we want.
[26] Start looking at the next index.
[27] Look for the first character of the correct case, saving the index.
[30] As long as we have not swaped that character back to where we need it.
[32-34] Swap that character one position to the left.
[36] Count the swap.
[37] The swap itself, for verbose mode.
[41] Do we have a winner? Note that the first iteration (start with lowercase) will always give a yes. The second one (start with uppercase) may or may not.
[43-45] If so, set the number of swaps, the swaps themselves, and the lc/uc starting status.
[62] Print the result.
Running it:
$ ./alternate-case aAbB
0
$ ./alternate-case AAbb
1
$ ./alternate-case AAAbbb
3
$ ./alternate-case aABb
1
$ ./alternate-case bBBAaa
2
Looking good.
With verbose mode:
$ ./alternate-case -v aAbB
: Target: L U L U
0
$ ./alternate-case -v AAbb
: Target: U L U L
: Swap 1: AbAb
1
$ ./alternate-case -v AAAbbb
: Target: U L U L U L
: Swap 1: AAbAbb
: Swap 2: AbAAbb
: Swap 3: AbAbAb
3
$ ./alternate-case -v aABb
: Target: L U L U
: Swap 1: aAbB
1
$ ./alternate-case -v bBBAaa
: Target: U L U L U L
: Swap 1: BbBAaa
: Swap 2: BbBaAa
2
Input: @str = ("relocate", "delocate", "allocate")
Output: ("locate")
Input: @str = ("apple", "banana", "cherry")
Output: ()
Input: @str = ("navigate", "cavity", "gravity")
Output: ("avi")
Input: @str = ("pedalgia", "pedalboard", "pedantic")
Output: ("peda")
Input: @strings = ("schoolmaster", "schoolhouse", "schooling")
Output: ("ho", "ol")
#! /usr/bin/env raku
subset English where * ~~ /^ <[a..zA..Z]>+ $/;
unit sub MAIN (English $s1, English $s2, English $s3,
:v(:$verbose));
sub is-vowel(Str $c) { $c.lc ∈ <a e i o u> }
sub alternating-runs(Str $s)
{
my @runs;
my $n = $s.chars;
my $i = 0;
while $i < $n
{
my $j = $i;
$j++ while $j + 1 < $n
&& is-vowel($s.substr($j, 1))
!= is-vowel($s.substr($j + 1, 1));
@runs.push: $s.substr($i, $j - $i + 1);
$i = $j + 1;
}
@runs;
}
sub alternating-substrings(Str $s)
{
my @subs;
for alternating-runs($s) -> $run
{
for 0 ..^ $run.chars -> $a
{
for 1 .. $run.chars - $a -> $len
{
@subs.push: $run.substr($a, $len);
}
}
}
@subs;
}
my @sets = map { alternating-substrings($_).Set },
$s1, $s2, $s3;
my @common = (@sets[0] ∩ @sets[1] ∩ @sets[2]).keys;
my $max = @common.elems ?? @common.map(*.chars).max !! 0;
my @result = @common.grep(*.chars == $max).sort;
if $verbose
{
for $s1, $s2, $s3 -> $s
{
say ": $s -> " ~ alternating-runs($s).join(", ");
}
say ": Common: " ~ @common.sort.join(", ") if @common.elems;
say ": Longest: $max" if $max;
}
say "({ @result.map( '"' ~ * ~ '"' ).join(", ") })";[3] A custom type with subset for an English "word".
See docs.raku.org/language/typesystem#subset for more information about subset.
[5] Apply the custom type on the three input strings.
[8] Helper procedure telling us if the character is a vowel. I have excluded "y" here.
[10] The procedure finding the maximal alternating runs in a string.
[12] The runs we find.
[13] The number of characters.
[16] While there are characters left.
[18] The end of the current run.
[19-21] Extend the run as long as the next two characters have different
vowel/consonant status (is-vowel).
[23] Save the run.
[24] Continue right after the run.
[27] Return the runs.
[30] The procedure finding all the alternating substrings in a string. (Every substring of an alternating run is alternating itself.)
[32] The substrings we find.
[34] For each maximal run.
[36] For each starting position in the run.
[38] For each possible length from that position.
[40] Save the substring.
[45] Return the substrings.
Running it:
$ ./alternating-vowels-consonants relocate delocate allocate
("locate")
$ ./alternating-vowels-consonants apple banana cherry
()
$ ./alternating-vowels-consonants navigate cavity gravity
("avi")
$ ./alternating-vowels-consonants pedalgia pedalboard pedantic
("peda")
$ ./alternating-vowels-consonants schoolmaster schoolhouse schooling
("ho", "ol")
Looking good.
With verbose mode:
$ ./alternating-vowels-consonants -v relocate delocate allocate
: relocate -> relocate
: delocate -> delocate
: allocate -> al, locate
: Common: a, at, ate, c, ca, cat, cate, e, l, lo, loc, loca, locat, locate, \
o, oc, oca, ocat, ocate, t, te
: Longest: 6
("locate")
$ ./alternating-vowels-consonants -v apple banana cherry
: apple -> ap, p, le
: banana -> banana
: cherry -> c, her, r, y
()
$ ./alternating-vowels-consonants -v navigate cavity gravity
: navigate -> navigate
: cavity -> cavit, y
: gravity -> g, ravit, y
: Common: a, av, avi, i, t, v, vi
: Longest: 3
("avi")
$ ./alternating-vowels-consonants -v pedalgia pedalboard pedantic
: pedalgia -> pedal, gi, a
: pedalboard -> pedal, bo, ar, d
: pedantic -> pedan, tic
: Common: a, d, da, e, ed, eda, p, pe, ped, peda
: Longest: 4
("peda")
$ ./alternating-vowels-consonants -v schoolmaster schoolhouse schooling
: schoolmaster -> s, c, ho, ol, mas, ter
: schoolhouse -> s, c, ho, ol, ho, use
: schooling -> s, c, ho, olin, g
: Common: c, h, ho, l, o, ol, s
: Longest: 2
("ho", "ol")
And that's it.