203 lines
4.5 KiB
Python
203 lines
4.5 KiB
Python
#!/usr/bin/env python3
|
|
|
|
import sys
|
|
|
|
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) -> list[int]:
|
|
# 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
|
|
|
|
print(102, oA, output, len(output))
|
|
# return oi == len(program)
|
|
return output
|
|
|
|
|
|
print(program, len(program))
|
|
for i in range(0, len(program), 2):
|
|
inst = program[i]
|
|
liop = program[i + 1]
|
|
print(106, i, instnames[inst], liop)
|
|
print()
|
|
|
|
# Bruteforce
|
|
indexes = list(range(len(program)))
|
|
|
|
|
|
def to_number(inps: list[int]) -> int:
|
|
A = 0
|
|
for i in indexes[::-1]:
|
|
A <<= 3
|
|
A += inps[i]
|
|
return A
|
|
|
|
|
|
inps = program.copy()
|
|
res = test(to_number(inps))
|
|
while res != program:
|
|
for i in indexes[::-1]:
|
|
j = 0
|
|
revi = - len(program) + i
|
|
while res[revi] != program[i]:
|
|
inps[i] = j
|
|
A = to_number(inps)
|
|
res = test(A)
|
|
j += 1
|
|
print("Hi")
|
|
|
|
# i = 3
|
|
# for j in range(8):
|
|
# inps = program.copy()
|
|
# inps[i] = j
|
|
# A = to_number(inps)
|
|
# test(A)
|
|
|
|
print()
|
|
|
|
# indexes = list(range(len(inps)))
|
|
# for i in indexes[::-1]:
|
|
# An = A & 0b111
|
|
# A <<= 3
|
|
# inp = program[i]
|
|
# A += inp ^ 2
|
|
# A <<= 3
|
|
# A += 1
|
|
|
|
# # Smartforce
|
|
# A = 0
|
|
# indexes = list(range(len(program)))
|
|
# for i in indexes[::-1]:
|
|
# An = A & 0b111
|
|
# A <<= 3
|
|
# inp = program[i]
|
|
# A += inp ^ 2
|
|
|
|
|
|
# # I thought it would be easy
|
|
# assoc: dict[tuple[int, int], int] = dict()
|
|
# for i in range(8):
|
|
# for j in range(8):
|
|
# out = test(i)[0]
|
|
# assoc[out] = i, j
|
|
#
|
|
# A = 0
|
|
# for p in program:
|
|
# A = A << 3
|
|
# A += assoc[p]
|
|
#
|
|
# A = assoc[7] << 6
|
|
|
|
res = test(A)
|
|
print("Ref", program)
|
|
print("Res", res)
|
|
print("Cor", res == program)
|
|
print(A)
|
|
|
|
|
|
# print(test(100000000))
|
|
#
|
|
# Amin = 2**(3*(len(program)-1))
|
|
# Amax = 2**(3*len(program))
|
|
# Amin = 0
|
|
# Amax = 7
|
|
# for A in range(Amin, Amax + 1):
|
|
# # if A % 65536 == 0:
|
|
# # print(91, A)
|
|
# if test(A):
|
|
# print(A)
|
|
# break
|
|
# A += 1
|
|
|
|
|
|
# print(",".join([str(o) for o in output]))
|