Weekly Challenge: Balancing the Score

Weekly Challenge 342

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. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Balance String

Task

You are given a string made up of lowercase English letters and digits only.

Write a script to format the give string where no letter is followed by another letter and no digit is followed by another digit. If there are multiple valid rearrangements, always return the lexicographically smallest one. Return empty string if it is impossible to format the string.

My solution

For this task, I start by separating the input_string into two lists (arrays in Perl) called digits and letters. Both list are sorted, with the letters sorted in a case insensitive manner. The item in the digits list remain of the str (string) type.

def balance_string(input_string: str) -> str:
    digits = sorted(re.findall(r"\d", input_string))
    letters = sorted(
        re.findall(r"[A-Za-z]", input_string),
        key=str.lower
    )

I then check if the absolute difference between the lengths of both lists is more than one. If it is, it is impossible to format the string so I return an empty string.

    if abs(len(digits) - len(letters)) > 1:
        return ""

If the digits list is smaller than the letters list, I prepend an empty string to the digits list. If the letters list is smaller, I append an empty string to the letters list.

    if len(digits) < len(letters):
        digits.insert(0, "")
    elif len(letters) < len(digits):
        letters.append("")

Now both lists are the same size. The solution is found by pairing up the digit and then letter at each position.

    solution = ""
    for i in range(len(digits)):
        solution += digits[i] + letters[i]

    return solution

The Perl solution follows the same logic.

Examples

$ ./ch-1.py a0b1c2
"0a1b2c"

$ ./ch-1.py abc12
"a1b2c"

$ ./ch-1.py 0a2b1c3
"0a1b2c3"

$ ./ch-1.py 1a23
""

$ ./ch-1.py ab123
"1a2b3"

Task 2: Max Score

Task

You are given a string, $str, containing 0 and 1 only.

Write a script to return the max score after splitting the string into two non-empty substrings. The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

My solution

The Python solution is relatively straight forward. I first check that the input_string contains only 0s and 1s, and raise an exception if this is not the case. I set the variable current_max to 0.

I then have a loop from 1 to one less then the length of the string. For each iteration, I split the string at that position and count the zeros on the left side and ones on the right side. If this score is greater than the current maximum score, I update the current_max variable.

def max_score(input_string: str) -> int:
    if not re.match(r'^[01]+$', input_string):
        raise ValueError("Input must contain only '0' and '1' characters")

    current_max = 0

    for i in range(1, len(input_string)):
        left = input_string[:i].count('0')
        right = input_string[i:].count('1')

        if left + right > current_max:
            current_max = left + right

    return current_max

As Perl, doesn't have the count method, I can achieve the same by using the tr function. This will return the number of changes made. The overall logic is the same. I have a calculate_score function to calculate the score. It takes the input_string and split position as input.

sub calculate_score ($input_string, $split_index) {
    my $left = substr($input_string, 0, $split_index);
    my $right = substr($input_string, $split_index);

    my $count_0 = ($left =~ tr/0//);
    my $count_1 = ($right =~ tr/1//);

    return $count_0 + $count_1;
}

Examples

$ ./ch-2.py 0011
4

$ ./ch-2.py 0000
3

$ ./ch-2.py 1111
3

$ ./ch-2.py 0101
3

$ ./ch-2.py 011101
5