diff options
author | Jack Sangdahl <[email protected]> | 2024-06-15 22:20:32 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-06-15 22:20:32 -0600 |
commit | 8e313e2614c7a0fe5af924febdbacc650e33835e (patch) | |
tree | 63426b6942ceebe17708140c972a7d7451bd2f74 /19_2023.py | |
download | aoc-8e313e2614c7a0fe5af924febdbacc650e33835e.tar.gz aoc-8e313e2614c7a0fe5af924febdbacc650e33835e.zip |
intial
Diffstat (limited to '19_2023.py')
-rw-r--r-- | 19_2023.py | 111 |
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) |