aoc2023/d8.py

106 lines
2.4 KiB
Python

import lib
EXAMPLE = """
LLR
AAA = (BBB, BBB)
BBB = (AAA, ZZZ)
ZZZ = (ZZZ, ZZZ)
"""
EXAMPLE2 = """
LR
11A = (11B, XXX)
11B = (XXX, 11Z)
11Z = (11B, XXX)
22A = (22B, XXX)
22B = (22C, 22C)
22C = (22Z, 22Z)
22Z = (22B, 22B)
XXX = (XXX, XXX)
"""
def solve(lines: list[str]):
res = 0
elems = {}
for (i, line) in enumerate(lines):
if i == 0:
first = list(line)
else:
left, pair = line.split("=")
left = left.strip()
pair = pair.replace("(", "").replace(")", "").strip().split(", ")
elems[left] = pair
i = 0
start = "AAA"
while start != "ZZZ":
dir = first[i % len(first)]
if dir == "L":
start = elems[start][0]
elif dir == "R":
start = elems[start][1]
else:
raise Exception("Unex")
i += 1
return i
def solve2(lines: list[str]):
res = 0
elems = {}
starts = []
ends = {}
for (i, line) in enumerate(lines):
if i == 0:
first = list(line)
else:
left, pair = line.split("=")
left = left.strip()
if left.endswith("A"):
starts.append(left)
if left.endswith("Z"):
ends[left] = 0
pair = pair.replace("(", "").replace(")", "").strip().split(", ")
elems[left] = pair
i = 0
while True:
new_starts = []
for start in starts:
dir = first[i % len(first)]
if dir == "L":
new_starts.append(elems[start][0])
elif dir == "R":
new_starts.append(elems[start][1])
else:
raise Exception("Unex")
i += 1
for start in new_starts:
if start in ends and ends[start] == 0:
ends[start] = i
starts = new_starts
for e in ends.values():
if e == 0:
break
else:
break
# 25:00
return lib.lcm(ends.values())
def main():
lines = lib.str_to_lines_no_empty(EXAMPLE)
print("Example 1:", solve(lines))
lines = lib.str_to_lines_no_empty(open("i8.txt").read())
print("Solution 1:", solve(lines))
lines = lib.str_to_lines_no_empty(EXAMPLE2)
print("Example 2:", solve2(lines))
lines = lib.str_to_lines_no_empty(open("i8.txt").read())
print("Solution 2:", solve2(lines))
if __name__ == "__main__":
main()