Advent of Code 2020 - day 8

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

This puzzle's core consists of emulating a (very simple) computer. I may have been a little overzealous to create the Computer class, possibly influenced by the repeated appearances of the intcode computer last year, but fortunately I didn't go overboard with it.

Part 1

We have a basic computer with a memory storing the program, the instruction pointer (ip) with the memory address of the next instruction to execute, a register called accumulator, and an obviously RISC instruction set: acc increments the accumulator by its argument, jmp provokes a jump in memory with an offset corresponding to its argument (i.e. it increments the instruction pointer by its argument), and nop which does nothing. Each instruction consists of the opcode and an integer value as argument, although the argument is ignored in the case of nop.

The operation is simple: on boot-up both the accumulator and the instruction pointer hold the value 0. The program is loaded in memory, and we represent it as a list (where the index corresponds to the address) of opcode, argument tuples. The parsing in this case is straightforward.

The only generalization design decision is to use the opcodes directly with the getattr method, so that we can add new behaviour by just adding new Computer methods named after the corresponding opcode. If multiple arguments are needed, we can define each method with its proper arity and change the call to getattr(self, cmd)(*args), using the star notation to unpack the arguments.

Executing an instruction takes it from memory using the index in the instruction pointer, applies the opcode and argument, and increments the ip by one to move to the next instruction. Because of this, the jmp instruction needs to insert a correction after applying the offset, but otherwise every non-jmp opcode would need to increment the ip by itself, which is easier to forget. The implementation of the opcodes is trivial.

The question in this part is to find a loop in the program. Given that there is no branching, that means an infinite loop. We do this in the find_loop method, by keeping track of the addresses of executed instructions. As usual, we keep a set for the quick membership lookups. As soon as we are about to execute an instruction that we have already gone through, that's our loop, so we stop.

Part 2

In the second part we are asked to fix the program to avoid the loop by changing exactly one instruction either from nop to jmp or from jmp to nop. Undoubtedly trying out every possibility is not an option, so we need to think of a smarter scheme. It's time to go back to graphs.

We can represent the execution path as a graph, wehere each instruction is a node, and edges represent transition from one instruction to the next, usually moving up one address, except for jmp instructions. The first for loop in find_valid_addresses builds this graph as a dictionary with a destination as value for each address as key. This works because there is no potential branching, so the destination is always fixed, independently of the state of the machine.

But what we actually need is the opposite, we need to know from which addresses we can reach a given address. In other words, we need to invert the dictionary, but carefully: while each origin has a unique destination, each destination may be reached from multiple origins or from non at all. A defaultdict of sets makes this terse without impairing readability.

Now we are ready to determine which addresses can reach the end of the program. We take the last instruction to begin with, then we add all addresses from which that one can be reached, then the addresses from which those ones can be reached, an so on recursively. The actual implementation in find_valid_addresses follows the same concept that we applied before in day 7 to find out which suitcases could contain ours.

Now that we know which addresses eventually lead to the termination of the program, we can go about fixing the infinite loop. We just need to check for each nop and jmp instruction, as they happen in the program execution, whether switching it would lead to one of those addresses; if so, we do the switch, and return. We need to do a dirty emulation of the computer to follow the flow of the program (but without regard for the accumulator), or we might end up changing an opcode that is not actually reached, which would be useless.

We can now run the fixed program to get the answer to the exercise.