1 files changed, 49 insertions, 0 deletions
diff --git a/2024/19/python/main.py b/2024/19/python/main.py
new file mode 100644
index 0000000..9889970
--- /dev/null
+++ b/2024/19/python/main.py
@@ -0,0 +1,49 @@
+from fileinput import input
+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)
+
+
+def drops(design, start=0):
+    curr = trie
+    for n, s in enumerate(design[start:], start=start + 1):
+        if s not in curr:
+            return
+        term, curr = curr[s]
+        if term:
+            yield n
+
+
+def match(design):
+    q = list(drops(design))
+    seen = set()
+    while q:
+        n = q.pop()
+        if n == len(design):
+            return True
+        if n in seen:
+            continue
+        seen.add(n)
+        for d in drops(design, n):
+            q.append(d)
+    return False
+
+
+silver = sum(map(match, designs))
+gold = 0
+
+print("silver:", silver)
+print("gold:", gold)