Add Python solution to challenge 151

4 files changed, 126 insertions, 3 deletions

diff --git a/challenge-151/paulo-custodio/perl/ch-1.pl b/challenge-151/paulo-custodio/perl/ch-1.pl
index 09184918b8..9b265b16ac 100644
--- a/challenge-151/paulo-custodio/perl/ch-1.pl
+++ b/challenge-151/paulo-custodio/perl/ch-1.pl
@@ -2,7 +2,7 @@
 
 # Challenge 151
 #
-# TASK #1 › Binary Tree Depth
+# TASK #1 > Binary Tree Depth
 # Submitted by: Mohammad S Anwar
 # You are given binary tree.
 #
diff --git a/challenge-151/paulo-custodio/perl/ch-2.pl b/challenge-151/paulo-custodio/perl/ch-2.pl
index 3581a4c94c..719fb7d336 100644
--- a/challenge-151/paulo-custodio/perl/ch-2.pl
+++ b/challenge-151/paulo-custodio/perl/ch-2.pl
@@ -2,10 +2,10 @@
 
 # Challenge 151
 #
-# TASK #2 › Rob The House
+# TASK #2 > Rob The House
 # Submitted by: Mohammad S Anwar
 # You are planning to rob a row of houses, always starting with the first
-# and moving in the same direction. However, you can’t rob two adjacent houses.
+# and moving in the same direction. However, you can't rob two adjacent houses.
 #
 # Write a script to find the highest possible gain that can be achieved.
 #
diff --git a/challenge-151/paulo-custodio/python/ch-1.py b/challenge-151/paulo-custodio/python/ch-1.py
new file mode 100644
index 0000000000..ede0f99b16
--- /dev/null
+++ b/challenge-151/paulo-custodio/python/ch-1.py
@@ -0,0 +1,85 @@
+#!/usr/bin/env python3
+
+# Challenge 151
+#
+# TASK #1 > Binary Tree Depth
+# Submitted by: Mohammad S Anwar
+# You are given binary tree.
+#
+# Write a script to find the minimum depth.
+#
+# The minimum depth is the number of nodes from the root to the nearest leaf
+# node (node without any children).
+#
+# Example 1:
+# Input: '1 | 2 3 | 4 5'
+#
+#                 1
+#                / \
+#               2   3
+#              / \
+#             4   5
+#
+# Output: 2
+#
+# Example 2:
+# Input: '1 | 2 3 | 4 *  * 5 | * 6'
+#
+#                 1
+#                / \
+#               2   3
+#              /     \
+#             4       5
+#              \
+#               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_tree(lines):
+    found = re.search(r'^[ ]+\d', lines[0])
+    col = found.span()[1] - 1
+    return parse_subtree(lines, 0, col)
+
+def min_depth(tree):
+    if not tree:
+        return 0
+    else:
+        return 1+min(min_depth(tree.left), min_depth(tree.right))
+
+tree = parse_tree(read_input())
+print(min_depth(tree))
diff --git a/challenge-151/paulo-custodio/python/ch-2.py b/challenge-151/paulo-custodio/python/ch-2.py
new file mode 100644
index 0000000000..ad18d07d6c
--- /dev/null
+++ b/challenge-151/paulo-custodio/python/ch-2.py
@@ -0,0 +1,38 @@
+#!/usr/bin/env python3
+
+# Challenge 151
+#
+# TASK #2 > Rob The House
+# Submitted by: Mohammad S Anwar
+# You are planning to rob a row of houses, always starting with the first
+# and moving in the same direction. However, you can't rob two adjacent houses.
+#
+# Write a script to find the highest possible gain that can be achieved.
+#
+# Example 1:
+# Input: @valuables = (2, 4, 5);
+# Output: 7
+#
+# If we rob house (index=0) we get 2 and then the only house we can rob is
+# house (index=2) where we have 5.
+# So the total valuables in this case is (2 + 5) = 7.
+#
+# Example 2:
+# Input: @valuables = (4, 2, 3, 6, 5, 3);
+# Output: 13
+#
+# The best choice would be to first rob house (index=0) then rob house (index=3) then finally house (index=5).
+# This would give us 4 + 6 + 3 =13.
+
+import sys
+
+def max_gain(valuables):
+    gain = valuables[0]
+    max_next = 0
+    for i in range(2, len(valuables)):
+        next = max_gain(valuables[i:])
+        max_next = max(max_next, next)
+    return gain+max_next
+
+valuables = list(map(int, sys.argv[1:]))
+print(max_gain(valuables))