Weekly Challenge: The one about alternating

Weekly Challenge 394

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. Unless otherwise stated, Copilot (and other AI tools) have NOT been used to generate the solution. It's a great way for us all to practice some coding.

Challenge, My solutions

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.

My solution

I'm pretty sure I've overengineered this solution, given that it is task one. For this I start with two constants called UCL and LCL which is a set of upper case letters and lower case letters respectively.

import string

UCL = set(string.ascii_uppercase)
LCL = set(string.ascii_lowercase)

I then have a function is_alt_case. It determines if the string is alternating between upper and lower case letters. If it is, it will return None (-1 for the Perl solution). If it finds a letter with incorrect case, it will find the position of the next letter in the correct case and returns one less than that position. This represents the letters that will be swapped.

def is_alt_case(s: str, upper_first: bool) -> int|None:
    for pos, letter in enumerate(s):
        next_letters = UCL if (upper_first + pos) % 2 else LCL
        if letter in next_letters:
            continue

        for i in range(pos+ 1, len(s)):
            if s[i] in next_letters:
                return i-1

    return None

As strings are immutable in Python, I have function called swap_letters. Given a string s and an integer pos, it will swap the letters in position pos and pos+1.

def swap_letters(s: str, pos: int) -> str:
    return s[:pos] + s[pos+1] + s[pos] + s[pos+2:]

The main function starts by checking that the strings is valid, specifically it contains only letters, has an even number of letters and half of them are upper case.

def alt_case(input_string: str) -> int:
    half_length = len(input_string) // 2
    if len(input_string) % 2:
        raise ValueError("String must have an even number of characters")
    if not re.search("^[a-z]+$", input_string, flags=re.I):
        raise ValueError("The word contain non-letter characters")
    if sum(1 for letter in input_string if letter in UCL) != half_length:
        raise ValueError(
            "Letter must contain the same number of upper and lower case letters"
        )

As I don't know if the string should start with an upper case or lower case letter, I try both and return the one with the minimum number of moves.

I have a loop that calls is_alt_case until it returns None (meaning the string is correct) counting moves for each move made.

    move_list = []

    for upper_first in {True, False}:
        s = input_string
        moves = 0
        while (next_swap_pos := is_alt_case(s, upper_first)) is not None:
            s = swap_letters(s, next_swap_pos)
            moves += 1

        move_list.append(moves)

    return min(move_list)

Examples

$ ./ch-1.py aAbB
0

$ ./ch-1.py AAbb
1

$ ./ch-1.py AAAbbb
3

$ ./ch-1.py aABb
1

$ ./ch-1.py bBBAaa
2

Task 2: Alternating Vowels Consonants

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.

My solution

For this challenge, I define a function called is_alt_vc. It checks if the substring alternates between vowels and consonants. For the first letter, it sets vowel_next to True or False depending on the type of it. It then alternates this variable for each subsequent letter.

def is_alt_vc(substr: str) -> bool:
    # Start with the type of the fist letter
    vowel_next = substr.lower()[0] in VOWELS

    for letter in substr.lower():
        if vowel_next ^ (letter in VOWELS):
            # The letter is the wrong type
            return False
        # The next letter needs to be the opposite
        vowel_next = not(vowel_next)

    # The word alternates between vowels and consonants
    return True

The main function starts by checking that all the supplied words only contain letters of the English alphabet.

def alt_vc(words: list[str]) -> list[str]:
    if not all(re.search('^[a-z]+$', word, flags=re.I) for word in words):
        raise ValueError("Some words contain non-letters")

I then find the shortest_word (the first if there is more than one of the same length) and the length of that word. The maximum possible solution is this length.

    shortest_word = sorted(words, key=len)[0]
    min_length = len(shortest_word)

I then have a double loop. The outer loop is called length and starts with min_length and decreases to 1. The inner loop is called start representing the starting position of the substr, the value is 0 up to the min_length - length. I then generate the substring, and check if it appears in all words and alternates between vowels and consonants.

If one or more substrings of a specific length is found, I return all the substrings found. If the loops are exhausted, I return an empty list (array in Perl).

    result = []
    for length in range(min_length, 0, -1):
        for start in range(min_length-length+1):
            substr = shortest_word[start:start+length]
            if all(substr in word for word in words) and is_alt_vc(substr):
                result.append(substr)

        if result:
            return sorted(result)

    return []

Examples

$ ./ch-2.py relocate delocate allocate
("locate")

$ ./ch-2.py apple banana cherry
()

$ ./ch-2.py navigate cavity gravity
("avi")

$ ./ch-2.py pedalgia pedalboard pedantic
("peda")

$ ./ch-2.py schoolmaster schoolhouse schooling
("ho", "ol")