« Advent of Code 2020 - Day 7
Capture-the-Flag: Rear Hatch »

Advent of Code 2020 - Day 8

in   code   ,

Day 8 of AoC 2020 (Handheld Halting) is a nice instruction simulation problem, and fairly easy to boot. Spoilers ahead.

The input consists of a series of instructions, one instruction per line. There are only 3 instructions - acc, jmp and nop. All instructions are followed by a number; acc updates the internal accumulator by that number, jmp updates the program counter by that number, while nop does nothing. The program counter is incremented after acc and nop instructions.

One observation we can make is that a program with no corruption will have no loops. This is because there are no conditional instructions, which is a prerequisite for creating loops with an exit condition. A correct program will always terminate, because all jmp instructions will jump to an instruction that has not been executed before.

Let’s first tackle parsing the input. We can handle this by just splitting each line at whitespace, and converting the second field into an integer.

def load_data(datafile):
    data = []
    with open(datafile) as df:
        for line in df:
            instruction, value = line.strip().split()
            value = int(value)

            data.append([instruction, value])

    return data

For part 1, we need to simulate the instructions, until we find an instruction that has already been executed. We can keep track of this by creating a list that maps the program counter to a boolean value that indicates whether this PC has been visited yet, and updating it on execution.

def simulate(program):
    pc = 0
    acc = 0
    visited = [False] * len(program)
    while 0 <= pc < len(program) and not visited[pc]:
        inst = program[pc]
        visited[pc] = True
        if inst[0] == 'acc':
            acc += inst[1]
        elif inst[0] == 'jmp':
            pc += inst[1]
            continue # So we don't increment the PC a second time.
        elif inst[0] == 'nop':
            # nop
            pass
        else:
            print('Unknown instruction {} at {}'.format(inst, pc))

        pc += 1

    # If the program has terminated normally, pc should be outside the
    # range of the input program. If it is within the program, then the
    # simulator has encountered a loop.
    return not 0 <= pc < len(program), acc

The above code snippet is sufficient to get the result of the program right before we hit the infinite loop.

Part 2 asks us to find the one instruction that has been corrupted, i.e., find either the nop that should have been a jmp, or the jmp that should have been a nop. One way we can do this is to create a copy of the program, swap the instruction (if it is not acc), and simulate the new program using our simulate function in the above snippet.

This is essentially a brute force approach, but it is sufficient for our needs, as the input is fairly small at under 700 instructions, and acc instructions account for about half of that. Therefore, even a brute force solution would be fairly quick.

swap = {'nop': 'jmp', 'jmp': 'nop'}
for pc, inst in enumerate(orig_program):
    if inst[0] in swap:
        new_program = copy.deepcopy(orig_program)
        new_program[pc][0] = swap[inst[0]]
        result, acc = simulate(new_program)

        if result:
            print('Part 2:', acc)
            break

 

 Recent Posts

 Tags

 Categories