07 November 2025

Challenge 346

Magic Parentheses

• Task 1: Longest Parenthesis
• Task 2: Magic Expression

Task 1: Longest Parenthesis

Submitted by: Mohammad Sajid Anwar

---

You are given a string containing only ( and ).

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

Example 1

Input: $str = '(()())'
Output: 6

Valid Parenthesis: '(()())'

Example 2

Input: $str = ')()())'
Output: 4

Valid Parenthesis: '()()' at positions 1-4.

Example 3

Input: $str = '((()))()(((()'
Output: 8

Valid Parenthesis: '((()))()' at positions 0-7.

Example 4

Input: $str = '))))((()('
Output: 2

Valid Parenthesis: '()' at positions 6-7.

Example 5

Input: $str = '()(()'
Output: 2

Valid Parenthesis: '()' at positions 0-1 and 3-4.

---

Solution

The rules for valid parentheses may be derived from the examples:

1. A single pair () of parentheses is valid, see examples 4 and 5.
2. valid parentheses enclosed in a pair of parentheses (...) are valid, see examples 1 and 3
3. The concatenation of valid parentheses is valid (...)(...), see example 2.

The task can be solved with a single regular expression that contains a code block, here with some comments:

m{
    (               # L1
        (?:         # L2
            \(      # L3
            (?1)?   # L4
            \)      # L5
        )+          # L6
    )               # L7
    (?{length($1) > $max and $max = length($1)})    # L8
    (*FAIL)         # L9
}x;

The block L1 - L7 has two functions:

1. It captures valid parentheses via $1, see L8.
2. It specifies a sub-pattern matching valid parentheses via (?1), see L4.

L2 - L6 matches one or more repetitions of the containing sub-expression (rule 3).

L3 - L5 match a pair of parentheses containing zero or one valid parentheses (rules 1 and 2).

L8 checks the length of the current match against the current maximum length.

L9 forces the regex engine into backtracking to find all valid parentheses.

use strict;
use warnings;

sub longest_parenthesis {
    my $max = 0;
    shift =~ m{
        (
            (?:
                \(
                (?1)?
                \)
            )+
        )
        (?{length($1) > $max and $max = length($1)})
        (*FAIL)
    }x;
    $max;
}

See the full solution to task 1.

Task 2: Magic Expression

Submitted by: Mohammad Sajid Anwar

---

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.

Example 1

Input: $str = "123", $target = 6
Output: ("1*2*3", "1+2+3")

Example 2

Input: $str = "105", $target = 5
Output: ("1*0+5", "10-5")

Example 3

Input: $str = "232", $target = 8
Output: ("2*3+2", "2+3*2")

Example 4

Input: $str = "1234", $target = 10
Output: ("1*2*3+4", "1+2+3+4")

Example 5

Input: $str = "1001", $target = 2
Output: ("1+0*0+1", "1+0+0+1", "1+0-0+1", "1-0*0+1", "1-0+0+1", "1-0-0+1")

---

Solution

The rules for valid expression can be derived from the examples:

• All possible expressions that evaluate to the target shall be found.
• Neighboring digits may be grouped together as one number as can be seen in example 2: 10-5 is valid.
• Leading zeros are not allowed. Otherwise the expression 1+001 would be valid in example 5.

It is possible to generate all possible expression, discard invalid ones, evaluate and compare them to the target. There are \(4^{n-1}\) expressions to be processed. This doesn’t look desirable but no better approach crossed my mind.

Some implementation details:

• There are four possible operators between two digits: +, -, * and concatenation. This leads to the mentioned number of \(4^{n-1}\) generated expressions.
• If such many loop cycles are inevitable, it is essential to make each cycle as efficient as possible.
• The digits are placed in an array that contains “holes” for the selected operators. The “holes” are produced by a capturing group in a split pattern.
• The “holes” may be addressed as an array slice of all odd indices.
• The operators to be inserted can be enumerated with a \((n - 1)\)-fold set product of the operators’ array with itself. For better performance make sure Set::Product::XS is installed, too.
• Expressions containing a number with a leading zero are skipped. This check is required only if $str has a zero followed by a digit, that may become a leading zero.
• The remaining expressions are calculated and compared to the target using PARI. This is much faster than using perl’s eval for the calculations.
• There is an edge case where $str has only a single digit. Here a comparison of this digit with the target is sufficient.

use strict;
use warnings;
use Set::Product 'product';
use List::Gather;
use Math::Pari 'PARI';
use experimental 'signatures';

sub magic_expression ($str, $target) {
    state $op = ['', '+', '-', '*'];
    my ($n, $t, $nz, $e) = (length($str), PARI($target), $str !~ /0./);
    return $str == $target ? $str : () if $n == 1;
    my @expr = split /()/, $str;
    my @odd = map 2 * $_ + 1, 0 .. $n - 2;

    gather {
        product {
            @expr[@odd] = @_;
            $e = join '', @expr;
            ($nz || $e !~ /(?<!\d)0\d/) && $t == PARI($e) && take $e;
        } ($op) x ($n - 1);
    }
}

See the full solution to task 2.