-
Notifications
You must be signed in to change notification settings - Fork 0
/
day21.py
178 lines (163 loc) · 5.95 KB
/
day21.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
from pathlib import Path
from collections import deque
from math import log10
TEST_INPUT = """root: pppw + sjmn
dbpl: 5
cczh: sllz + lgvd
zczc: 2
ptdq: humn - dvpt
dvpt: 3
lfqf: 4
humn: 5
ljgn: 2
sjmn: drzm * dbpl
sllz: 4
pppw: cczh / lfqf
lgvd: ljgn * ptdq
drzm: hmdt - zczc
hmdt: 32""".splitlines()
def parse_input(puzzle: list[str]) -> list[tuple[str, int] | tuple[str, str, str]]:
output = []
for line in puzzle:
words = line.split()
if len(words) == 2:
output.append((words[0][:-1], int(words[1])))
else:
assert len(words) == 4
output.append((words[0][:-1], words[1], words[2], words[3]))
return output
def part_one(puzzle: list[str]) -> int:
"""Find what root will be"""
instructions = parse_input(puzzle)
results = {}
while not results.get("root"):
for line in instructions:
if results.get(line[0]):
continue
if len(line) == 2:
# yay a real assignment
results[line[0]] = line[1]
else:
operation = line[2]
operand1 = results.get(line[1])
operand2 = results.get(line[3])
if operand1 is None or operand2 is None:
results[line[0]] = None
continue
if operation == "/":
results[line[0]] = operand1 // operand2
elif operation == "+":
results[line[0]] = operand1 + operand2
elif operation == "-":
results[line[0]] = operand1 - operand2
elif operation == "*":
results[line[0]] = operand1 * operand2
else:
raise ValueError(f"Unknown operation {operation}")
return results["root"]
def substitute_value(variable: str, puzzle: list[str]) -> int | str:
line = [i for i in puzzle if i.startswith(f"{variable}:")][0]
value = line.split(":")[1].strip()
if "humn" in value:
print("found dependency on human")
operands = value.split()
if operands[0] == "humn":
return (
f"(humn {operands[1]} {substitute_value(operands[2], puzzle=puzzle)})"
)
return f"({substitute_value(operands[0], puzzle)} {operands[1]} humn)"
try:
return int(value)
except ValueError:
operands = value.split()
internal = f"({substitute_value(operands[0], puzzle=puzzle)} {operands[1]} {substitute_value(operands[2], puzzle=puzzle)})"
try:
result = eval(internal.replace("/", "//"))
except NameError:
return internal
return result
def part_two(puzzle: list[str]) -> int:
"""Find what humn needs to shout so that root's operands are equal"""
target_line = [line for line in puzzle if line.startswith("root")][0]
dependencies = target_line.split(":")[1].strip().split()
operand1, _, operand2 = dependencies
print(f"must make {operand1} equal to {operand2}")
expr1 = substitute_value(operand1, puzzle)
expr2 = substitute_value(operand2, puzzle)
print(f"Solve this for humn: {expr1} = {expr2}")
try:
target = int(expr1)
except ValueError:
target = int(expr2)
expr = expr1
else:
expr = expr2
# just pick a really big number
humn = 5_000_000_000_000
turns = 0
last_value = None
last_values = deque([], maxlen=10)
in_infinite_loop = False
while True:
real_value = eval(expr)
try:
real_value = int(real_value)
except ValueError:
pass
else:
if real_value == target:
print("\n")
return humn
difference = target - real_value
if difference > 0:
if not in_infinite_loop and difference > 1_000_000_000_000:
humn -= 1_000_000_000
elif not in_infinite_loop and difference > 1_000_000_000:
humn -= 1_000_000
elif not in_infinite_loop and difference > 1_000_000:
humn -= 1_000
elif not in_infinite_loop and difference > 1000:
humn -= 100
else:
humn -= 1
else:
if not in_infinite_loop and difference < -1_000_000_000_000:
humn += 1_000_000_000
elif not in_infinite_loop and difference < -1_000_000_000:
humn += 1_000_00
elif not in_infinite_loop and difference < -1_000_000:
humn += 1_000
elif not in_infinite_loop and difference < -1000:
humn += 100
else:
humn += 1
if last_value == real_value:
repeats += 1
if repeats > 10:
raise ValueError(f"Found infinite loop at {last_value}")
else:
repeats = 0
last_value = real_value
last_values.appendleft(humn)
turns += 1
if turns > 500000 and len(set(last_values)) < 500000:
if not in_infinite_loop:
print(f"\ninfinite loop detected at {turns}")
in_infinite_loop = True
else:
if in_infinite_loop:
print(f"\nloop cleared at {turns}")
in_infinite_loop = False
if not turns % 1001:
print(
f"{turns=}\t{humn=}, {real_value=}, {last_value=}, {difference=}, {round(log10(abs(difference)))}, {last_values[0] - last_values[1]}, {in_infinite_loop=}",
end="\r",
)
def main():
part_one_result = part_one(TEST_INPUT)
assert part_one_result == 152, part_one_result
puzzle = Path("day21.txt").read_text().splitlines()
print(part_one(puzzle=puzzle))
print(part_two(puzzle=puzzle))
if __name__ == "__main__":
main()