init commit

2 files changed, 68 insertions, 0 deletions

diff --git a/9/input b/9/input
new file mode 100644
index 0000000..97a6b63
--- /dev/null
+++ b/9/input
@@ -0,0 +1,28 @@
+Faerun to Tristram = 65
+Faerun to Tambi = 129
+Faerun to Norrath = 144
+Faerun to Snowdin = 71
+Faerun to Straylight = 137
+Faerun to AlphaCentauri = 3
+Faerun to Arbre = 149
+Tristram to Tambi = 63
+Tristram to Norrath = 4
+Tristram to Snowdin = 105
+Tristram to Straylight = 125
+Tristram to AlphaCentauri = 55
+Tristram to Arbre = 14
+Tambi to Norrath = 68
+Tambi to Snowdin = 52
+Tambi to Straylight = 65
+Tambi to AlphaCentauri = 22
+Tambi to Arbre = 143
+Norrath to Snowdin = 8
+Norrath to Straylight = 23
+Norrath to AlphaCentauri = 136
+Norrath to Arbre = 115
+Snowdin to Straylight = 101
+Snowdin to AlphaCentauri = 84
+Snowdin to Arbre = 96
+Straylight to AlphaCentauri = 107
+Straylight to Arbre = 14
+AlphaCentauri to Arbre = 46
diff --git a/9/solution.py b/9/solution.py
new file mode 100644
index 0000000..48b0c7c
--- /dev/null
+++ b/9/solution.py
@@ -0,0 +1,40 @@
+from itertools import permutations, islice
+import collections
+
+def sliding_window(iterable, n):
+    # sliding_window('ABCDEFG', 4) -> ABCD BCDE CDEF DEFG
+    it = iter(iterable)
+    window = collections.deque(islice(it, n), maxlen=n)
+    if len(window) == n:
+        yield tuple(window)
+    for x in it:
+        window.append(x)
+        yield tuple(window)
+
+def part1(nodes: set, distances: dict) -> int:
+    """
+    >>> part1(set('ABC'), {('A', 'B'): 464, ('A', 'C'): 518, ('B', 'C'): 141})
+    605
+    """
+    return min(sum(distances[tuple(sorted(edge))] for edge in sliding_window(path, 2)) for path in permutations(nodes))
+
+def part2(nodes: set, distances: dict) -> int:
+    """
+    >>> part2(set('ABC'), {('A', 'B'): 464, ('A', 'C'): 518, ('B', 'C'): 141})
+    982
+    """
+    return max(sum(distances[tuple(sorted(edge))] for edge in sliding_window(path, 2)) for path in permutations(nodes))
+
+if __name__ == '__main__':
+    nodes = set()
+    distances = dict()
+    with open('input') as f:
+        for l in f:
+            l = l.strip()
+            edge, distance = l.split(' = ')
+            edge = tuple(sorted(edge.split(' to ')))
+            nodes.add(edge[0])
+            nodes.add(edge[1])
+            distances[edge] = int(distance)
+    print(part1(nodes, distances))
+    print(part2(nodes, distances))