Weekly Challenge: The First Expansion

Weekly Challenge 390

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. 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: Decode String

You are given an encoded string.

Write a script to return the decoded string of the given encoded string.

The encoding rule is: K[encoded_string], where the encoded_string inside the square brackets is repeated exactly K > 0 times.

My solution

This task is very similar to the second challenge three weeks ago. My commentary there applies equally here.

I start with a function called expand_brackets which will expand the inner most brackets preceeded by a number using that number match_obj[1] to multiple the characters inside the bracket match_obj[2].

def expand_brackets(match_obj: re.Match) -> str:
    multiplier = int(match_obj[1])
    s = match_obj[2]
    return s * multiplier

The main decode_string function starts by expanding all brackets using a regular expression and the expand_brackets callback function. It then checks that all brackets have been removed, and returns the string.

import re

def decode_string(input_string: str) -> str:
    while re.search(r"\d+\[[A-Z0-9]+\]", input_string, flags=re.I):
        input_string = re.sub(
            r"(\d+)\[([^\[\]]+)\]", expand_brackets, input_string, flags=re.I
        )

    if "[" in input_string or "]" in input_string:
        raise ValueError("Invalid input")

    return input_string

Examples

$ ./ch-1.py "2[3[a]]"
"aaaaaa"

$ ./ch-1.py "10[a]"
"aaaaaaaaaa"

$ ./ch-1.py "a2[b]c3[d]e"
"abbcddde"

$ ./ch-1.py "2[a2[b]c]"
"abbcabbc"

$ ./ch-1.py "1[a]2[b3[c]]"
"abcccbccc"

Task 2: Order Characters

You are given a string $s (containing only alphabetic characters) and an integer $k > 0.

Write a script to choose one of the first $k letters of given string and append it at the end of the string. You keep doing this until you have lexicographically smallest string and return the string.

My solution

Picking from 1 to k, and repeating sounds like a task that requires a recursive function. The order_characters function takes the input values, and calls the find_string function to find all strings that can be computed. It then sorts the set, and returns the first one alphabetically.

def order_characters(input_string: str, k: int) -> str:
    strings_found = set()
    find_string(input_string, k)
    return sorted(strings_found)[0]

The find_string function (which is called from above) starts by adding the current word to the strings_found set. It then has a loop from 1 to k. For each iteration it generates new_word by moving one character to the end of the string. If that string is not in the strings_found set, the recursive function is called again.

def find_string(word, k):
    nonlocal strings_found

    strings_found.add(word)
    for i in range(k):
        new_word = word[:i] + word[i + 1 :] + word[i]
        if new_word not in strings_found:
            find_string(new_word, k)

Examples

$ ./ch-2.py dbca 1
"adbc"

$ ./ch-2.py geeks 2
"eegks"

$ ./ch-2.py cbaed 3
"abcde"

$ ./ch-2.py fedcba 4
"abcdef"

$ ./ch-2.py perl 1
"erlp"

$ ./ch-2.py oloolooo 1
"looloooo"

$ ./ch-2.py oloooolo 1
"looloooo"