Weekly Challenge: Longest Expression

Weekly Challenge 346

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: Longest Parenthesis

Task

You are given a string containing only ( and ).

Write a script to find the length of the longest valid parenthesis.

My solution

I start by writing a function called is_balanced, which takes a string as input. It counts the number of open and close parentheses. If it finds a closing one without a matching opening, it returns False. It will also return False if at the end there is an opening parentheses that doesn't have a closing one.

def is_balanced(s: str) -> bool:
    count = 0
    for char in s:
        if char == '(':
            count += 1
        elif char == ')':
            if count == 0:
                return False
            count -= 1
    return count == 0

The main function has two loops. The outer loop is called length ($len in the Perl solution). It starts at the length of the string, down to 2 (as it's not possible to have a valid single parenthesis). The inner loop with the variable start, marks the start position. For each iteration I called the is_balanced function starting at start with the length length and return the length if the string is balanced.

def longest_parenthesis(input_string: str) -> int:
    if not re.search(r'^[()]+$', input_string):
        raise ValueError("Input string must contain only parentheses")

    for length in range(len(input_string), 1, -1):
        for start in range(len(input_string) - length + 1):
            substring = input_string[start:start + length]
            if is_balanced(substring):
                return length

    return 0

Examples

$ ./ch-1.py '(()())'
6

$ ./ch-1.py ')()())'
4

$ ./ch-1.py '((()))()(((()'
8

$ ./ch-1.py '))))((()('
2

$ ./ch-1.py '()(()'
2

Task 2: Magic Expression

Task

You are given a string containing only digits and a target integer.

Write a script to insert binary operators +, - and * between the digits in the given string that evaluates to target integer.

My solution

This was a fun challenge. Between each digit, I can either add one of the operators or nothing (and thus join two digits together).

Originally I planned to use a bitwise operation to determine what to do, but then I found the work had already been done. Python's itertools module has the product function, while Perl's Algorithm::Combinatorics module has the variations_with_repetition function.

I use this function along with zip (Python, Perl) to construct all possible combinations of expressions. There are 4^{length - 1} possible combinations.

The next part is to compare the expression with the target. There are many different ways to do this. The easiest is to use eval (Python, Perl). Both can cause serious issues if it the input has not been sanitised. This is mitigated because I have checked the input_string only contains digits.

I skip expressions that have a leading zero (like 1+001 in the last example). If the expression is equal to the target, I add it to the magic_expressions list (array in Perl).

def magic_expression(input_string: str | int, target: int) -> list[str]:
    input_string = str(input_string)
    if not re.search(r'^[0-9]+$', input_string):
        raise ValueError("Input string must contain only digits")

    operators = ['', '+', '-', '*']
    magic_expressions = []

    for ops in product(operators, repeat=len(input_string)-1):
        expression = ''.join(
            digit + op for digit, op in zip_longest(input_string, ops, fillvalue='')
        )
        if re.search(r'[\+\-\*]0\d', expression):
            continue
        if eval(expression) == target:
            magic_expressions.append(expression)

    return magic_expressions

Examples

The order is different that what is in the examples, still produces similar results.

$ ./ch-2.py 123 6
("1+2+3", "1*2*3")

$ ./ch-2.py 105 5
("10-5", "1*0+5")

$ ./ch-2.py 232 8
("2+3*2", "2*3+2")

$ ./ch-2.py 1234 10
("1+2+3+4", "1*2*3+4")

$ ./ch-2.py 1001 2
("1+0+0+1", "1+0-0+1", "1+0*0+1", "1-0+0+1", "1-0-0+1", "1-0*0+1")