126 lines
3.2 KiB
Python
126 lines
3.2 KiB
Python
#!/usr/bin/env python3
|
|
|
|
import sys
|
|
import rich.progress
|
|
|
|
input_file = sys.argv[1]
|
|
|
|
with open(input_file) as fd:
|
|
lines = [line.rstrip() for line in fd.readlines()]
|
|
|
|
# program 3 bits numbers
|
|
# registers A, B, C: any int
|
|
# instruction 3 bits, operand 3 bits
|
|
# literal operand, combo operand: 0-3 literal, 4-6: register A,B,C
|
|
# instruction pointer starts at 0
|
|
|
|
# 0 adv: truncated division, numerator = A, denominator 2**combo operand -> A
|
|
# 1 bxl: bitwise XOR, B ^ literal operand -> B
|
|
# 2 bst: combo operand % 8 -> B
|
|
# 3 jnz: { A = 0: nothing; A != 0: literal operand -> IP } # no increase there!
|
|
# 4 bxc: bitwise XOR, B ^ C -> B # operand ignored
|
|
# 5 out: combo operand % 8 -> output
|
|
# 6 bdv: truncated division, numerator = A, denominator 2**combo operand -> B
|
|
# 7 cdv: truncated division, numerator = A, denominator 2**combo operand -> C
|
|
|
|
instnames = ["adv", "bxl", "bst", "jnz", "bxc", "out", "bdv", "cdv"]
|
|
|
|
oA = int(lines[0].split(":")[1])
|
|
oB = int(lines[1].split(":")[1])
|
|
oC = int(lines[2].split(":")[1])
|
|
|
|
program = [int(p) for p in lines[4].split(":")[1].split(",")]
|
|
|
|
|
|
def test(oA: int) -> bool:
|
|
# print(32, "Testing", A)
|
|
|
|
ip = 0
|
|
A = oA
|
|
B = oB
|
|
C = oC
|
|
|
|
# output: list[int] = list()
|
|
oi = 0
|
|
|
|
# jumped: set[tuple[int, int, int, int]] = set()
|
|
|
|
while ip in range(len(program)):
|
|
inst = program[ip]
|
|
liop = program[ip + 1]
|
|
# print(50, ip, instnames[inst], liop)
|
|
|
|
if inst == 1:
|
|
B = B ^ liop
|
|
elif inst == 3:
|
|
if A != 0:
|
|
ip = liop
|
|
|
|
# Infinite loop prevention
|
|
# state = (ip, A, B, C)
|
|
# # print(66, state, jumped)
|
|
# if state in jumped:
|
|
# print("Infinite loop!")
|
|
# return False
|
|
# jumped.add(state)
|
|
|
|
continue
|
|
elif inst == 4:
|
|
B = B ^ C
|
|
else:
|
|
coop = liop
|
|
if liop == 4:
|
|
coop = A
|
|
elif liop == 5:
|
|
coop = B
|
|
elif liop == 6:
|
|
coop = C
|
|
|
|
if inst == 2:
|
|
B = coop % 8
|
|
elif inst == 5:
|
|
ou = coop % 8
|
|
# output.append(ou)
|
|
if oi >= len(program) or program[oi] != ou:
|
|
# if len(output) >= 6:
|
|
# print(84, oA, output)
|
|
return False
|
|
oi += 1
|
|
else:
|
|
trunc_div = A // 2**coop
|
|
if inst == 0:
|
|
A = trunc_div
|
|
elif inst == 6:
|
|
B = trunc_div
|
|
elif inst == 7:
|
|
C = trunc_div
|
|
else:
|
|
raise NotImplementedError()
|
|
|
|
ip += 2
|
|
|
|
|
|
return oi == len(program)
|
|
# return output == program
|
|
|
|
# print(program)
|
|
# for i in range(0, len(program), 2):
|
|
# inst = program[i]
|
|
# liop = program[i + 1]
|
|
# print(106, i, instnames[inst], liop)
|
|
# print()
|
|
#
|
|
# print(test(100000000))
|
|
|
|
Amin = 2**(3*(len(program)-1))
|
|
Amax = 2**(3*len(program))
|
|
|
|
for A in rich.progress.track(range(Amin, Amax+1)):
|
|
if test(A):
|
|
print(A)
|
|
break
|
|
A += 1
|
|
|
|
|
|
# print(",".join([str(o) for o in output]))
|