Advent of Code 2020, Day 8 -- Handheld Halting

Dec 8th, 2020

3 min read

Advent Of Code

Python solutions to Advent of Code 2020, day 8.

My Advent of Code solutions, done in Python. Refactors and solutions in other languages will be added if/when they're done.

Full code for Day 8 can be found on Github.

You can participate in Advent of Code at adventofcode.com/2020

The Day 8 problem can be found at adventofcode.com/2020/day/8

Solution, part 1

Oh no, this got very difficult. 😄

The first part was honestly not too bad. My solution is to visit and execute each instruction while keeping a list of indices that were previously visited. If index already appears in the indices list, it means we're in a loop, and it returns the accumulated value.

Note that the calculated index from either the "jmp" instruction or incrementing by 1 is added to the list at the end of the loop, so we get the current index by getting the -1 slice of indices.

I added a bunch of comments into my code this time because I has having a hard time keeping track of what was going on in the loop.

puzzle_input = open("input.txt", "r")
lines = puzzle_input.read().strip().split("\n")


def find_loop_value(lines):
    instructions = [tuple(x.split(" ")) for x in lines]
    acc = 0  # Accumulator
    indices = [0]  # List of visited indices.
    while True:
        idx = indices[-1]
        inst = instructions[idx]
        # Add current idx + instruction number
        if inst[0] == 'jmp':
            idx = idx + int(inst[1])
        # Add to the accumulator and increment idx by 1
        if inst[0] == 'acc':
            acc += int(inst[1])
            idx += 1
        # Increment idx by 1
        if inst[0] == 'nop':
            idx += 1
        # If the new idx is in the indices list,
        # that means we have a loop, so break
        # and return the acc.
        if idx in indices:
            return acc
        # If not broken, append to indices list.
        indices.append(idx)


print(find_loop_value(lines))

Solution, part 2

I'm going to brute-force part 2 by creating a function that will make a copy of the instructions and change one of the "jmp" instructions to "nop" or "nop" to "jmp". To do this, I'm iterating over the range of the length of the instructions, changing one at a time, then running it through a modified find_loop_value function.

I tried to just change the first part of the instruction tuple, but learned that tuples are immutable, so I'm changing the entire instruction tuple at that index instead. I could avoid that by using a list instead of a tuple for the instructions, but personal preference is to use a tuple.

You'll see that finished_program calls a modified copy of find_loop_value called find_correct_loop. This function either returns None if the program hits a loop, or the accumulator value if the next index is greater than or equal to the length of the instructions.

I think this could be sped up a bit by adding an extra if statement into fix_infinite_loop that skips running find_correct_loop if the instruction is "acc". Since that instruction never changes, it doesn't make sense to run the find script for that instance. However, at the time, I was just happy that it gave me the correct answer.

import copy

# Brute force solution.
def fix_infinite_loop(lines):
    # Creating a list of instructions.
    instructions = [tuple(x.split(" ")) for x in lines]

    # Iterate over the length of the instruction list.
    # x will be the index of the instruction to change.
    for x in range(0, len(lines)):
        # Making a shallow copy of the instructions.
        inst_copy = copy.copy(instructions)
        val = inst_copy[x][1]  # Value of the instruction.
        # If the instruction at the index is 'jmp',
        # replace that instruction with 'nop' and the value.
        if inst_copy[x][0] == 'jmp':
            inst_copy[x] = ('nop', val)
        # If the instruction at the index is 'nop',
        # replace that instruction with 'jmp' and the value.
        elif inst_copy[x][0] == 'nop':
            inst_copy[x] = ('jmp', val)

        finished_program = find_correct_loop(inst_copy)
        if finished_program:
            # print(inst_copy[x])  # Check out the changed instruction.
            return finished_program
            

# Basically the same function as find_loop_value.
# Checks the index of the instruction to the length
# of the entire instruction list.
# If the index is >= that length, we're at the end.
def find_correct_loop(instructions):
    ins_length = len(instructions)
    acc = 0  # Accumulator
    indices = [0]  # List of visited indices.
    while True:
        idx = indices[-1]
        inst = instructions[idx]
        # Add current idx + instruction number
        if inst[0] == 'jmp':
            idx = idx + int(inst[1])
        # Add to the accumulator and increment idx by 1
        if inst[0] == 'acc':
            acc += int(inst[1])
            idx += 1
        # Increment idx by 1
        if inst[0] == 'nop':
            idx += 1
        # If the new idx is in the indices list,
        # that means we have a loop, so break
        # and return nothing.
        if idx in indices:
            return
        # This is where we break if the idx >=
        # the total length of the instruction list
        # and return the accumulated value.
        if idx >= ins_length:
            return acc
        # If not broken, append to indices list.
        indices.append(idx)


print(fix_infinite_loop(lines))

mary.codes