Initial commit

3 files changed, 110 insertions, 0 deletions

diff --git a/09/input.txt b/09/input.txt
new file mode 100644
index 0000000..9850564
--- /dev/null
+++ b/09/input.txt
@@ -0,0 +1,28 @@
+Faerun to Norrath = 129
+Faerun to Tristram = 58
+Faerun to AlphaCentauri = 13
+Faerun to Arbre = 24
+Faerun to Snowdin = 60
+Faerun to Tambi = 71
+Faerun to Straylight = 67
+Norrath to Tristram = 142
+Norrath to AlphaCentauri = 15
+Norrath to Arbre = 135
+Norrath to Snowdin = 75
+Norrath to Tambi = 82
+Norrath to Straylight = 54
+Tristram to AlphaCentauri = 118
+Tristram to Arbre = 122
+Tristram to Snowdin = 103
+Tristram to Tambi = 49
+Tristram to Straylight = 97
+AlphaCentauri to Arbre = 116
+AlphaCentauri to Snowdin = 12
+AlphaCentauri to Tambi = 18
+AlphaCentauri to Straylight = 91
+Arbre to Snowdin = 129
+Arbre to Tambi = 53
+Arbre to Straylight = 40
+Snowdin to Tambi = 15
+Snowdin to Straylight = 99
+Tambi to Straylight = 70
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()
diff --git a/09/test.py b/09/test.py
new file mode 100755
index 0000000..932c12b
--- /dev/null
+++ b/09/test.py
@@ -0,0 +1,22 @@
+#!/usr/bin/python
+
+import unittest
+
+import main
+
+
+
+class Examples(unittest.TestCase):
+    def test_example1(self):
+        lines = [
+            "London to Dublin = 464",
+            "London to Belfast = 518",
+            "Dublin to Belfast = 141"
+        ]
+        self.assertEqual(main.solve_partn(1, lines), 605)
+        self.assertEqual(main.solve_partn(2, lines), 982)
+
+
+
+if __name__ == "__main__":
+    unittest.main()