Add Perl and Python solutions for challenge 346

5 files changed, 337 insertions, 20 deletions

diff --git a/challenge-346/lubos-kolouch/README b/challenge-346/lubos-kolouch/README
index 5b34a3ed40..7f47843cb2 100644
--- a/challenge-346/lubos-kolouch/README
+++ b/challenge-346/lubos-kolouch/README
@@ -1,30 +1,26 @@
-# Perl Weekly Challenge 345 Solutions
+# Perl Weekly Challenge 346 Solutions
 
-Perl and Python implementations for both tasks of Weekly Challenge 345.
+Perl and Python implementations for both tasks of Weekly Challenge 346.
 
-## Task 1: Peak Positions
+## Task 1: Longest Parenthesis
 
-Identify every index whose value is strictly greater than its immediate
-neighbour(s). Endpoints are considered peaks when they exceed their sole
-neighbour.
+Determine the length of the longest valid parenthesis substring contained
+within an input built from `(` and `)`.
 
-- **Perl (`perl/ch-1.pl`)**: Validates the integer list with `Type::Params`,
-  then performs a single pass comparing each value against the surrounding
-  entries to collect the peak indices.
-- **Python (`python/ch-1.py`)**: Mirrors the linear scan with explicit type
-  hints and a set of `unittest` cases for the provided examples.
+- **Perl (`perl/ch-1.pl`)**: Uses a stack of indices with type-checked input
+  to track unmatched parentheses and compute the maximum span.
+- **Python (`python/ch-1.py`)**: Mirrors the stack-based pass with explicit
+  type hints and `unittest` coverage for the specification data.
 
-## Task 2: Last Visitor
+## Task 2: Magic Expression
 
-Process a mixed list of positive integers and `-1` markers. Each integer is
-stored at the front of a queue, while every `-1` requests the value `x` steps
-back in that queue, where `x` counts consecutive `-1` entries.
+Insert `+`, `-`, and `*` between the digits of the supplied string so the
+expression evaluates to the target integer.
 
-- **Perl (`perl/ch-2.pl`)**: Maintains the visitor queue with input validation
-  and tracks the current `-1` run to select the right lookup or `-1` when the
-  queue is too short.
-- **Python (`python/ch-2.py`)**: Provides the same behaviour with typed
-  functions and unit tests aligned with the specification examples.
+- **Perl (`perl/ch-2.pl`)**: Performs depth-first search with precedence-aware
+  bookkeeping, returning every lexicographically sorted solution.
+- **Python (`python/ch-2.py`)**: Applies the same backtracking strategy with
+  typed helpers and unit tests bound to the official examples.
 
 ## Running the Solutions
 
diff --git a/challenge-346/lubos-kolouch/perl/ch-1.pl b/challenge-346/lubos-kolouch/perl/ch-1.pl
new file mode 100644
index 0000000000..5319b3468e
--- /dev/null
+++ b/challenge-346/lubos-kolouch/perl/ch-1.pl
@@ -0,0 +1,79 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use feature qw(signatures state);
+no warnings qw(experimental::signatures);
+use Type::Params    qw(compile);
+use Types::Standard qw(StrMatch);
+use Test::More;
+
+=pod
+
+=head1 PURPOSE
+
+Compute the length of the longest valid parenthesis substring contained in
+an input string made up exclusively of opening and closing parentheses.
+
+=head1 ALGORITHM
+
+We validate the input using L<Type::Params> to ensure it only contains the
+characters C<(>) and C<)>. A stack of indices tracks unmatched opening
+parentheses, seeded with C<-1> as a sentinel to simplify length
+calculations. While scanning the string:
+
+=over 4
+
+=item *
+Push the index of every opening parenthesis.
+
+=item *
+Pop for each closing parenthesis, measuring the span back to the previous
+unmatched position. When the stack empties we push the current index to mark
+the start of the next candidate segment.
+
+=back
+
+The maximum span observed is the required result.
+
+=cut
+
+## no critic (Subroutines::ProhibitSubroutinePrototypes)
+sub longest_parenthesis ($str_input) {
+    state $check = compile( StrMatch [qr/\A[()]*\z/] );
+    my ($str) = $check->($str_input);
+
+    my $length = length $str;
+    return 0 if $length == 0;
+
+    my @stack   = (-1);
+    my $longest = 0;
+
+    for my $idx ( 0 .. $length - 1 ) {
+        my $char = substr $str, $idx, 1;
+
+        if ( $char eq '(' ) {
+            push @stack, $idx;
+            next;
+        }
+
+        pop @stack;
+        if (@stack) {
+            my $candidate = $idx - $stack[-1];
+            $longest = $candidate if $candidate > $longest;
+        }
+        else {
+            push @stack, $idx;
+        }
+    }
+
+    return $longest;
+}
+
+# Example tests provided by the specification.
+is( longest_parenthesis('(()())'),        6, 'Example 1' );
+is( longest_parenthesis(')()())'),        4, 'Example 2' );
+is( longest_parenthesis('((()))()(((()'), 8, 'Example 3' );
+is( longest_parenthesis('))))((()('),     2, 'Example 4' );
+is( longest_parenthesis('()(()'),         2, 'Example 5' );
+
+done_testing();
diff --git a/challenge-346/lubos-kolouch/perl/ch-2.pl b/challenge-346/lubos-kolouch/perl/ch-2.pl
new file mode 100644
index 0000000000..1fd5d5753c
--- /dev/null
+++ b/challenge-346/lubos-kolouch/perl/ch-2.pl
@@ -0,0 +1,92 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use feature qw(signatures state);
+no warnings qw(experimental::signatures);
+use Type::Params    qw(compile);
+use Types::Standard qw(Int StrMatch);
+use Test::More;
+
+=pod
+
+=head1 PURPOSE
+
+Generate all expressions that insert the binary operators C<+>, C<->, and
+C<*> between the digits of a string so that the resulting arithmetic equals
+a target integer.
+
+=head1 ALGORITHM
+
+Input validation employs L<Type::Params> ensuring a digit-only string and an
+integer target. The search performs depth-first backtracking over every
+possible digit partition. For each partition we append the next operand with
+each operator, tracking both the cumulative value and the most recent
+operand to preserve multiplication precedence:
+
+=over 4
+
+=item *
+Addition and subtraction directly adjust the running total.
+
+=item *
+Multiplication rewinds the previous operand from the total and replaces it
+with the product, effectively emulating standard precedence without parsing.
+
+=back
+
+Numbers containing leading zeros are skipped (except the single digit zero).
+All matching expressions are sorted lexicographically before being returned.
+
+=cut
+
+## no critic (Subroutines::ProhibitSubroutinePrototypes)
+sub magic_expression ( $digits_input, $target_input ) {
+    state $check = compile( StrMatch [qr/\A\d+\z/], Int );
+    my ( $digits, $target ) = $check->( $digits_input, $target_input );
+
+    my $length = length $digits;
+    my @results;
+
+    my $search;
+    $search = sub ( $pos, $expression, $value, $last_operand ) {
+        if ( $pos == $length ) {
+            push @results, $expression if $value == $target;
+            return;
+        }
+
+        for my $end ( $pos + 1 .. $length ) {
+            my $chunk = substr $digits, $pos, $end - $pos;
+            next if length($chunk) > 1 && substr( $chunk, 0, 1 ) eq '0';
+            my $number = 0 + $chunk;
+
+            if ( $pos == 0 ) {
+                $search->( $end, $chunk, $number, $number );
+                next;
+            }
+
+            $search->( $end, "$expression+$chunk", $value + $number, $number );
+            $search->( $end, "$expression-$chunk", $value - $number, -$number );
+
+            my $product = $last_operand * $number;
+            $search->( $end, "$expression*$chunk", $value - $last_operand + $product, $product );
+        }
+    };
+
+    $search->( 0, q{}, 0, 0 );
+    @results = sort @results;
+
+    return \@results;
+}
+
+# Example tests provided by the specification.
+is_deeply( magic_expression( '123',  6 ),  [ '1*2*3',   '1+2+3' ],   'Example 1' );
+is_deeply( magic_expression( '105',  5 ),  [ '1*0+5',   '10-5' ],    'Example 2' );
+is_deeply( magic_expression( '232',  8 ),  [ '2*3+2',   '2+3*2' ],   'Example 3' );
+is_deeply( magic_expression( '1234', 10 ), [ '1*2*3+4', '1+2+3+4' ], 'Example 4' );
+is_deeply(
+    magic_expression( '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' ],
+    'Example 5'
+);
+
+done_testing();
diff --git a/challenge-346/lubos-kolouch/python/ch-1.py b/challenge-346/lubos-kolouch/python/ch-1.py
new file mode 100644
index 0000000000..c5a60ae383
--- /dev/null
+++ b/challenge-346/lubos-kolouch/python/ch-1.py
@@ -0,0 +1,61 @@
+"""Longest Parenthesis Challenge Solution.
+
+Determine the length of the longest valid parenthesis substring within an
+input consisting solely of opening and closing parentheses.
+"""
+
+from __future__ import annotations
+
+import unittest
+
+
+def longest_parenthesis(paren_string: str) -> int:
+    """Return the length of the longest well-formed parenthesis substring.
+
+    The algorithm scans the string once while maintaining a stack of indices
+    for unmatched opening parentheses. A sentinel index of ``-1`` simplifies
+    length calculations when a balanced substring is identified.
+    """
+    stack: list[int] = [-1]
+    longest = 0
+
+    for index, char in enumerate(paren_string):
+        if char not in ("(", ")"):
+            msg = "Input must contain only '(' and ')'."
+            raise ValueError(msg)
+
+        if char == "(":
+            stack.append(index)
+            continue
+
+        stack.pop()
+        if stack:
+            candidate = index - stack[-1]
+            longest = max(longest, candidate)
+        else:
+            stack.append(index)
+
+    return longest
+
+
+class LongestParenthesisTests(unittest.TestCase):
+    """Unit tests restricted to the specification examples."""
+
+    def test_example_1(self) -> None:
+        self.assertEqual(longest_parenthesis("(()())"), 6)
+
+    def test_example_2(self) -> None:
+        self.assertEqual(longest_parenthesis(")()())"), 4)
+
+    def test_example_3(self) -> None:
+        self.assertEqual(longest_parenthesis("((()))()(((()"), 8)
+
+    def test_example_4(self) -> None:
+        self.assertEqual(longest_parenthesis("))))((()("), 2)
+
+    def test_example_5(self) -> None:
+        self.assertEqual(longest_parenthesis("()(()"), 2)
+
+
+if __name__ == "__main__":
+    unittest.main()
diff --git a/challenge-346/lubos-kolouch/python/ch-2.py b/challenge-346/lubos-kolouch/python/ch-2.py
new file mode 100644
index 0000000000..6196ec7e3e
--- /dev/null
+++ b/challenge-346/lubos-kolouch/python/ch-2.py
@@ -0,0 +1,89 @@
+"""Magic Expression Challenge Solution.
+
+Insert binary operators between the digits of a string so that the resulting
+expression evaluates to a target integer.
+"""
+
+from __future__ import annotations
+
+import unittest
+
+
+def magic_expression(digits: str, target: int) -> list[str]:
+    """Return sorted expressions that evaluate to ``target``.
+
+    The function performs a depth-first search over every partition of the
+    digit string, appending each operator while maintaining the cumulative
+    value and most recent operand. Multiplication adjusts the running total
+    to honour standard operator precedence without relying on ``eval``.
+    """
+    if not digits.isdigit():
+        msg = "Input must consist solely of decimal digits."
+        raise ValueError(msg)
+
+    results: list[str] = []
+    length = len(digits)
+
+    def backtrack(index: int, expression: str, value: int,
+                  last_operand: int) -> None:
+        if index == length:
+            if value == target:
+                results.append(expression)
+            return
+
+        for end in range(index + 1, length + 1):
+            chunk = digits[index:end]
+            if len(chunk) > 1 and chunk[0] == "0":
+                break
+            number = int(chunk)
+
+            if index == 0:
+                backtrack(end, chunk, number, number)
+                continue
+
+            backtrack(end, f"{expression}+{chunk}", value + number, number)
+            backtrack(end, f"{expression}-{chunk}", value - number, -number)
+            product = last_operand * number
+            backtrack(
+                end,
+                f"{expression}*{chunk}",
+                value - last_operand + product,
+                product,
+            )
+
+    backtrack(0, "", 0, 0)
+    results.sort()
+    return results
+
+
+class MagicExpressionTests(unittest.TestCase):
+    """Unit tests restricted to the specification examples."""
+
+    def test_example_1(self) -> None:
+        self.assertEqual(magic_expression("123", 6), ["1*2*3", "1+2+3"])
+
+    def test_example_2(self) -> None:
+        self.assertEqual(magic_expression("105", 5), ["1*0+5", "10-5"])
+
+    def test_example_3(self) -> None:
+        self.assertEqual(magic_expression("232", 8), ["2*3+2", "2+3*2"])
+
+    def test_example_4(self) -> None:
+        self.assertEqual(magic_expression("1234", 10), ["1*2*3+4", "1+2+3+4"])
+
+    def test_example_5(self) -> None:
+        self.assertEqual(
+            magic_expression("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",
+            ],
+        )
+
+
+if __name__ == "__main__":
+    unittest.main()