Add Python solution to challenge 125

2 files changed, 159 insertions, 0 deletions

diff --git a/challenge-125/paulo-custodio/python/ch-1.py b/challenge-125/paulo-custodio/python/ch-1.py
new file mode 100644
index 0000000000..e8241be92c
--- /dev/null
+++ b/challenge-125/paulo-custodio/python/ch-1.py
@@ -0,0 +1,68 @@
+#!/usr/bin/env python3
+
+# TASK #1 > Pythagorean Triples
+# Submitted by: Cheok-Yin Fung
+# You are given a positive integer $N.
+#
+# Write a script to print all Pythagorean Triples containing $N as a member.
+# Print -1 if it can't be a member of any.
+#
+# Triples with the same set of elements are considered the same, i.e. if your
+# script has already printed (3, 4, 5), (4, 3, 5) should not be printed.
+#
+# The famous Pythagorean theorem states that in a right angle triangle, the
+# length of the two shorter sides and the length of the longest side are
+# related by a2+b2 = c2.
+#
+# A Pythagorean triple refers to the triple of three integers whose lengths can
+# compose a right-angled triangle.
+#
+# Example
+#     Input: $N = 5
+#     Output:
+#         (3, 4, 5)
+#         (5, 12, 13)
+#
+#     Input: $N = 13
+#     Output:
+#         (5, 12, 13)
+#         (13, 84, 85)
+#
+#     Input: $N = 1
+#     Output:
+#         -1
+
+import sys
+from math import gcd
+
+MAX_GEN = 100
+
+def gen_pythagorean_triples():
+    out = []
+    seen = set()
+    for m in range(2, MAX_GEN+1):
+        for n in range(1, m):
+            if gcd(m, n)==1:
+                a = m*m-n*n
+                b = 2*m*n
+                c = m*m+n*n
+                if m%2==1 and n%2==1:
+                    a = a/2
+                    b = b/2
+                    c = c/2
+                if a > b:
+                    a, b = b, a
+                if (a,b) not in seen:
+                    seen.add((a,b))
+                    out.append([a, b, c])
+    return out
+
+N = int(sys.argv[1])
+pythagorean_triples = gen_pythagorean_triples()
+found = filter(lambda x : x[0]==N or x[1]==N or x[2]==N, pythagorean_triples)
+printed = False
+for triplet in found:
+    print("("+ ", ".join([str(x) for x in triplet]) +")")
+    printed = True
+if not printed:
+    print(-1)
diff --git a/challenge-125/paulo-custodio/python/ch-2.py b/challenge-125/paulo-custodio/python/ch-2.py
new file mode 100644
index 0000000000..e921273d7c
--- /dev/null
+++ b/challenge-125/paulo-custodio/python/ch-2.py
@@ -0,0 +1,91 @@
+#!/usr/bin/env python3
+
+# TASK #2 > Binary Tree Diameter
+# Submitted by: Mohammad S Anwar
+# You are given binary tree as below:
+#
+#     1
+#    / \
+#   2   5
+#  / \ / \
+# 3  4 6  7
+#        / \
+#       8  10
+#      /
+#     9
+# Write a script to find the diameter of the given binary tree.
+#
+# The diameter of a binary tree is the length of the longest path between any
+# two nodes in a tree. It doesn't have to pass through the root.
+#
+# For the above given binary tree, possible diameters (6) are:
+#
+# 3, 2, 1, 5, 7, 8, 9
+#
+# or
+#
+# 4, 2, 1, 5, 7, 8, 9
+#
+# UPDATE (2021-08-10 17:00:00 BST): Jorg Sommrey corrected the example.
+# The length of a path is the number of its edges, not the number of the
+# vertices it connects. So the diameter should be 6, not 7.
+
+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 height(node):
+    if node is None:
+        return 0
+    return 1 + max(height(node.left), height(node.right))
+
+def diameter(root):
+    if root is None:
+        return 0
+
+    lheight = height(root.left)
+    rheight = height(root.right)
+
+    ldiameter = diameter(root.left)
+    rdiameter = diameter(root.right)
+
+    return max(lheight + rheight + 1, max(ldiameter, rdiameter))-1
+
+tree = parse(read_input())
+print(diameter(tree))