day 19

r0f1 · r0f1 · commit b77e29e12ef4 · 2020-12-19T21:48:51.000+01:00
diff --git a/README.md b/README.md
@@ -20,7 +20,7 @@
 |[16](https://adventofcode.com/2020/day/16)|Ticket Translation|[py](/day16/main.py), [alt](/day16/alt.py)|
 |[17](https://adventofcode.com/2020/day/17)|Conway Cubes|[py](/day17/main.py)|
 |[18](https://adventofcode.com/2020/day/18)|Operation Order|[py](/day18/main.py)|
-|[19](https://adventofcode.com/2020/day/19)|-|-|
+|[19](https://adventofcode.com/2020/day/19)|Monster Messages|[py](/day19/main.py)|
 |[20](https://adventofcode.com/2020/day/20)|-|-|
 |[21](https://adventofcode.com/2020/day/21)|-|-|
 |[22](https://adventofcode.com/2020/day/22)|-|-|
diff --git a/day19/main.py b/day19/main.py
@@ -0,0 +1,31 @@
+import re
+
+def build_regex(d, rulenum, is_part1):
+    if not is_part1:
+        if rulenum == "8":
+            return build_regex(d, "42", is_part1) + "+"
+        elif rulenum == "11":
+            a = build_regex(d, "42", is_part1)
+            b = build_regex(d, "31", is_part1)
+            return "(?:" + "|".join(f"{a}{{{n}}}{b}{{{n}}}" for n in range(1, 100)) + ")"
+
+    rule = d[rulenum]
+    if re.fullmatch(r'"."', rule):
+        return rule[1]
+    else:
+        parts = rule.split(" | ")
+        res = []
+        for part in parts:
+            nums = part.split(" ")
+            res.append("".join(build_regex(d, n, is_part1) for n in nums))
+        return "(?:" + "|".join(res) + ")"
+
+with open("input.txt") as f:
+    rules, msgs = [l.rstrip("\n") for l in f.read().split("\n\n")]
+
+d = dict([rule.split(": ") for rule in rules.split("\n")])
+msgs = [x.strip() for x in msgs.split("\n")]
+
+for is_part1 in [True, False]:
+    z = build_regex(d, "0", is_part1)
+    print(sum([bool(re.fullmatch(z, msg)) for msg in msgs]))
