Merge pull request #1583 from andrezgz/challenge-056

challenge-056 andrezgz solution

2 files changed, 122 insertions, 0 deletions

diff --git a/challenge-056/andrezgz/perl/ch-1.pl b/challenge-056/andrezgz/perl/ch-1.pl
new file mode 100644
index 0000000000..8bba832d66
--- /dev/null
+++ b/challenge-056/andrezgz/perl/ch-1.pl
@@ -0,0 +1,42 @@
+#!/usr/bin/perl
+
+# https://perlweeklychallenge.org/blog/perl-weekly-challenge-056/
+# Task #1
+#
+# Diff-K
+# You are given an array @N of positive integers (sorted) and another non negative integer k.
+#
+# Write a script to find if there exists 2 indices i and j such that A[i] - A[j] = k and i != j.
+#
+# It should print the pairs of indices, if any such pairs exist.
+#
+# Example:
+#
+#     @N = (2, 7, 9)
+#     $k = 2
+# Output : 2,1
+
+use strict;
+use warnings;
+
+my $usage = "Usage: $0 <sum> <n1> <n2> ...\n";
+
+my $k = shift or die $usage;
+my @sorted = sort {$a <=> $b } @ARGV;
+die $usage if @sorted < 2;
+
+OUT: for my $i (reverse 0 .. @sorted - 1) {
+    for my $j (reverse 0 .. $i-1) {
+        next OUT if $sorted[$i] - $sorted[$j] > $k; #avoid checking further
+        print "($i,$j)\n"  if $sorted[$i] - $sorted[$j] == $k;
+    }
+}
+
+__END__
+
+./ch-1.pl 2 2 7 9
+(2,1)
+
+./ch-1.pl 3 2 7 9 10 11 12
+(5,2)
+(3,1)
diff --git a/challenge-056/andrezgz/perl/ch-2.pl b/challenge-056/andrezgz/perl/ch-2.pl
new file mode 100644
index 0000000000..93ef4c63ca
--- /dev/null
+++ b/challenge-056/andrezgz/perl/ch-2.pl
@@ -0,0 +1,80 @@
+#!/usr/bin/perl
+
+# https://perlweeklychallenge.org/blog/perl-weekly-challenge-056/
+# Task #2
+#
+# Path Sum
+# You are given a binary tree and a sum, write a script to find
+# if the tree has a path such that adding up all the values along the path
+# equals the given sum. Only complete paths (from root to leaf node)
+# may be considered for a sum.
+#
+# Example
+# Given the below binary tree and sum = 22,
+#
+#           5
+#          / \
+#         4   8
+#        /   / \
+#       11  13  9
+#      /  \      \
+#     7    2      1
+# For the given binary tree, the partial path sum 5 -> 8 -> 9 = 22 is not valid.
+#
+# The script should return the path 5 -> 4 -> 11 -> 2 whose sum is 22.
+
+use strict;
+use warnings;
+
+my $sum = shift || 22;
+
+my $tree = {
+            v => 5,
+            l => {
+                v => 4,
+                l => {
+                    v => 11,
+                    l => { v => 7 },
+                    r => { v => 2 }
+                }
+            },
+            r => {
+                v => 8,
+                l => { v=> 13 },
+                r => {
+                    v => 9,
+                    r => { v => 1}
+                }
+            }
+};
+
+travel($tree);
+
+sub travel {
+    my $node = shift;
+    my $path = shift // [];
+
+    push @$path, $node->{v};
+
+    if (1 == scalar keys %$node) {
+        my $s = 0;
+        $s += $_ for @$path;
+        print join(' -> ',@$path).$/ if $s == $sum;
+    }
+    else {
+        foreach my $k ('l','r'){
+            next unless exists $node->{$k};
+            travel($node->{$k},$path);
+            pop @$path;
+        }
+    }
+
+}
+
+__END__
+
+./ch-2.pl 22
+5 -> 4 -> 11 -> 2
+
+./ch-2.pl 26
+5 -> 8 -> 13