summaryrefslogtreecommitdiff
path: root/19_2023.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-06-15 22:20:32 -0600
committerJack Sangdahl <[email protected]>2024-06-15 22:20:32 -0600
commit8e313e2614c7a0fe5af924febdbacc650e33835e (patch)
tree63426b6942ceebe17708140c972a7d7451bd2f74 /19_2023.py
downloadaoc-8e313e2614c7a0fe5af924febdbacc650e33835e.tar.gz
aoc-8e313e2614c7a0fe5af924febdbacc650e33835e.zip
intial
Diffstat (limited to '19_2023.py')
-rw-r--r--19_2023.py111
1 files changed, 111 insertions, 0 deletions
diff --git a/19_2023.py b/19_2023.py
new file mode 100644
index 0000000..55b7755
--- /dev/null
+++ b/19_2023.py
@@ -0,0 +1,111 @@
+import sys
+import re
+from copy import deepcopy
+from math import gcd
+from collections import defaultdict, Counter, deque
+import heapq
+
+D = open(sys.argv[1]).read().strip()
+L = D.split("\n")
+G = [[c for c in row] for row in L]
+R = len(G)
+C = len(G[0])
+
+rules, parts = D.split("\n\n")
+R = {}
+for rule in rules.split("\n"):
+ name, rest = rule.split("{")
+ R[name] = rest[:-1]
+
+
+def accepted(part):
+ state = "in"
+ while True:
+ rule = R[state]
+ for cmd in rule.split(","):
+ applies = True
+ res = cmd
+ if ":" in cmd:
+ cond, res = cmd.split(":")
+ var = cond[0]
+ op = cond[1]
+ n = int(cond[2:])
+ if op == ">":
+ applies = part[var] > n
+ else:
+ applies = part[var] < n
+ if applies:
+ if res == "A":
+ return True
+ if res == "R":
+ return False
+ state = res
+ break
+
+
+ans = 0
+for part in parts.split("\n"):
+ part = part[1:-1]
+ part = {x.split("=")[0]: int(x.split("=")[1]) for x in part.split(",")}
+ if accepted(part):
+ ans += part["x"] + part["m"] + part["a"] + part["s"]
+print(ans)
+
+
+def new_range(op, n, lo, hi):
+ if op == ">":
+ lo = max(lo, n + 1)
+ elif op == "<":
+ hi = min(hi, n - 1)
+ elif op == ">=":
+ lo = max(lo, n)
+ elif op == "<=":
+ hi = min(hi, n)
+ else:
+ assert False
+ return (lo, hi)
+
+
+def new_ranges(var, op, n, xl, xh, ml, mh, al, ah, sl, sh):
+ if var == "x":
+ xl, xh = new_range(op, n, xl, xh)
+ elif var == "m":
+ ml, mh = new_range(op, n, ml, mh)
+ elif var == "a":
+ al, ah = new_range(op, n, al, ah)
+ elif var == "s":
+ sl, sh = new_range(op, n, sl, sh)
+ return (xl, xh, ml, mh, al, ah, sl, sh)
+
+
+# x m a s
+ans = 0
+Q = deque([("in", 1, 4000, 1, 4000, 1, 4000, 1, 4000)])
+while Q:
+ state, xl, xh, ml, mh, al, ah, sl, sh = Q.pop()
+ if xl > xh or ml > mh or al > ah or sl > sh:
+ continue
+ if state == "A":
+ score = (xh - xl + 1) * (mh - ml + 1) * (ah - al + 1) * (sh - sl + 1)
+ ans += score
+ continue
+ elif state == "R":
+ continue
+ else:
+ rule = R[state]
+ for cmd in rule.split(","):
+ applies = True
+ res = cmd
+ if ":" in cmd:
+ cond, res = cmd.split(":")
+ var = cond[0]
+ op = cond[1]
+ n = int(cond[2:])
+ Q.append((res, *new_ranges(var, op, n, xl, xh, ml, mh, al, ah, sl, sh)))
+ xl, xh, ml, mh, al, ah, sl, sh = new_ranges(
+ var, "<=" if op == ">" else ">=", n, xl, xh, ml, mh, al, ah, sl, sh
+ )
+ else:
+ Q.append((res, xl, xh, ml, mh, al, ah, sl, sh))
+ break
+print(ans)