Add Python solutions to challenge 121

4 files changed, 89 insertions, 4 deletions

diff --git a/challenge-121/paulo-custodio/Makefile b/challenge-121/paulo-custodio/Makefile
new file mode 100644
index 0000000000..6316089eb8
--- /dev/null
+++ b/challenge-121/paulo-custodio/Makefile
@@ -0,0 +1,2 @@
+all: 
+	perl ../../challenge-001/paulo-custodio/test.pl
diff --git a/challenge-121/paulo-custodio/python/ch-1.py b/challenge-121/paulo-custodio/python/ch-1.py
new file mode 100644
index 0000000000..c4f5276926
--- /dev/null
+++ b/challenge-121/paulo-custodio/python/ch-1.py
@@ -0,0 +1,30 @@
+#!/usr/bin/env python3
+
+# Challenge 121
+#
+# TASK #1 > Invert Bit
+# Submitted by: Mohammad S Anwar
+# You are given integers 0 <= $m <= 255 and 1 <= $n <= 8.
+#
+# Write a script to invert $n bit from the end of the binary representation of
+# $m and print the decimal representation of the new binary number.
+#
+# Example
+# Input: $m = 12, $n = 3
+# Output: 8
+#
+# Binary representation of $m = 00001100
+# Invert 3rd bit from the end = 00001000
+# Decimal equivalent of 00001000 = 8
+#
+# Input $m = 18, $n = 4
+# Output: 26
+#
+# Binary representation of $m = 00010010
+# Invert 4th bit from the end = 00011010
+# Decimal equivalent of 00011010 = 26
+
+import sys
+
+m, n = int(sys.argv[1]), int(sys.argv[2])
+print(m ^ (1 << (n-1)))
diff --git a/challenge-121/paulo-custodio/python/ch-2.py b/challenge-121/paulo-custodio/python/ch-2.py
new file mode 100644
index 0000000000..7a3b6f4443
--- /dev/null
+++ b/challenge-121/paulo-custodio/python/ch-2.py
@@ -0,0 +1,57 @@
+#!/usr/bin/env python3
+
+# Challenge 121
+#
+# TASK #2 > The Travelling Salesman
+# Submitted by: Jorg Sommrey
+# You are given a NxN matrix containing the distances between N cities.
+#
+# Write a script to find a round trip of minimum length visiting all N cities
+# exactly once and returning to the start.
+#
+# Example
+# Matrix: [0, 5, 2, 7]
+#         [5, 0, 5, 3]
+#         [3, 1, 0, 6]
+#         [4, 5, 4, 0]
+#
+# Output:
+#         length = 10
+#         tour = (0 2 1 3 0)
+
+import sys
+
+def read_dist():
+    dist = []
+    for line in sys.stdin:
+        row = [int(x) for x in line.split()]
+        dist.append(row)
+    return dist
+
+def shortest_tour(dist):
+    short_length = 100000
+    short_path = []
+
+    def tour(length, path):
+        nonlocal short_length, short_path
+
+        cities = list(set(range(0, len(dist))) - set(path))
+        cities.sort()
+
+        if len(cities)==0:
+            # no more cities to visit
+            length += dist[path[-1]][path[0]]
+            path.append(path[0])
+            if length < short_length:
+                short_length, short_path = length, path
+        else:
+            # try each city
+            for city in cities:
+                tour(length + dist[path[-1]][city], [*path, city])
+
+    tour(0, [0])
+    return (short_length, short_path)
+
+length, path = shortest_tour(read_dist())
+print("length =", length)
+print("tour = ("+ " ".join([str(x) for x in path]) + ")")
diff --git a/challenge-121/paulo-custodio/test.pl b/challenge-121/paulo-custodio/test.pl
deleted file mode 100644
index ba6c37260b..0000000000
--- a/challenge-121/paulo-custodio/test.pl
+++ /dev/null
@@ -1,4 +0,0 @@
-#!/usr/bin/env perl
-use Modern::Perl;
-use Test::More;
-require '../../challenge-001/paulo-custodio/test.pl';