1 files changed, 42 insertions, 0 deletions
diff --git a/2024/19/python.py b/2024/19/python.py
new file mode 100755
index 0000000..efd3272
--- /dev/null
+++ b/2024/19/python.py
@@ -0,0 +1,42 @@
+#!/usr/bin/env python3
+
+from fileinput import input
+from functools import cache
+from itertools import takewhile
+
+inp = map(str.strip, input())
+towels = [t.strip() for t in next(takewhile(bool, inp)).split(",")]
+designs = [d for d in inp if d]
+
+# Construct trie
+trie = {}
+for towel in towels:
+    prev = None
+    curr = trie
+    for t in towel:
+        term, succ = curr.setdefault(t, (False, {}))
+        prev = curr
+        curr = succ
+    prev[towel[-1]] = (True, curr)
+
+
+@cache
+def steps(design, n=0):
+    if n == len(design):
+        return 1
+    ways = 0
+    curr = trie
+    for d, s in enumerate(design[n:], start=1):
+        if s not in curr:
+            return ways
+        term, curr = curr[s]
+        if term:
+            ways += steps(design, n + d)
+    return ways
+
+
+silver = sum(map(bool, map(steps, designs)))
+gold = sum(map(steps, designs))
+
+print("silver:", silver)
+print("gold:", gold)