Merge pull request #12964 from LubosKolouch/master

Add Perl and Python solutions for challenge 346

9 files changed, 543 insertions, 20 deletions

diff --git a/challenge-331/lubos-kolouch/perl/ch-1.pl b/challenge-331/lubos-kolouch/perl/ch-1.pl
new file mode 100644
index 0000000000..64a049ad6c
--- /dev/null
+++ b/challenge-331/lubos-kolouch/perl/ch-1.pl
@@ -0,0 +1,39 @@
+#!/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(Str);
+use Test::More;
+
+=pod
+
+=head1 PURPOSE
+
+Return the length of the final word in a string, ignoring any leading or
+trailing whitespace. Words are sequences of non-whitespace characters.
+
+=head1 ALGORITHM
+
+We validate the argument with L<Type::Params> to ensure a defined string. The
+string is scanned for word tokens using a regular expression; if at least one
+word is found we report the length of the final token, otherwise we return zero.
+
+=cut
+
+## no critic (Subroutines::ProhibitSubroutinePrototypes)
+sub last_word_length ($text) {
+    state $check = compile(Str);
+    my ($str) = $check->($text);
+
+    my @words = $str =~ /(\S+)/g;
+    return @words ? length( $words[-1] ) : 0;
+}
+
+# Examples supplied by the specification.
+is( last_word_length('The Weekly Challenge'), 9, 'Example 1' );
+is( last_word_length('   Hello   World    '), 5, 'Example 2' );
+is( last_word_length('Let\'s begin the fun'), 3, 'Example 3' );
+
+done_testing();
diff --git a/challenge-331/lubos-kolouch/perl/ch-2.pl b/challenge-331/lubos-kolouch/perl/ch-2.pl
new file mode 100644
index 0000000000..0f3f198525
--- /dev/null
+++ b/challenge-331/lubos-kolouch/perl/ch-2.pl
@@ -0,0 +1,65 @@
+#!/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(Str);
+use Test::More;
+
+=pod
+
+=head1 PURPOSE
+
+Decide whether two strings are buddy strings, i.e. whether exactly one swap of
+two characters in C<$source> can produce C<$target>. Identical strings are
+considered buddies if any character occurs more than once.
+
+=head1 ALGORITHM
+
+Inputs are validated with L<Type::Params>. If lengths differ we immediately
+return false. Otherwise we collect positions where the characters differ; more
+than two mismatches disqualify the pair. Two mismatches form buddies when the
+characters cross-match, while zero mismatches form buddies only if the string
+contains a duplicate character.
+
+=cut
+
+## no critic (Subroutines::ProhibitSubroutinePrototypes)
+sub are_buddy_strings ( $source, $target ) {
+    state $check = compile( Str, Str );
+    my ( $src, $tgt ) = $check->( $source, $target );
+
+    return 0 if length($src) != length($tgt);
+
+    my @diff;
+    for my $idx ( 0 .. length($src) - 1 ) {
+        my $s_char = substr $src, $idx, 1;
+        my $t_char = substr $tgt, $idx, 1;
+        next if $s_char eq $t_char;
+
+        push @diff, [ $s_char, $t_char ];
+        return 0 if @diff > 2;
+    }
+
+    if ( @diff == 0 ) {
+        my %seen;
+        for my $char ( split //, $src ) {
+            return 1 if ++$seen{$char} > 1;
+        }
+        return 0;
+    }
+
+    return
+         @diff == 2
+      && $diff[0][0] eq $diff[1][1]
+      && $diff[0][1] eq $diff[1][0];
+}
+
+# Examples supplied by the specification.
+is( are_buddy_strings( 'fuck', 'fcuk' ), 1, 'Example 1' );
+is( are_buddy_strings( 'love', 'love' ), 0, 'Example 2' );
+is( are_buddy_strings( 'fodo', 'food' ), 1, 'Example 3' );
+is( are_buddy_strings( 'feed', 'feed' ), 1, 'Example 4' );
+
+done_testing();
diff --git a/challenge-331/lubos-kolouch/python/ch-1.py b/challenge-331/lubos-kolouch/python/ch-1.py
new file mode 100644
index 0000000000..f4206c36fa
--- /dev/null
+++ b/challenge-331/lubos-kolouch/python/ch-1.py
@@ -0,0 +1,41 @@
+#!/usr/bin/env python3
+"""
+Task 1: Last Word
+
+Determine the length of the final word within a string, trimming any
+whitespace that may precede or follow the words. Words are contiguous
+sequences of non-whitespace characters.
+"""
+from __future__ import annotations
+
+import unittest
+
+
+def last_word_length(text: str) -> int:
+    """
+    Return the length of the last word found in `text`.
+
+    Args:
+        text: Input string that may contain leading/trailing whitespace.
+
+    Returns:
+        Length of the final word if present, otherwise zero.
+    """
+    words: list[str] = text.split()
+    return len(words[-1]) if words else 0
+
+
+class LastWordTests(unittest.TestCase):
+
+    def test_example_1(self) -> None:
+        self.assertEqual(last_word_length("The Weekly Challenge"), 9)
+
+    def test_example_2(self) -> None:
+        self.assertEqual(last_word_length("   Hello   World    "), 5)
+
+    def test_example_3(self) -> None:
+        self.assertEqual(last_word_length("Let's begin the fun"), 3)
+
+
+if __name__ == "__main__":
+    unittest.main()
diff --git a/challenge-331/lubos-kolouch/python/ch-2.py b/challenge-331/lubos-kolouch/python/ch-2.py
new file mode 100644
index 0000000000..802c11154e
--- /dev/null
+++ b/challenge-331/lubos-kolouch/python/ch-2.py
@@ -0,0 +1,61 @@
+#!/usr/bin/env python3
+"""
+Task 2: Buddy Strings
+
+Given two strings of equal length, determine whether swapping a single pair of
+characters in the source string can produce the target string. Identical
+strings are considered buddies when any character appears at least twice.
+"""
+from __future__ import annotations
+
+import unittest
+
+
+def are_buddy_strings(source: str, target: str) -> bool:
+    """
+    Decide whether `source` and `target` form a pair of buddy strings.
+
+    Args:
+        source: Original string.
+        target: Desired string after at most one swap.
+
+    Returns:
+        True when a single swap (or a swap of identical characters) can make
+        the strings equal, otherwise False.
+    """
+    if len(source) != len(target):
+        return False
+
+    if source == target:
+        # Identical strings are buddies if any character repeats.
+        return len(set(source)) < len(source)
+
+    differences: list[tuple[str,
+                            str]] = [(s_char, t_char)
+                                     for s_char, t_char in zip(source, target)
+                                     if s_char != t_char]
+
+    if len(differences) != 2:
+        return False
+
+    (first_source, first_target), (second_source, second_target) = differences
+    return first_source == second_target and first_target == second_source
+
+
+class BuddyStringTests(unittest.TestCase):
+
+    def test_example_1(self) -> None:
+        self.assertTrue(are_buddy_strings("fuck", "fcuk"))
+
+    def test_example_2(self) -> None:
+        self.assertFalse(are_buddy_strings("love", "love"))
+
+    def test_example_3(self) -> None:
+        self.assertTrue(are_buddy_strings("fodo", "food"))
+
+    def test_example_4(self) -> None:
+        self.assertTrue(are_buddy_strings("feed", "feed"))
+
+
+if __name__ == "__main__":
+    unittest.main()
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()