1 files changed, 40 insertions, 0 deletions
diff --git a/4.py b/4.py
new file mode 100644
index 0000000..dfd7468
--- /dev/null
+++ b/4.py
@@ -0,0 +1,40 @@
+from dataclasses import dataclass
+from functools import cache
+from sys import stdin
+
+
+@dataclass(frozen=True)
+class Card:
+    id: int
+    winning: frozenset[int]
+    have: frozenset[int]
+
+    @property
+    def nmatching(self) -> int:
+        return len(self.winning & self.have)
+
+    @classmethod
+    def from_str(cls, s: str):
+        card, rest = s.split(": ")
+        _, card_id = card.split()
+        winning, have = rest.split(" | ")
+        return cls(
+            int(card_id),
+            frozenset(map(int, winning.split())),
+            frozenset(map(int, have.split())),
+        )
+
+
+cards = [Card.from_str(l.rstrip()) for l in stdin]
+cards = {c.id: c for c in cards}
+
+
+@cache
+def p2_impl(card: Card) -> int:
+    return 1 + sum(
+        p2_impl(cards[cid]) for cid in range(card.id + 1, card.id + card.nmatching + 1)
+    )
+
+
+print(sum(int(2 ** (c.nmatching - 1)) for c in cards.values()))
+print(sum(p2_impl(c) for c in cards.values()))