Initial commit

1 files changed, 60 insertions, 0 deletions

diff --git a/09/main.py b/09/main.py
new file mode 100755
index 0000000..d082678
--- /dev/null
+++ b/09/main.py
@@ -0,0 +1,60 @@
+#!/usr/bin/python
+
+from itertools import permutations
+
+
+
+def parse_input(lines):
+    edges = {}
+
+    for line in lines:
+        words = line.split()
+        x = words[0]
+        y = words[2]
+        d = int(words[4])
+
+        if x not in edges:
+            edges[x] = {}
+        if y not in edges:
+            edges[y] = {}
+
+        edges[x][y] = d
+        edges[y][x] = d
+
+    return edges
+
+
+
+def solve_partn(partn, lines):
+    edges = parse_input(lines)
+    nodes = list(edges.keys())
+
+    # This is simply the famous travelling salesman problem,
+    # so exhaustively trying all routes is the only solution.
+    routes = permutations(nodes)
+    totals = []
+    for r in routes:
+        t = 0
+        for i in range(len(r) - 1):
+            t += edges[r[i]][r[i + 1]]
+        totals.append(t)
+
+    if partn == 1:
+        return min(totals)
+    else: # partn == 2
+        return max(totals)
+
+
+
+def main():
+    # Read distances (graph edges) from input text file
+    with open("input.txt", "r") as f:
+        lines = f.read().splitlines()
+
+    print("Part 1 solution:", solve_partn(1, lines)) # 207 for me
+    print("Part 2 solution:", solve_partn(2, lines)) # 804 for me
+
+
+
+if __name__ == "__main__":
+    main()