diff options
| -rw-r--r-- | challenge-346/lubos-kolouch/README | 36 | ||||
| -rw-r--r-- | challenge-346/lubos-kolouch/perl/ch-1.pl | 79 | ||||
| -rw-r--r-- | challenge-346/lubos-kolouch/perl/ch-2.pl | 92 | ||||
| -rw-r--r-- | challenge-346/lubos-kolouch/python/ch-1.py | 61 | ||||
| -rw-r--r-- | challenge-346/lubos-kolouch/python/ch-2.py | 89 |
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() |