1 files changed, 51 insertions, 0 deletions
diff --git a/13/solution.py b/13/solution.py
new file mode 100644
index 0000000..af0362b
--- /dev/null
+++ b/13/solution.py
@@ -0,0 +1,51 @@
+"""Advent of Code 2015, day 15"""
+
+from collections import defaultdict
+from itertools import combinations
+from functools import cache
+from typing import TypeVar, Generic
+
+T = TypeVar('T')
+class WeightedGraph(Generic[T]):
+    nodes: set[T]
+    weights: defaultdict[tuple[T, T], int]
+    def __init__(self):
+        self.nodes = set()
+        self.weights = defaultdict(int)
+    def add_edge(self, a, b, weight):
+        self.nodes.add(a)
+        self.nodes.add(b)
+        self.weights[tuple(sorted((a, b)))] = weight
+    def get_edge(self, a, b):
+        return self.weights[tuple(sorted((a, b)))]
+
+def part1(graph: WeightedGraph[str]) -> int:
+    @cache
+    def max_happiness(first_guest: str, guest: str, remaining: frozenset[str]) -> int:
+        remaining = remaining - {guest}
+        if len(remaining) == 0:
+            return graph.get_edge(first_guest, guest)
+        return max(graph.get_edge(guest, other) + max_happiness(first_guest, other, remaining) for other in remaining)
+    return max(max_happiness(guest, guest, frozenset(graph.nodes)) for guest in graph.nodes)
+
+def part2(graph: WeightedGraph[str]) -> int:
+    for guest in graph.nodes.copy():
+        graph.add_edge(guest, 'Me', 0)
+    return part1(graph)
+
+if __name__ == '__main__':
+    guests = set()
+    edges = dict()
+    with open('input') as f:
+        for l in f:
+            a, _, what, how_much, _, _, _, _, _, _, b = l.rstrip()[:-1].split()
+            guests.add(a)
+            guests.add(b)
+            if what == 'lose':
+                how_much = -int(how_much)
+            edges[(a, b)] = int(how_much)
+    g = WeightedGraph()
+    for a, b in combinations(guests, 2):
+        g.add_edge(a, b, edges[(a, b)] + edges[(b, a)])
+    print(part1(g))
+    print(part2(g))