import operator
from dataclasses import dataclass
from functools import partial
from typing import Callable, Iterable, List, Mapping, Sequence, Tuple, Type, Union
Instruction = Tuple[str, int, int, int]
OpcodeFunction = Union[Callable[[int, int], int], Callable[[int], int]]
@dataclass
class Opcode:
# An opcode function takes one or two integers as input
f: OpcodeFunction
operands: str # 1 or 2 characters, i and r
opcode: str = ""
def __set_name__(self, owner: Type["CPU"], name: str) -> None:
self.opcode = name[3:]
owner.opcodes[self.opcode] = self
def __repr__(self) -> str:
return f"<opcode {self.opcode} {self.operands!r}>"
def __get__(
self, instance: "CPU", owner: Type["CPU"]
) -> Callable[[int, int, int], None]:
return partial(self.__call__, instance)
def __call__(self, cpu: "CPU", *ops: int) -> None:
# operand C receives the output
*ops, op_c = ops
# map the oter operands to values
value = {"r": cpu.registers.__getitem__, "i": operator.pos}
ops = (value[t](op) for t, op in zip(self.operands, ops))
# execute the operand, store the integer result in the register
# designated by C. Int is used to convert bool results to 0 or 1
cpu.registers[op_c] = int(self.f(*ops))
def opcode(operands: str) -> Callable[[OpcodeFunction], Opcode]:
"""Operator operates on 1 or 2 operands
Specify the operands as 'r' or 'i' for registers and immediate values.
"""
def decorator(f: OpcodeFunction) -> Opcode:
return Opcode(f, operands)
return decorator
class CPU:
registers: List[int] # limited to 6
opcodes: Mapping[str, Opcode] = {}
def __init__(self) -> None:
self.registers = [0, 0, 0, 0, 0, 0]
self.bound: Mapping[str, Callable[[int, int, int], None]] = {
name: opcode.__get__(self, None) for name, opcode in CPU.opcodes.items()
}
# Addition
# addr (add register) stores into register C the result of adding register
# A and register B.
op_addr = opcode("rr")(operator.add)
# addi (add immediate) stores into register C the result of adding
# register A and value B.
op_addi = opcode("ri")(operator.add)
# Multiplication:
# mulr (multiply register) stores into register C the result of
# multiplying register A and register B.
op_mulr = opcode("rr")(operator.mul)
# muli (multiply immediate) stores into register C the result of
# multiplying register A and value B.
op_muli = opcode("ri")(operator.mul)
# Bitwise AND:
# banr (bitwise AND register) stores into register C the result of the
# bitwise AND of register A and register B.
op_banr = opcode("rr")(operator.and_)
# bani (bitwise AND immediate) stores into register C the result of the
# bitwise AND of register A and value B.
op_bani = opcode("ri")(operator.and_)
# Bitwise OR:
# borr (bitwise OR register) stores into register C the result of the
# bitwise OR of register A and register B.
op_borr = opcode("rr")(operator.or_)
# bori (bitwise OR immediate) stores into register C the result of the
# bitwise OR of register A and value B.
op_bori = opcode("ri")(operator.or_)
# Assignment:
# setr (set register) copies the contents of register A into register C.
# (Input B is ignored.)
op_setr = opcode("r")(operator.pos) # pos is the identity function for int
# seti (set immediate) stores value A into register C. (Input B is
# ignored.)
op_seti = opcode("i")(operator.pos) # pos is the identity function for int
# Greater-than testing:
# 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.
op_gtir = opcode("ir")(operator.gt)
# 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.
op_gtri = opcode("ri")(operator.gt)
# 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.
op_gtrr = opcode("rr")(operator.gt)
# Equality testing:
# eqir (equal immediate/register) sets register C to 1 if value A is equal
# to register B. Otherwise, register C is set to 0.
op_eqir = opcode("ir")(operator.eq)
# eqri (equal register/immediate) sets register C to 1 if register A is
# equal to value B. Otherwise, register C is set to 0.
op_eqri = opcode("ri")(operator.eq)
# eqrr (equal register/register) sets register C to 1 if register A is
# equal to register B. Otherwise, register C is set to 0.
op_eqrr = opcode("rr")(operator.eq)
def execute(self, ipregister: int, instructions: Sequence[Instruction]) -> int:
opcodes = self.bound
r = self.registers
while 0 <= r[ipregister] < len(instructions):
op, *operands = instructions[r[ipregister]]
opcodes[op](*operands)
r[ipregister] += 1
return self.registers[0]
def parse_instructions(lines: Iterable[str]) -> Tuple[int, Sequence[Instruction]]:
it = iter(lines)
ipregister = int(next(it).rpartition(" ")[-1])
instructions = []
for line in it:
opcode, *operands = line.split()
instructions.append((opcode, *map(int, operands)))
return ipregister, instructions
testprogram = parse_instructions(
"""\
#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""".splitlines()
)
assert CPU().execute(*testprogram) == 7
import aocd
data = aocd.get_data(day=19, year=2018)
ipregister, instructions = parse_instructions(data.splitlines())
print("Part 1:", CPU().execute(ipregister, instructions))
Part 1: 912
The puzzle is specifically crafted to take a very, very long time once you set register 0 to 1. We need to find a shortcut. The machine code given isn't very long, we need to analyse it a little to see what it does and were we can cut a corner.
Looking over my puzzle input, I annotated the instructions with my interpretation; my IP is register #4. If you are looking at this notebook on Github, you may want to switch to the Jupyter notebook viewer instead to see my colour annotations and have label links work:
label | i | opcode | op1 | op2 | reg | interpretation |
---|---|---|---|---|---|---|
0 | addi | 4 | 16 | 4 | jmp 17 (SETUP) |
|
MAIN | 1 | seti | 1 | 2 | r2 = 1 |
|
LOOP1 | 2 | seti | 1 | 5 | r5 = 1 |
|
LOOP2 | 3 | mulr | 2 | 5 | 3 |
|
4 | eqrr | 3 | 1 | 3 | ||
5 | addr | 3 | 4 | 4 | ||
6 | addi | 4 | 1 | 4 | ||
7 | addr | 2 | 0 | 0 | ||
8 | addi | 5 | 1 | 5 | r5 += 1 |
|
9 | gtrr | 5 | 1 | 3 |
|
|
10 | addr | 4 | 3 | 4 | ||
11 | seti | 2 | 4 | |||
12 | addi | 2 | 1 | 2 | r2 += 1 |
|
13 | gtrr | 2 | 1 | 3 |
|
|
14 | addr | 3 | 4 | 4 | ||
15 | seti | 1 | 4 | |||
16 | mulr | 4 | 4 | 4 | HALT | |
SETUP | 17 | addi | 1 | 2 | 1 |
r1 = 911
simplified from |
18 | mulr | 1 | 1 | 1 | ||
19 | mulr | 4 | 1 | 1 | ||
20 | muli | 1 | 11 | 1 | ||
21 | addi | 3 | 3 | 3 | ||
22 | mulr | 3 | 4 | 3 | ||
23 | addi | 3 | 9 | 3 | ||
24 | addr | 1 | 3 | 1 | ||
25 | addr | 4 | 0 | 4 |
|
|
26 | seti | 0 | 4 | |||
PART2 | 27 | setr | 4 | 3 |
r1 = 10551311
simplified from
|
|
28 | mulr | 3 | 4 | 3 | ||
29 | addr | 4 | 3 | 3 | ||
30 | mulr | 4 | 3 | 3 | ||
31 | muli | 3 | 14 | 3 | ||
32 | mulr | 3 | 4 | 3 | ||
33 | addr | 1 | 3 | 1 | ||
34 | seti | 0 | 0 | r0 = 0 |
||
35 | seti | 0 | 4 | jmp 36 (MAIN) |
The above can be condensed into the following Python code:
v = 911 if part1 else 10551311
result = 0
for i in range(1, v + 1):
for j in range(1, v + 1):
if i * j == v:
result += i
So we are basically finding the sum of the divisors of the given number. For 911, a prime number, that's just 911 itself and 1, and so the answer is 912.
For part 2 the number becomes a lot, lot larger, so lets not bother with our CPU at all and just calculate the number using Python. Not with the above code, of course; we don't need a double loop here!
from itertools import chain
def sum_factors(n):
return sum(
set(
chain.from_iterable(
(i, n // i) for i in range(1, int(n**0.5) + 1) if not n % i
)
)
)
assert sum_factors(911) == 912
print("Part 2:", sum_factors(10551311))
Part 2: 10576224