Merge pull request #12982 from vinodk89/branch-for-challenge-346

Solutions for Challenge-346 (Perl)

2 files changed, 115 insertions, 0 deletions

diff --git a/challenge-346/vinod-k/perl/ch-1.pl b/challenge-346/vinod-k/perl/ch-1.pl
new file mode 100644
index 0000000000..a158fc59cf
--- /dev/null
+++ b/challenge-346/vinod-k/perl/ch-1.pl
@@ -0,0 +1,57 @@
+#!/usr/bin/perl
+
+##########################################################################
+# You are given a string containing only ( and ).
+#
+# Write a script to find the length of the longest valid parenthesis.
+##########################################################################
+
+use strict;
+use warnings;
+
+sub all_longest_valid_parentheses {
+    my ($str) = @_;
+    my @stack = (-1);
+    my $max_len = 0;
+    my @results;
+
+    for my $i (0 .. length($str)-1) {
+        if (substr($str, $i, 1) eq '(') {
+            push @stack, $i;
+        } else {
+            pop @stack;
+            if (@stack) {
+                my $len = $i - $stack[-1];
+                if ($len > $max_len) {
+                    $max_len = $len;
+                    @results = ([$stack[-1] + 1, $i]);
+                } elsif ($len == $max_len && $len > 0) {
+                    push @results, [$stack[-1] + 1, $i];
+                }
+            } else {
+                push @stack, $i;
+            }
+        }
+    }
+    return ($max_len, @results);
+}
+
+# Example usage:
+for my $str ('(()())', ')()())', '((()))()(((()', '))))((()(', '()(()') {
+    my ($len, @subs) = all_longest_valid_parentheses($str);
+
+    print "Input: \$str = '$str'\n";
+    print "Output: $len\n";
+    if ($len > 0) {
+        print "Valid Parenthesis: ";
+        my @out;
+        for my $r (@subs) {
+            my ($start, $end) = @$r;
+            push @out, "'" . substr($str, $start, $len) . "' at positions $start-$end";
+        }
+        print join(" and ", @out), ".\n";
+    } else {
+        print "No valid parenthesis.\n";
+    }
+    print "\n";
+}
diff --git a/challenge-346/vinod-k/perl/ch-2.pl b/challenge-346/vinod-k/perl/ch-2.pl
new file mode 100644
index 0000000000..787634583b
--- /dev/null
+++ b/challenge-346/vinod-k/perl/ch-2.pl
@@ -0,0 +1,58 @@
+#!/usr/bin/perl
+
+##########################################################################
+# 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.
+##########################################################################
+
+use strict;
+use warnings;
+
+sub add_operators_recursive {
+    my ($digits, $target, $pos, $expr, $prev, $value, $result) = @_;
+    if ($pos == length($digits)) {
+        if ($value == $target) {
+            push @$result, $expr;
+        }
+        return;
+    }
+
+    for my $i ($pos+1 .. length($digits)) {
+        my $part = substr($digits, $pos, $i - $pos);
+        next if length($part) > 1 && substr($part, 0, 1) eq '0';
+        my $num = int($part);
+
+        if ($pos == 0) {
+            add_operators_recursive($digits, $target, $i, $part, $num, $num, $result);
+        } else {
+            add_operators_recursive($digits, $target, $i, "$expr+$part", $num, $value + $num, $result);
+            add_operators_recursive($digits, $target, $i, "$expr-$part", -$num, $value - $num, $result);
+            add_operators_recursive($digits, $target, $i, "$expr*$part", $prev*$num, $value - $prev + $prev*$num, $result);
+        }
+    }
+}
+
+sub add_operators {
+    my ($digits, $target) = @_;
+    my @result;
+    add_operators_recursive($digits, $target, 0, "", 0, 0, \@result);
+    return @result;
+}
+
+# string and target
+my @examples = (
+    ["123", 6],
+    ["105", 5],
+    ["232", 8],
+    ["1234", 10],
+    ["1001", 2]
+);
+
+for my $ex (@examples) {
+    my ($str, $target) = @$ex;
+    my @output = add_operators($str, $target);
+    print "Input: \$str = \"$str\", \$target = $target\n";
+    print "Output: (" . join(", ", @output) . ")\n\n";
+}