Perl Weekly Challenge 346.
My solutions (task 1 and task 2 ) to the The Weekly Challenge - 346.
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.
My first trivial approach was to simply count the parenthesis in all valid sequences. To that end, I removed pairs () until none remain. This yields a simple one-liner:
perl -E '
for(@ARGV){$i=$_; $r=0; $r+=2 while s/\(\)//; say "$i -> $r"}
' "(()())" ")()())" "((()))()(((()" "))))((()(" "()(()"
Results:
(()()) -> 6
)()()) -> 4
((()))()(((() -> 10
))))((()( -> 2
()(() -> 4
This approach is wrong, as we are asked for the length of the longest continuous sequence of valid parenthesis, not the sum of the lengths of all valid sequences.
A second approach is to replace pairs “()” by the digit 2, and patterns of the form (n) where n is a number by n+2. A pattern of the form n() is to be relaced by n+2, and n(m) with n and m numbers is to be replaced by n+m+2. For example, (()) would be replaced by (2) which would be replaced by 4, ()()() would be replaced by 2()(), 4() and 6, and ()(()()) would be replaced 2(()()), 2(2()), 2(4), and finally, by 8. When these replacements are no longer possible, I expect a string with a number for every valid run of parenthesis. Then I just have to choose the largest of these numbers. This can be accomplished with a one-liner.
Examples
perl -MList::Util=max -E '
for(@ARGV){$i=$_;1 while s/((\d*)\((\d*)\))/$2+$3+2/e;say "$i -> ", max /\d+/g;}
' "(()())" ")()())" "((()))()(((()" "))))((()(" "()(()"
Results:
(()()) -> 6
)()()) -> 4
((()))()(((() -> 8
))))((()( -> 2
()(() -> 2
I took advantage of the /e modifier in the substitution, which allows
executing arbitrary perl code in the replacement part, and the fact
that perl may interpret empty strings as the number 0.
The full code is:
1 # Perl weekly challenge 346
2 # Task 1: Longest Parenthesis
3 #
4 # See https://wlmb.github.io/2025/11/02/PWC346/#task-1-longest-parenthesis
5 use v5.36;
6 use feature qw(try);
7 use List::Util qw(max);
8 die <<~"FIN" unless @ARGV;
9 Usage: $0 S0 S1...
10 to find the longest sequence of correctly nested parenthesis, where
11 Si is a string formed of any number of parenthesis "(" and ")".
12 FIN
13 for(@ARGV){
14 try {
15 die "Expected only round parenthesis" unless /^[()]*$/;
16 my $input=$_;
17 1 while s/((\d*)\((\d*)\))/+($2||0)+($3||0)+2/e;
18 say "$input -> ", max 0, /\d+/g;
19 }
20 catch($e){warn $e}
21 }
Examples:
./ch-1.pl "(()())" ")()())" "((()))()(((()" "))))((()(" "()(()" ")("
Results:
(()()) -> 6
)()()) -> 4
((()))()(((() -> 8
))))((()( -> 2
()(() -> 2
)( -> 0
I added at the end an example to test the case with no valid parenthesis.
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")
I can intercalate all possible combinations of the two operators between the digits and eval the result. The examples also include subtraction, so I guess i should try it. Maybe I could try division also. The examples also show numbers with two or more digits. So I can also intercalate null strings.
perl -MAlgorithm::Combinatorics=tuples_with_repetition -E '
for my($s,$x)(@ARGV){@d=split "",$s;$t=tuples_with_repetition(["",qw(+ - * /)],
@d-1);@r=();while($o=$t->next){$e=join "",map({($d[$_],$o->[$_])}0..@d-2),
$d[-1];push @r, $e if eval($e)==$x;}say "$s $x -> @r";}
' 123 6 105 5 232 8 1234 10 1001 2
Results:
123 6 -> 1+2+3 1*2*3
105 5 -> 10-5 1*05 1*0+5
232 8 -> 2+3*2 2*3+2
1234 10 -> 1+2+3+4 1*2*3+4
1001 2 -> 1+001 1+00+1 1+0+01 1+0+0+1 1+0-0+1 1+0*0+1 1-00+1 1-0+01 1-0+0+1 1-0-0+1 1-0*0+1
The results seem correct, but they differ from the solutions in the
problem statement in that they include numbers with leading zeroes. I
have nothing against them, but to get the expected solutions I have to
grep the results discarding solutions with leading zeroes. This
yields a longish three-liner:
perl -MAlgorithm::Combinatorics=tuples_with_repetition -E '
for my($s,$x)(@ARGV){@d=split "", $s;$t=tuples_with_repetition(["",qw(+ - * /)
], @d-1);@r=();while($o=$t->next){$e=join "", map({($d[$_],$o->[$_])}0..@d-2),
$d[-1];push @r,$e if!($e=~/(^|\D)0\d/)&&eval($e)==$x;}say "$s $x -> @r";}
' 123 6 105 5 232 8 1234 10 1001 2
Results:
123 6 -> 1+2+3 1*2*3
105 5 -> 10-5 1*0+5
232 8 -> 2+3*2 2*3+2
1234 10 -> 1+2+3+4 1*2*3+4
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
The full code is
1 # Perl weekly challenge 346
2 # Task 2: Magic Expression
3 #
4 # See https://wlmb.github.io/2025/11/02/PWC346/#task-2-magic-expression
5 use v5.36;
6 use feature qw(try);
7 use Algorithm::Combinatorics qw(tuples_with_repetition);
8 use Scalar::Util qw(looks_like_number);
9 die <<~"FIN" unless @ARGV && @ARGV%2==0;
10 Usage: $0 S0 T0 S1 T1...
11 to intercalate arithmetic operators among the digits of string Sn
12 to produce target Tn
13 FIN
14 for my($string, $target)(@ARGV){
15 try {
16 die "Empty string" unless $string ne "";
17 die "Only digits accepted in string: $string" unless $string=~/^\d*$/;
18 die "Target doesn't looks like number: $target" unless looks_like_number($target);
19 my @digits=split "", $string;
20 my $iterator=tuples_with_repetition(["",qw(+ - * /)], @digits-1);
21 my @results=();
22 while(my $intercalate=$iterator->next){
23 my $expression=join "",
24 map({($digits[$_], $intercalate->[$_])} 0..@digits-2),
25 $digits[-1];
26 next if $expression=~/(^|\D)0\d/; # forbid leading zeros
27 my $value = eval $expression;
28 next unless defined $value; # ignore illegal expressions
29 push @results, $expression if $value==$target;
30 }
31 say "$string, $target -> @results";
32 }
33 catch($e){warn $e;}
34 }
Example:
./ch-2.pl 123 6 105 5 232 8 1234 10 1001 2
Results:
123, 6 -> 1+2+3 1*2*3
105, 5 -> 10-5 1*0+5
232, 8 -> 2+3*2 2*3+2
1234, 10 -> 1+2+3+4 1*2*3+4
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
/;
Note: Line 26:
next if $expression=~/(^|\D)0\d/; # forbid leading zeros
was originally written as
next if $expression=~/0\d/; # forbid leading zeros~
which erronelusly discarded any solution with a zero before a digit,
such as 100+1=101 which is a correct solution corresponding to the
input 1001 and the target 101. Thanks to Jo for pointing this out.
I made a few other changes after Jo’s comment.
./ch-2.pl "" 0