2018-12-19 - Chronal Classification
(original .ipynb)
class VM(object):
def __init__(self, register, ip=-1):
self.ip = ip
self.ip_binding = None
self.register = register
self.instructions = []
self.opcodes = {
"addr": self.addr,
"addi": self.addi,
"mulr": self.mulr,
"muli": self.muli,
"banr": self.banr,
"bani": self.bani,
"borr": self.borr,
"bori": self.bori,
"setr": self.setr,
"seti": self.seti,
"gtir": self.gtir,
"gtri": self.gtri,
"gtrr": self.gtrr,
"eqir": self.eqir,
"eqri": self.eqri,
"eqrr": self.eqrr
}
def load(self, instructions):
self.instructions = []
for instruction in instructions:
if "#ip" == instruction[:3]:
_, ip_str = instruction.split(" ")
self.ip_binding = int(ip_str)
else:
op, a, b, c = instruction.split(" ")
self.instructions.append([op, int(a), int(b), int(c)])
def get_debug_state(self):
return " ".join([
f"ip={self.ip}",
str(self.register),
" ".join(str(i) for i in self.instructions[self.ip])
])
def run(self, debug=False):
while True:
try:
self.ip += 1
debug_state = self.get_debug_state()
self.step()
if debug:
print(debug_state, str(self.register))
except:
break
return self.register
def step(self):
if self.ip >= len(self.instructions):
return False
op, a, b, c = self.instructions[self.ip]
self.execute(op, a, b, c)
return True
def execute(self, opcode, a, b, c):
if self.ip_binding != None:
self.register[self.ip_binding] = self.ip
decode_int = {
0 : self.eqir,
1 : self.seti,
2 : self.eqri,
3 : self.eqrr,
4 : self.addi,
5 : self.setr,
6 : self.gtrr,
7 : self.gtri,
8 : self.muli,
9 : self.bori,
10: self.bani,
11: self.borr,
12: self.gtir,
13: self.banr,
14: self.addr,
15: self.mulr
}
decode_str = {
"eqir" : self.eqir,
"seti" : self.seti,
"eqri" : self.eqri,
"eqrr" : self.eqrr,
"addi" : self.addi,
"setr" : self.setr,
"gtrr" : self.gtrr,
"gtri" : self.gtri,
"muli" : self.muli,
"bori" : self.bori,
"bani" : self.bani,
"borr" : self.borr,
"gtir" : self.gtir,
"banr" : self.banr,
"addr" : self.addr,
"mulr" : self.mulr
}
if (type(opcode) is str):
assert(decode_str[opcode](a,b,c))
elif (type(opcode) is int):
assert(decode_int[opcode](a,b,c))
else:
raise Exception(f"opcode {opcode} is neither int nor str")
if self.ip_binding != None:
self.ip = self.register[self.ip_binding]
def any_invalid_registers(self, regs):
result = True
for reg in regs:
result = result & (reg < len(self.register))
return not result
def test_opcode(self, opcode_name, initial_register_state, a, b, c, final_register_state):
self.register = [ reg for reg in initial_register_state ]
result = self.opcodes[opcode_name](a, b, c)
return result and (self.register == final_register_state)
# addr (add register) stores into register C the result of adding register A and register B.
def addr(self, a, b, c):
if self.any_invalid_registers((a,b,c)):
return False
self.register[c] = self.register[a] + self.register[b]
return True
# addi (add immediate) stores into register C the result of adding register A and value B.
def addi(self, a, b, c):
if self.any_invalid_registers((a, c)):
return False
self.register[c] = self.register[a] + b
return True
# mulr (multiply register) stores into register C the result of multiplying register A and register B.
def mulr(self, a, b, c):
if self.any_invalid_registers((a, b, c)):
return False
self.register[c] = self.register[a] * self.register[b]
return True
# muli (multiply immediate) stores into register C the result of multiplying register A and value B.
def muli(self, a, b, c):
if self.any_invalid_registers((a, c)):
return False
self.register[c] = self.register[a] * b
return True
# banr (bitwise AND register) stores into register C the result of the bitwise AND of register A and register B.
def banr(self, a, b, c):
if self.any_invalid_registers((a, b, c)):
return False
self.register[c] = self.register[a] & self.register[b]
return True
# bani (bitwise AND immediate) stores into register C the result of the bitwise AND of register A and value B.
def bani(self, a, b, c):
if self.any_invalid_registers((a, c)):
return False
self.register[c] = self.register[a] & b
return True
# borr (bitwise OR register) stores into register C the result of the bitwise OR of register A and register B.
def borr(self, a, b, c):
if self.any_invalid_registers((a, b, c)):
return False
self.register[c] = self.register[a] | self.register[b]
return True
# bori (bitwise OR immediate) stores into register C the result of the bitwise OR of register A and value B.
def bori(self, a, b, c):
if self.any_invalid_registers((a, c)):
return False
self.register[c] = self.register[a] | b
return True
# setr (set register) copies the contents of register A into register C. (Input B is ignored.)
def setr(self, a, b, c):
if self.any_invalid_registers((a, c)):
return False
self.register[c] = self.register[a]
return True
# seti (set immediate) stores value A into register C. (Input B is ignored.)
def seti(self, a, b, c):
if self.any_invalid_registers([c]):
return False
self.register[c] = a
return True
# gtir (greater-than immediate/register) sets register C to 1 if value A is greater than register B. Otherwise, register C is set to 0.
def gtir(self, a, b, c):
if self.any_invalid_registers((c, b)):
return False
self.register[c] = int(a > self.register[b])
return True
# gtri (greater-than register/immediate) sets register C to 1 if register A is greater than value B. Otherwise, register C is set to 0.
def gtri(self, a, b, c):
if self.any_invalid_registers((c, a)):
return False
self.register[c] = int(self.register[a] > b)
return True
# gtrr (greater-than register/register) sets register C to 1 if register A is greater than register B. Otherwise, register C is set to 0.
def gtrr(self, a, b, c):
if self.any_invalid_registers((a, b)):
return False
self.register[c] = int(self.register[a] > self.register[b])
return True
# eqir (equal immediate/register) sets register C to 1 if value A is equal to register B. Otherwise, register C is set to 0.
def eqir(self, a, b, c):
if self.any_invalid_registers((c, b)):
return False
self.register[c] = int(a == self.register[b])
return True
# eqri (equal register/immediate) sets register C to 1 if register A is equal to value B. Otherwise, register C is set to 0.
def eqri(self, a, b, c):
if self.any_invalid_registers((c, a)):
return False
self.register[c] = int(self.register[a] == b)
return True
# eqrr (equal register/register) sets register C to 1 if register A is equal to register B. Otherwise, register C is set to 0.
def eqrr(self, a, b, c):
if self.any_invalid_registers((a,b,c)):
return False
self.register[c] = int(self.register[a] == self.register[b])
return True
def disassemble(self):
return "\n".join(
f"{i:02}: " + self.disassemble_instr(instr)
for i, instr in enumerate(self.instructions)
)
def disassemble_instr(self, instr):
op, a_, b_, c = instr
a = self.disassemble_reg(a_, True)
ra = self.disassemble_reg(a_, False)
b = self.disassemble_reg(b_, True)
rb = self.disassemble_reg(b_, False)
rc = self.disassemble_reg(c, False)
diss_instr = {
"addr": "{ra} + {rb}",
"addi": "{ra} + {b}",
"mulr": "{ra} * {rb}",
"muli": "{ra} * {b}",
"banr": "{ra} & {rb}",
"bani": "{ra} & {b}",
"borr": "{ra} | {rb}",
"bori": "{ra} | {b}",
"setr": "{ra}",
"seti": "{a}",
"gtrr": "{ra} > {rb} ? 1 : 0",
"gtri": "{ra} > {b} ? 1 : 0",
"eqir": "{a} == {rb} ? 1 : 0",
"eqri": "{ra} == {b} ? 1 : 0",
"eqrr": "{ra} == {rb} ? 1 : 0",
}
return f"{rc} = " + diss_instr[op].format(a=a, ra=ra, b=b, rb=rb)
def disassemble_reg(self, reg, immediate):
if self.ip_binding != None and reg == self.ip_binding:
return "IP"
elif immediate:
return str(reg)
return f"R{reg}"
puzzle_input_str = open("puzzle_input/day19.txt").read()
test_input_str = """#ip 0
seti 5 0 1
seti 6 0 2
addi 0 1 0
addr 1 2 3
setr 1 0 0
seti 8 0 4
seti 9 0 5"""
def part_one(raw_instructions, registers, debug=False):
instructions = raw_instructions.split("\n")
vm = VM(registers)
vm.load(instructions)
return vm.run(debug)[0]
assert 6 == part_one(test_input_str, 6 * [0])
# part 1
print(part_one(puzzle_input_str, [0] * 6))
1806
# part 2
# print(run_program(problem_input_str, [1] + 5 * [0], False))
# FFS ok so this is basically a super-quadratic program that actually requires you to
# disassemble your code, identify what the program is _trying_ to do and find a better
# approach. That's frustrating.
def disassemble_program(raw_instructions, registers, debug=False):
instructions = raw_instructions.split("\n")
vm = VM(registers)
vm.load(instructions)
print(vm.disassemble())
disassemble_program(puzzle_input_str, [0] * 6)
00: IP = IP + 16
01: R1 = 1
02: R4 = 1
03: R3 = R1 * R4
04: R3 = R3 == R2 ? 1 : 0
05: IP = R3 + IP
06: IP = IP + 1
07: R0 = R1 + R0
08: R4 = R4 + 1
09: R3 = R4 > R2 ? 1 : 0
10: IP = IP + R3
11: IP = 2
12: R1 = R1 + 1
13: R3 = R1 > R2 ? 1 : 0
14: IP = R3 + IP
15: IP = 1
16: IP = IP * IP
17: R2 = R2 + 2
18: R2 = R2 * R2
19: R2 = IP * R2
20: R2 = R2 * 11
21: R3 = R3 + 8
22: R3 = R3 * IP
23: R3 = R3 + 16
24: R2 = R2 + R3
25: IP = IP + R0
26: IP = 0
27: R3 = IP
28: R3 = R3 * IP
29: R3 = IP + R3
30: R3 = IP * R3
31: R3 = R3 * 14
32: R3 = R3 * IP
33: R2 = R2 + R3
34: R0 = 0
35: IP = 0
# reassembled into python this looks like the below
def naive_reassembly():
r0, r1, r2, r3, r4, r5 = [1, 0, 0, 0, 0, 0]
# initialise r2 to 10551428 very inefficiently
r2 = r2 + 2
r2 = r2 * r2
r2 = 19 * r2
r2 = r2 * 11
r3 = r3 + 8
r3 = r3 * 22
r3 = r3 + 16
r2 = r2 + r3
r3 = 27
r3 = r3 * 28
r3 = 29 + r3
r3 = 30 * r3
r3 = r3 * 14
r3 = r3 * 32
r2 = r2 + r3
r1 = 1
while r1 <= r2:
r4 = 1
while r4 <= r2:
if r1 * r4 == r2:
r0 += r1
r4 += 1
r1 += 1
return r0
# ... but this is still slow as hell. after a bit of fiddling around it became
# apparent we're basically just summing up all the integers which are factors
# of 10551428. this is a very low
def part_two():
total = 0
n = 10551428
while n > 0:
if 10551428 % n == 0:
total += n
n -= 1
return total
part_two()
18741072