From 64ab7f4bcbb4d094eec4be7272f7383af32c590b Mon Sep 17 00:00:00 2001
From: mhsn <mail@mhsn.net>
Date: Thu, 19 Dec 2024 22:35:08 +0000
Subject: 2024-19 python p1

---
 2024/19/python/main.py | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 49 insertions(+)
 create mode 100644 2024/19/python/main.py

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)
-- 
cgit v1.2.3