init commit

2 files changed, 107 insertions, 0 deletions

diff --git a/13/input b/13/input
new file mode 100644
index 0000000..35be357
--- /dev/null
+++ b/13/input
@@ -0,0 +1,56 @@
+Alice would gain 54 happiness units by sitting next to Bob.
+Alice would lose 81 happiness units by sitting next to Carol.
+Alice would lose 42 happiness units by sitting next to David.
+Alice would gain 89 happiness units by sitting next to Eric.
+Alice would lose 89 happiness units by sitting next to Frank.
+Alice would gain 97 happiness units by sitting next to George.
+Alice would lose 94 happiness units by sitting next to Mallory.
+Bob would gain 3 happiness units by sitting next to Alice.
+Bob would lose 70 happiness units by sitting next to Carol.
+Bob would lose 31 happiness units by sitting next to David.
+Bob would gain 72 happiness units by sitting next to Eric.
+Bob would lose 25 happiness units by sitting next to Frank.
+Bob would lose 95 happiness units by sitting next to George.
+Bob would gain 11 happiness units by sitting next to Mallory.
+Carol would lose 83 happiness units by sitting next to Alice.
+Carol would gain 8 happiness units by sitting next to Bob.
+Carol would gain 35 happiness units by sitting next to David.
+Carol would gain 10 happiness units by sitting next to Eric.
+Carol would gain 61 happiness units by sitting next to Frank.
+Carol would gain 10 happiness units by sitting next to George.
+Carol would gain 29 happiness units by sitting next to Mallory.
+David would gain 67 happiness units by sitting next to Alice.
+David would gain 25 happiness units by sitting next to Bob.
+David would gain 48 happiness units by sitting next to Carol.
+David would lose 65 happiness units by sitting next to Eric.
+David would gain 8 happiness units by sitting next to Frank.
+David would gain 84 happiness units by sitting next to George.
+David would gain 9 happiness units by sitting next to Mallory.
+Eric would lose 51 happiness units by sitting next to Alice.
+Eric would lose 39 happiness units by sitting next to Bob.
+Eric would gain 84 happiness units by sitting next to Carol.
+Eric would lose 98 happiness units by sitting next to David.
+Eric would lose 20 happiness units by sitting next to Frank.
+Eric would lose 6 happiness units by sitting next to George.
+Eric would gain 60 happiness units by sitting next to Mallory.
+Frank would gain 51 happiness units by sitting next to Alice.
+Frank would gain 79 happiness units by sitting next to Bob.
+Frank would gain 88 happiness units by sitting next to Carol.
+Frank would gain 33 happiness units by sitting next to David.
+Frank would gain 43 happiness units by sitting next to Eric.
+Frank would gain 77 happiness units by sitting next to George.
+Frank would lose 3 happiness units by sitting next to Mallory.
+George would lose 14 happiness units by sitting next to Alice.
+George would lose 12 happiness units by sitting next to Bob.
+George would lose 52 happiness units by sitting next to Carol.
+George would gain 14 happiness units by sitting next to David.
+George would lose 62 happiness units by sitting next to Eric.
+George would lose 18 happiness units by sitting next to Frank.
+George would lose 17 happiness units by sitting next to Mallory.
+Mallory would lose 36 happiness units by sitting next to Alice.
+Mallory would gain 76 happiness units by sitting next to Bob.
+Mallory would lose 34 happiness units by sitting next to Carol.
+Mallory would gain 37 happiness units by sitting next to David.
+Mallory would gain 40 happiness units by sitting next to Eric.
+Mallory would gain 18 happiness units by sitting next to Frank.
+Mallory would gain 7 happiness units by sitting next to George.
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))