Add Perl and Python solutions to challenge 129

7 files changed, 470 insertions, 0 deletions

diff --git a/challenge-129/paulo-custodio/perl/ch-1.pl b/challenge-129/paulo-custodio/perl/ch-1.pl
new file mode 100644
index 0000000000..c5195f9e12
--- /dev/null
+++ b/challenge-129/paulo-custodio/perl/ch-1.pl
@@ -0,0 +1,111 @@
+#!/usr/bin/env perl
+
+# TASK #1 > Root Distance
+# Submitted by: Mohammad S Anwar
+# You are given a tree and a node of the given tree.
+# 
+# Write a script to find out the distance of the given node from the root.
+# 
+# Example 1:
+# Tree:
+#         1
+#        / \
+#       2   3
+#            \
+#             4
+#            / \
+#           5   6
+# 
+# Node: 6
+# Output: 3 as the distance of given node 6 from the root (1).
+# 
+# Node: 5
+# Output: 3
+# 
+# Node: 2
+# Output: 1
+# 
+# Node: 4
+# Output: 2
+# Example 2:
+# Tree:
+#         1
+#        / \
+#       2   3
+#      /     \
+#     4       5
+#      \     /
+#       6   7
+#      / \
+#     8   9
+# 
+# Node: 7
+# Output: 3 as the distance of given node 6 from the root (1).
+# 
+# Node: 8
+# Output: 4
+# 
+# Node: 6
+# Output: 3
+
+use Modern::Perl;
+
+# tree object
+{
+    package Tree;
+    use Object::Tiny::RW qw( value left right );
+}
+
+sub parse_tree {
+    chomp(my @lines = <STDIN>);
+    @lines or die "malformed tree\n";
+    $lines[0] =~ /^( +)\d/ or die "malformed tree\n";
+    my $tree = parse_subtree(\@lines, 0, length($1));
+    return $tree;
+}
+
+sub parse_subtree {
+    my($lines, $row, $col) = @_;
+
+    # parse root
+    my $value = substr($lines->[$row], $col, 1);
+    $value =~ /\d/ or die "malformed tree\n";
+    my $node = Tree->new(value => $value);
+
+    # parse children
+    if ($row+2 <= $#{$lines}) {
+        # parse left subtree
+        if ($col-2 >= 0 &&
+			$col-2 < length($lines->[$row+1]) &&
+		    substr($lines->[$row+1], $col-1, 1) eq '/') {
+            my $child = parse_subtree($lines, $row+2, $col-2);
+            $node->left($child);
+        }
+        # parse right subtree
+        if ($col+2 < length($lines->[$row+2]) && 
+		    substr($lines->[$row+1], $col+1, 1) eq '\\') {
+            my $child = parse_subtree($lines, $row+2, $col+2);
+            $node->right($child);
+        }
+    }
+    return $node;
+}
+
+sub root_dist {
+	my($node, $value, $dist) = @_;
+	$dist ||= 0;
+	return $dist if $value == $node->value;
+	if ($node->left) {
+		my $found = root_dist($node->left, $value, $dist+1);
+		return $found if $found > 0;
+	}
+	if ($node->right) {
+		my $found = root_dist($node->right, $value, $dist+1);
+		return $found if $found > 0;
+	}
+	return -1;
+}
+	
+my $tree = parse_tree();
+my $value = shift||0;
+say(root_dist($tree, $value));
diff --git a/challenge-129/paulo-custodio/perl/ch-2.pl b/challenge-129/paulo-custodio/perl/ch-2.pl
new file mode 100644
index 0000000000..949beebbab
--- /dev/null
+++ b/challenge-129/paulo-custodio/perl/ch-2.pl
@@ -0,0 +1,63 @@
+#!/usr/bin/env perl
+
+# TASK #2 > Add Linked Lists
+# Submitted by: Mohammad S Anwar
+# You are given two linked list having single digit positive numbers.
+# 
+# Write a script to add the two linked list and create a new linked representing
+# the sum of the two linked list numbers. The two linked lists may or may not
+# have the same number of elements.
+# 
+# HINT: Just a suggestion, feel free to come up with your own unique way to deal
+# with the task. I am expecting a class representing linked list. It should have
+# methods to create a linked list given list of single digit positive numbers
+# and a method to add new member. Also have a method that takes 2 linked list
+# objects and returns a new linked list. Finally a method to print the linked
+# list object in a user friendly format.
+#
+# Example 1:
+# Input: L1 = 1 -> 2 -> 3
+#        L2 = 3 -> 2 -> 1
+# Output: 4 -> 4 -> 4
+# 
+# Example 2:
+# Input: L1 = 1 -> 2 -> 3 -> 4 -> 5
+#        L2 =           6 -> 5 -> 5
+# Output:     1 -> 3 -> 0 -> 0 -> 0
+
+use Modern::Perl;
+use HOP::Stream ':all';
+
+use Data::Dump 'dump';
+
+@ARGV==2 or die "Usage: ch-2.pl l1 l2\n";
+my $l1 = list_to_stream(split //, $ARGV[0]);
+my $l2 = list_to_stream(split //, $ARGV[1]);
+my $sum = add_streams($l1, $l2);
+say show($sum);
+
+sub reverse_stream {
+	my($in) = @_;
+	my $out;
+	while ($in) {
+		my $n = drop($in);
+		$out = node($n, $out);
+	}
+	return $out;
+}
+
+sub add_streams {
+	my($l1, $l2) = @_;
+	$l1 = reverse_stream($l1);
+	$l2 = reverse_stream($l2);
+	my($sum);
+	my $carry = 0;
+	while ($l1 || $l2 || $carry) {
+		my $n1 = drop($l1) // 0;
+		my $n2 = drop($l2) // 0;
+		my $s = $n1+$n2+$carry;
+		$sum = node($s % 10, $sum);
+		$carry = int($s / 10);
+	}
+	return $sum;
+}
diff --git a/challenge-129/paulo-custodio/python/ch-1.py b/challenge-129/paulo-custodio/python/ch-1.py
new file mode 100644
index 0000000000..78306de292
--- /dev/null
+++ b/challenge-129/paulo-custodio/python/ch-1.py
@@ -0,0 +1,111 @@
+#!/usr/bin/env python3
+
+# TASK #1 > Root Distance
+# Submitted by: Mohammad S Anwar
+# You are given a tree and a node of the given tree.
+# 
+# Write a script to find out the distance of the given node from the root.
+# 
+# Example 1:
+# Tree:
+#         1
+#        / \
+#       2   3
+#            \
+#             4
+#            / \
+#           5   6
+# 
+# Node: 6
+# Output: 3 as the distance of given node 6 from the root (1).
+# 
+# Node: 5
+# Output: 3
+# 
+# Node: 2
+# Output: 1
+# 
+# Node: 4
+# Output: 2
+# Example 2:
+# Tree:
+#         1
+#        / \
+#       2   3
+#      /     \
+#     4       5
+#      \     /
+#       6   7
+#      / \
+#     8   9
+# 
+# Node: 7
+# Output: 3 as the distance of given node 6 from the root (1).
+# 
+# Node: 8
+# Output: 4
+# 
+# Node: 6
+# Output: 3
+
+import fileinput
+import re
+import sys
+
+class Node:
+    def __init__(self, value):
+        self.value = value
+        self.left = None
+        self.right = None
+
+    def __repr__(self):
+        return "Node(value: {}, left: {}, right: {})" \
+                .format(self.value, self.left, self.right)
+
+def read_input():
+    lines = []
+    for line in fileinput.input():
+        lines.append(line)
+    return lines
+
+def parse_subtree(lines, row, col):
+    def ch(row, col):
+        if row < 0 or row >= len(lines) or \
+           col < 0 or col >= len(lines[row]):
+            return ' '
+        else:
+            return lines[row][col]
+
+    tree = Node(int(lines[row][col]))
+    if ch(row + 1, col - 1) == '/':
+        tree.left = parse_subtree(lines, row + 2, col - 2)
+    if ch(row + 1, col + 1) == '\\':
+        tree.right = parse_subtree(lines, row + 2, col + 2)
+
+    return tree
+
+def parse(lines):
+    found = re.search("^[ ]+\d", lines[0])
+    col = found.span()[1] - 1
+    return parse_subtree(lines, 0, col)
+
+def root_dist(tree, value):
+    def subtree_dist(node, value, dist):
+        if value == node.value:
+            return dist
+        if node.left:
+            found = subtree_dist(node.left, value, dist+1)
+            if found > 0:
+                return found
+        if node.right:
+            found = subtree_dist(node.right, value, dist+1)
+            if found > 0:
+                return found
+        return -1
+    
+    return subtree_dist(tree, value, 0)
+
+value = int(sys.argv.pop())
+tree = parse(read_input())
+dist = root_dist(tree, value)
+print(dist)
diff --git a/challenge-129/paulo-custodio/python/ch-2.py b/challenge-129/paulo-custodio/python/ch-2.py
new file mode 100644
index 0000000000..8cf54a885f
--- /dev/null
+++ b/challenge-129/paulo-custodio/python/ch-2.py
@@ -0,0 +1,81 @@
+#!/usr/bin/env python3
+
+# TASK #2 > Add Linked Lists
+# Submitted by: Mohammad S Anwar
+# You are given two linked list having single digit positive numbers.
+# 
+# Write a script to add the two linked list and create a new linked representing
+# the sum of the two linked list numbers. The two linked lists may or may not
+# have the same number of elements.
+# 
+# HINT: Just a suggestion, feel free to come up with your own unique way to deal
+# with the task. I am expecting a class representing linked list. It should have
+# methods to create a linked list given list of single digit positive numbers
+# and a method to add new member. Also have a method that takes 2 linked list
+# objects and returns a new linked list. Finally a method to print the linked
+# list object in a user friendly format.
+#
+# Example 1:
+# Input: L1 = 1 -> 2 -> 3
+#        L2 = 3 -> 2 -> 1
+# Output: 4 -> 4 -> 4
+# 
+# Example 2:
+# Input: L1 = 1 -> 2 -> 3 -> 4 -> 5
+#        L2 =           6 -> 5 -> 5
+# Output:     1 -> 3 -> 0 -> 0 -> 0
+
+import sys
+
+def node(head, tail):
+    return [head, tail]
+
+def drop(strm):
+    if strm is None:
+        return None, strm
+    else:
+        head = strm[0]
+        tail = strm[1]
+        return head, tail
+
+def show_strm(strm):
+    if strm is None:
+        return ""
+    else:
+        n, strm = drop(strm)
+        return str(n) + " " + show_strm(strm)
+
+def list_to_stream(lst):
+    stream = None
+    while len(lst) > 0:
+        stream = node(lst.pop(), stream)
+    return stream
+
+def reverse_stream(in_strm):
+    out_strm = None
+    while in_strm:
+        n, in_strm = drop(in_strm)
+        out_strm = node(n, out_strm)
+    return out_strm
+
+def add_streams(s1, s2):
+    s1 = reverse_stream(s1)
+    s2 = reverse_stream(s2)
+    result = None
+    carry = 0
+    while s1 or s2 or carry!=0:
+        n1, s1 = drop(s1)
+        if not n1:
+            n1 = 0
+        n2, s2 = drop(s2)
+        if not n2:
+            n2 = 0
+        s = n1+n2+carry
+        result = node(s % 10, result)
+        carry = int(s / 10)
+    return result
+
+l1 = list_to_stream([int(x) for x in sys.argv[1]])
+l2 = list_to_stream([int(x) for x in sys.argv[2]])
+s = add_streams(l1, l2)
+print(show_strm(s))
diff --git a/challenge-129/paulo-custodio/t/test-1.yaml b/challenge-129/paulo-custodio/t/test-1.yaml
new file mode 100644
index 0000000000..329a15501a
--- /dev/null
+++ b/challenge-129/paulo-custodio/t/test-1.yaml
@@ -0,0 +1,90 @@
+- setup:
+  cleanup:
+  args:     6
+  input:    |
+            |         1
+            |        / \
+            |       2   3
+            |            \
+            |             4
+            |            / \
+            |           5   6
+  output:   3
+- setup:
+  cleanup:
+  args:     5
+  input:    |
+            |         1
+            |        / \
+            |       2   3
+            |            \
+            |             4
+            |            / \
+            |           5   6
+  output:   3
+- setup:
+  cleanup:
+  args:     2
+  input:    |
+            |         1
+            |        / \
+            |       2   3
+            |            \
+            |             4
+            |            / \
+            |           5   6
+  output:   1
+- setup:
+  cleanup:
+  args:     4
+  input:    |
+            |         1
+            |        / \
+            |       2   3
+            |            \
+            |             4
+            |            / \
+            |           5   6
+  output:   2
+- setup:
+  cleanup:
+  args:     7
+  input:    |
+            |         1
+            |        / \
+            |       2   3
+            |      /     \
+            |     4       5
+            |      \     /
+            |       6   7
+            |      / \
+            |     8   9
+  output:   3
+- setup:
+  cleanup:
+  args:     8
+  input:    |
+            |         1
+            |        / \
+            |       2   3
+            |      /     \
+            |     4       5
+            |      \     /
+            |       6   7
+            |      / \
+            |     8   9
+  output:   4
+- setup:
+  cleanup:
+  args:     6
+  input:    |
+            |         1
+            |        / \
+            |       2   3
+            |      /     \
+            |     4       5
+            |      \     /
+            |       6   7
+            |      / \
+            |     8   9
+  output:   3
diff --git a/challenge-129/paulo-custodio/t/test-2.yaml b/challenge-129/paulo-custodio/t/test-2.yaml
new file mode 100644
index 0000000000..8a84409b46
--- /dev/null
+++ b/challenge-129/paulo-custodio/t/test-2.yaml
@@ -0,0 +1,10 @@
+- setup:
+  cleanup:
+  args:     123 321
+  input:
+  output:   4 4 4
+- setup:
+  cleanup:
+  args:     12345 655
+  input:
+  output:   1 3 0 0 0
diff --git a/challenge-129/paulo-custodio/test.pl b/challenge-129/paulo-custodio/test.pl
new file mode 100644
index 0000000000..ba6c37260b
--- /dev/null
+++ b/challenge-129/paulo-custodio/test.pl
@@ -0,0 +1,4 @@
+#!/usr/bin/env perl
+use Modern::Perl;
+use Test::More;
+require '../../challenge-001/paulo-custodio/test.pl';