Add Python solution to challenge 128

2 files changed, 141 insertions, 0 deletions

diff --git a/challenge-128/paulo-custodio/python/ch-1.py b/challenge-128/paulo-custodio/python/ch-1.py
new file mode 100644
index 0000000000..2a0d27b894
--- /dev/null
+++ b/challenge-128/paulo-custodio/python/ch-1.py
@@ -0,0 +1,74 @@
+#!/usr/bin/env python3
+
+# TASK #1 > Maximum Sub-Matrix
+# Submitted by: Mohammad S Anwar
+# You are given m x n binary matrix having 0 or 1.
+#
+# Write a script to find out maximum sub-matrix having only 0.
+#
+# Example 1:
+# Input : [ 1 0 0 0 1 0 ]
+#         [ 1 1 0 0 0 1 ]
+#         [ 1 0 0 0 0 0 ]
+#
+# Output: [ 0 0 0 ]
+#         [ 0 0 0 ]
+# Example 2:
+# Input : [ 0 0 1 1 ]
+#         [ 0 0 0 1 ]
+#         [ 0 0 1 0 ]
+#
+# Output: [ 0 0 ]
+#         [ 0 0 ]
+#         [ 0 0 ]
+
+import fileinput
+import re
+
+def read_input():
+    lines = []
+    for line in fileinput.input():
+        lines.append(line)
+    return lines
+
+def parse_matrix(lines):
+    mx = []
+    for line in lines:
+        found = re.match(r"^\s*\[([01 ]+)\]\s*$", line)
+        if found:
+            row = [int(x) for x in found.group(1).split()]
+            mx.append(row)
+    return mx
+
+def print_matrix(mx):
+    for row in mx:
+        print("[ "+ " ".join([str(x) for x in row]) +" ]")
+
+def find_zeros(mx):
+    def all_zeros(mx, r1, c1, r2, c2):
+        for r in range(r1, r2+1):
+            for c in range(c1, c2+1):
+                if mx[r][c]!=0:
+                    return False
+        return True
+
+    max_rows,max_cols = 0,0
+    for r1 in range(0, len(mx)):
+        for c1 in range(0, len(mx[r1])):
+            if mx[r1][c1]==0:
+                for r2 in range(r1, len(mx)):
+                    for c2 in range(c1, len(mx[r1])):
+                        if mx[r2][c2]==0:
+                            rows,cols = r2-r1+1,c2-c1+1
+                            if rows*cols > max_rows*max_cols:
+                                if all_zeros(mx, r1, c1, r2, c2):
+                                    max_rows,max_cols = rows,cols
+    submx = []
+    for r in range(0, max_rows):
+        submx.append([0]*max_cols)
+
+    return submx
+
+mx = parse_matrix(read_input())
+submx = find_zeros(mx);
+print_matrix(submx)
diff --git a/challenge-128/paulo-custodio/python/ch-2.py b/challenge-128/paulo-custodio/python/ch-2.py
new file mode 100644
index 0000000000..ce50be00a6
--- /dev/null
+++ b/challenge-128/paulo-custodio/python/ch-2.py
@@ -0,0 +1,67 @@
+#!/usr/bin/env python3
+
+# TASK #2 > Minimum Platforms
+# Submitted by: Mohammad S Anwar
+# You are given two arrays of arrival and departure times of trains at a railway
+# station.
+#
+# Write a script to find out the minimum number of platforms needed so that no
+# train needs to wait.
+#
+# Example 1:
+# Input: @arrivals   = (11:20, 14:30)
+#        @departures = (11:50, 15:00)
+# Output: 1
+#
+#     The 1st arrival of train is at 11:20 and this is the only train at the
+#     station, so you need 1 platform.
+#     Before the second arrival at 14:30, the first train left the station at
+#     11:50, so you still need only 1 platform.
+# Example 2:
+# Input: @arrivals   = (10:20, 11:00, 11:10, 12:20, 16:20, 19:00)
+#        @departures = (10:30, 13:20, 12:40, 12:50, 20:20, 21:20)
+# Output: 3
+#
+#     Between 12:20 and 12:40, there would be at least 3 trains at the station,
+#     so we need minimum 3 platforms.
+
+import time
+
+def parse_arrivals_departures():
+    def parse_times():
+        line = input()
+        times = [time.strptime(x, "%H:%M") for x in line.split()]
+        return times
+
+    arrivals = parse_times()
+    departures = parse_times()
+    stops = []
+    while len(arrivals) > 0 and len(departures) > 0:
+        stops.append([arrivals.pop(0), departures.pop(0)])
+    return stops
+
+def allocate_platforms(stops):
+    platforms = []
+    
+    def platform_free(platform, s, e):
+        for stop in platform:
+            if (s >= stop[0] and s <  stop[1]) or \
+               (e >= stop[0] and e <  stop[1]) or \
+               (s <  stop[0] and e >= stop[1]):
+                return False
+        return True
+
+    def allocate_stop(s, e):
+        for platform in platforms:
+            if platform_free(platform, s, e):
+                platform.append([s, e])
+                return
+        platforms.append([[s, e]])
+    
+    for stop in stops:
+        allocate_stop(stop[0], stop[1])
+    return platforms
+
+stops = parse_arrivals_departures()
+platforms = allocate_platforms(stops)
+print(len(platforms))