The weekly challenge 346 - Task 1: Longest Parenthesis

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-346/#TASK1
 3 #
 4 # Task 1: Longest Parenthesis
 5 # ===========================
 6 #
 7 # You are given a string containing only ( and ).
 8 #
 9 # Write a script to find the length of the longest valid parenthesis.
10 #
11 ## Example 1
12 ##
13 ## Input: $str = '(()())'
14 ## Output: 6
15 ##
16 ## Valid Parenthesis: '(()())'
17 #
18 #
19 ## Example 2
20 ##
21 ## Input: $str = ')()())'
22 ## Output: 4
23 ##
24 ## Valid Parenthesis: '()()' at positions 1-4.
25 #
26 #
27 ## Example 3
28 ##
29 ## Input: $str = '((()))()(((()'
30 ## Output: 8
31 ##
32 ## Valid Parenthesis: '((()))()' at positions 0-7.
33 #
34 #
35 ## Example 4
36 ##
37 ## Input: $str = '))))((()('
38 ## Output: 2
39 ##
40 ## Valid Parenthesis: '()' at positions 6-7.
41 #
42 #
43 ## Example 5
44 ##
45 ## Input: $str = '()(()'
46 ## Output: 2
47 ##
48 ## Valid Parenthesis: '()' at positions 0-1 and 3-4.
49 #
50 ############################################################
51 ##
52 ## discussion
53 ##
54 ############################################################
55 #
56 # We create all possible substrings and check whether they are
57 # valid. We keep track of the longest one and return it in the
58 # end.
59 
60 use v5.35;
61 
62 longest_parenthesis('(()())');
63 longest_parenthesis(')()())');
64 longest_parenthesis('((()))()(((()');
65 longest_parenthesis('))))((()(');
66 longest_parenthesis('()(()');
67 
68 sub longest_parenthesis($str) {
69     say "Input: '$str'";
70     my $longest = 0;
71     my @parts = split //, $str;
72     foreach my $i (0..$#parts) {
73         foreach my $j (0..$#parts) {
74             my $current = join("", @parts[$i..$j]);
75             if(is_valid($current)) {
76                 my $l = length($current);
77                 $longest = $l if $l > $longest;
78             }
79         }
80     }
81     say "Output: $longest";
82 }
83 
84 sub is_valid($str) {
85     my @parts = split //, $str;
86     my $open = 0;
87     foreach my $elem (@parts) {
88         if($elem eq "(") {
89             $open++;
90         } else {
91             $open--;
92         }
93         return 0 if $open < 0;
94     }
95     return $open == 0;
96 }