Add Perl and Python solutions to challenge 130

7 files changed, 318 insertions, 0 deletions

diff --git a/challenge-130/paulo-custodio/perl/ch-1.pl b/challenge-130/paulo-custodio/perl/ch-1.pl
new file mode 100644
index 0000000000..c3cb2c7384
--- /dev/null
+++ b/challenge-130/paulo-custodio/perl/ch-1.pl
@@ -0,0 +1,23 @@
+#!/usr/bin/env perl
+
+# TASK #1 > Odd Number
+# Submitted by: Mohammad S Anwar
+# You are given an array of positive integers, such that all the
+# numbers appear even number of times except one number.
+# 
+# Write a script to find that integer.
+# 
+# Example 1
+# Input: @N = (2, 5, 4, 4, 5, 5, 2)
+# Output: 5 as it appears 3 times in the array where as all other
+# numbers 2 and 4 appears exactly twice.
+# Example 2
+# Input: @N = (1, 2, 3, 4, 3, 2, 1, 4, 4)
+# Output: 4
+
+use Modern::Perl;
+
+my @N = @ARGV;
+my %count; 
+$count{$_}++ for @N;
+say $_ for (grep {$count{$_}%2==1} keys %count);
diff --git a/challenge-130/paulo-custodio/perl/ch-2.pl b/challenge-130/paulo-custodio/perl/ch-2.pl
new file mode 100644
index 0000000000..5c2f5180eb
--- /dev/null
+++ b/challenge-130/paulo-custodio/perl/ch-2.pl
@@ -0,0 +1,122 @@
+#!/usr/bin/env perl
+
+# TASK #2 > Binary Search Tree
+# Submitted by: Mohammad S Anwar
+# You are given a tree.
+# 
+# Write a script to find out if the given tree is Binary Search Tree
+# (BST).
+# 
+# According to wikipedia, the definition of BST:
+# 
+# A binary search tree is a rooted binary tree, whose internal nodes
+# each store a key (and optionally, an associated value), and each has
+# two distinguished sub-trees, commonly denoted left and right. The
+# tree additionally satisfies the binary search property: the key in
+# each node is greater than or equal to any key stored in the left
+# sub-tree, and less than or equal to any key stored in the right
+# sub-tree. The leaves (final nodes) of the tree contain no key and
+# have no structure to distinguish them from one another.
+# 
+# Example 1
+# Input:
+#         8
+#        / \
+#       5   9
+#      / \
+#     4   6
+# 
+# Output: 1 as the given tree is a BST.
+# Example 2
+# Input:
+#         5
+#        / \
+#       4   7
+#      / \
+#     3   6
+# 
+# Output: 0 as the given tree is a not BST.
+
+use Modern::Perl;
+use List::Util qw( min max );
+
+# tree object
+{
+    package Tree;
+    use Object::Tiny::RW qw( value left right );
+}
+
+sub parse_tree {
+    chomp(my @lines = <>);
+    @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 subtree_min {
+	my($node) = @_;
+	my $min = $node->value;
+	if ($node->left) {
+		$min = min($min, subtree_min($node->left));
+	}
+	if ($node->right) {
+		$min = min($min, subtree_min($node->right));
+	}
+	return $min;
+}
+
+sub subtree_max {
+	my($node) = @_;
+	my $max = $node->value;
+	if ($node->left) {
+		$max = max($max, subtree_max($node->left));
+	}
+	if ($node->right) {
+		$max = max($max, subtree_max($node->right));
+	}
+	return $max;
+}
+
+sub subtree_is_bst {
+	my($node) = @_;
+	if ($node->left) {
+		return 0 if !subtree_is_bst($node->left);
+		return 0 if subtree_max($node->left) > $node->value;
+	}
+	if ($node->right) {
+		return 0 if !subtree_is_bst($node->right);
+		return 0 if subtree_min($node->right) < $node->value;
+	}
+	return 1;
+}
+
+my $tree = parse_tree();
+say subtree_is_bst($tree);
diff --git a/challenge-130/paulo-custodio/python/ch-1.py b/challenge-130/paulo-custodio/python/ch-1.py
new file mode 100644
index 0000000000..00794b20da
--- /dev/null
+++ b/challenge-130/paulo-custodio/python/ch-1.py
@@ -0,0 +1,29 @@
+#!/usr/bin/env python3
+
+# TASK #1 > Odd Number
+# Submitted by: Mohammad S Anwar
+# You are given an array of positive integers, such that all the
+# numbers appear even number of times except one number.
+# 
+# Write a script to find that integer.
+# 
+# Example 1
+# Input: @N = (2, 5, 4, 4, 5, 5, 2)
+# Output: 5 as it appears 3 times in the array where as all other
+# numbers 2 and 4 appears exactly twice.
+# Example 2
+# Input: @N = (1, 2, 3, 4, 3, 2, 1, 4, 4)
+# Output: 4
+
+import sys
+
+N = sys.argv[1:]
+count = {}
+for n in N:
+    if n not in count:
+        count[n] = 1
+    else:
+        count[n] += 1
+for n,count in count.items():
+    if count%2==1:
+        print(n)
diff --git a/challenge-130/paulo-custodio/python/ch-2.py b/challenge-130/paulo-custodio/python/ch-2.py
new file mode 100644
index 0000000000..e2e4f427f7
--- /dev/null
+++ b/challenge-130/paulo-custodio/python/ch-2.py
@@ -0,0 +1,110 @@
+#!/usr/bin/env python3
+
+# TASK #2 > Binary Search Tree
+# Submitted by: Mohammad S Anwar
+# You are given a tree.
+# 
+# Write a script to find out if the given tree is Binary Search Tree
+# (BST).
+# 
+# According to wikipedia, the definition of BST:
+# 
+# A binary search tree is a rooted binary tree, whose internal nodes
+# each store a key (and optionally, an associated value), and each has
+# two distinguished sub-trees, commonly denoted left and right. The
+# tree additionally satisfies the binary search property: the key in
+# each node is greater than or equal to any key stored in the left
+# sub-tree, and less than or equal to any key stored in the right
+# sub-tree. The leaves (final nodes) of the tree contain no key and
+# have no structure to distinguish them from one another.
+# 
+# Example 1
+# Input:
+#         8
+#        / \
+#       5   9
+#      / \
+#     4   6
+# 
+# Output: 1 as the given tree is a BST.
+# Example 2
+# Input:
+#         5
+#        / \
+#       4   7
+#      / \
+#     3   6
+# 
+# Output: 0 as the given tree is a not BST.
+
+import fileinput
+import re
+
+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 subtree_min(node):
+    min_value = node.value
+    if node.left:
+        min_value = min(min_value, subtree_min(node.left))
+    if node.right:
+        min_value = min(min_value, subtree_min(node.right))
+    return min_value
+
+def subtree_max(node):
+    max_value = node.value
+    if node.left:
+        max_value = max(max_value, subtree_max(node.left))
+    if node.right:
+        max_value = max(max_value, subtree_max(node.right))
+    return max_value
+
+def subtree_is_bst(node):
+    if node.left:
+        if not subtree_is_bst(node.left):
+            return 0
+        if subtree_max(node.left) > node.value:
+            return 0
+    if node.right:
+        if not subtree_is_bst(node.right):
+            return 0
+        if subtree_min(node.right) < node.value:
+            return 0
+    return 1
+
+tree = parse(read_input())
+print(subtree_is_bst(tree))
diff --git a/challenge-130/paulo-custodio/t/test-1.yaml b/challenge-130/paulo-custodio/t/test-1.yaml
new file mode 100644
index 0000000000..26d3ec1846
--- /dev/null
+++ b/challenge-130/paulo-custodio/t/test-1.yaml
@@ -0,0 +1,10 @@
+- setup:
+  cleanup:
+  args:     2 5 4 4 5 5 2
+  input:
+  output:   5
+- setup:
+  cleanup:
+  args:     1 2 3 4 3 2 1 4 4
+  input:
+  output:   4
diff --git a/challenge-130/paulo-custodio/t/test-2.yaml b/challenge-130/paulo-custodio/t/test-2.yaml
new file mode 100644
index 0000000000..514072061c
--- /dev/null
+++ b/challenge-130/paulo-custodio/t/test-2.yaml
@@ -0,0 +1,20 @@
+- setup:
+  cleanup:
+  args:     
+  input:    |
+            |         8
+            |        / \
+            |       5   9
+            |      / \
+            |     4   6
+  output:   1
+- setup:
+  cleanup:
+  args:     
+  input:    |
+            |         5
+            |        / \
+            |       4   7
+            |      / \
+            |     3   6
+  output:   0
diff --git a/challenge-130/paulo-custodio/test.pl b/challenge-130/paulo-custodio/test.pl
new file mode 100644
index 0000000000..ba6c37260b
--- /dev/null
+++ b/challenge-130/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';