For Day 8, the puzzle involves simulating a machine running a limited Assembly-like language. The language has three instructions:

  • nop <x>, ignored as a no-op instruction
  • acc <x>, add <x> to the single acc register
  • jmp <x>, add <x> to the instruction pointer

Small introduction to low-level computer terminology:

Assembly consists of machine code instructions, which are fed to the CPU and executed. Conceptually, assembly programs are lists of instructions, somewhat like this:

inst1
inst3 operand operand
inst2 operand

And so on. When values are tracked, a register is used to track the value (in this toy problem, acc is a register). An instruction pointer is a special register that is used to track where the execution is, “pointing” (hence the name) to the next instruction to be executed.

Given a program prog, an instruction pointer ip, and an accumulator acc, a step evaluation in a program run looks like this:

def step(ip, acc):
    inst = prog[ip].split(" ")
    if inst[0] == "nop":
        ip += 1
    elif inst[0] == "acc":
        acc += int(inst[1])
        ip += 1
    elif inst[0] == "jmp":
        ip += int(inst[1])

    return ip, acc

Part 1 requires running a program with an infinite loop, and halting the program when an instruction is about to be executed for the second time. This requires keeping track of the number of executions for each step in the program. My implementation looks like this:

def run_prog(prog, visualize=False):
    eval_counts = [0 for _ in prog]

    states = deque()

    ptr = 0
    acc = 0
    while eval_counts[ptr] < 1 and ptr < len(prog) - 1:
        if visualize:
            states.append(MachineState(acc, ptr, deepcopy(prog), deepcopy(eval_counts)))
        eval_counts[ptr] += 1
        ptr, acc = step(prog, ptr, acc)

    if visualize:
        states.append(MachineState(acc, ptr, deepcopy(prog), deepcopy(eval_counts)))
    terminated = False

    if ptr == len(prog) - 1:
        terminated = True
        ptr, acc = step(prog, ptr, acc)
        if visualize:
            states.append(MachineState(acc, ptr, deepcopy(prog), deepcopy(eval_counts)))

    return acc, terminated, states

Below is a visualization of the machine simulation, when executing a looping program:

Part 2 involved modifying exactly one nop instruction with a jmp, or vice versa, to produce a terminating program (e.g. one that does not have an infinite loop). This can be done with a program mutator:

def swap_inst(prog, x):
    new_prog = []
    for i, inst in enumerate(prog):
        if i != x:
            new_prog.append(inst)
        else:
            if inst.startswith("nop"):
                new_prog.append(inst.replace("nop", "jmp"))
            elif inst.startswith("jmp"):
                new_prog.append(inst.replace("jmp", "nop"))
    return new_prog

And a generator to produce the modified programs:

def iter_swaps(prog):
    for idx, inst in enumerate(prog):
        if inst.startswith("nop") or inst.startswith("jmp"):
            yield idx

p2 = None
for idx in iter_swaps(prog):
    new_prog = swap_inst(prog, idx)
    p2, terminated, _ = run_prog(new_prog)
    if terminated:
        break

Below is a screen cast showing a machine simulation with a correctly modified program: