Part 1

In Day 8, we receive a set of custom instructions that uses some specific vocabulary:

• acc n modifies the value of an accumulator by n. After an acc instruction, the instruction immediately below it is executed next.
• jmp n jumps to the instruction that is n lines before of above the current one.
• nop means no operation. Nothing is done and the next instruction to be executed is the one immediately below.

We are told that the program we are looking is looping forever. This happens because, at one point, an instruction is executed a second time thus starting the infinite loop. The goal of Part 1 is to determine the value contained in the accumulator before starting the infinite loop.

Let’s have a look at the input data we are given as example. I have modified it a little bit to add two columns: one for the line number and another one for the step number in the program and the corresponding accumulator value.

| Line | Instruction | Step and accumulator |
|++++++|+++++++++++++|++++++++++++++++++++++|
|    0 |      nop +0 |                 1, 0 |
|    1 |      acc +1 |                 2, 1 | <-- Should also be step 8
|    2 |      jmp +4 |                 3, 1 |
|    3 |      acc +3 |                 6, 5 |
|    4 |      jmp -3 |                 7, 5 |
|    5 |     acc -99 |                      |
|    6 |      acc +1 |                 4, 2 |
|    7 |      jmp -4 |                 5, 2 |
|    8 |      acc +6 |                      |

We can see that, once the program reaches line 4 in step 7, the instruction makes us go back to line 1 that was already executed as the second instruction of the program. We are thus reaching the beginning of the infinite loop, and the final accumulator value is 5.

To solve this problem, we need to identify the important information that will help us find the beginning of the infinite loop. One way to do this would be to create a list of instructions that were executed by the program. But we need to be careful about that, because we don’t know whether the same instruction can appear at different places in our program or not. And so, we should memorise line numbers instead of actual instructions.

This is an example of what can be done to solve this problem:

line_number = 0
visited_lines = []
accumulator = 0
# lines is already a list of instructions
while line_number not in visited_lines:
    # We add the line number to the list of visited_lines
    visited_lines.append(line_number)
    instruction = lines[line_number]
    # We parse the information for an instruction
    operation = instruction.split(" ")[0]
    sign = instruction.split(" ")[1][0]
    value = int(instruction.split(" ")[1][1:])
    if operation == "nop":
        line_number += 1
    elif operation == "acc":
        accumulator = accumulator + value if sign == "+" else accumulator - value
        line_number += 1
    elif operation == "jmp":
        line_number = line_number + value if sign == "+" else line_number - value
print(accumulator)

I think the code is self explanatory. A possible issue would be to not realise that each instruction has the same structure: an operation, followed by a white space, followed by a + or - sign, followed by an integer value.

Part 2

In Part 2, we are told that there is exactly one instruction that leads to the infinite loop. More precisely, a jmp instruction should be a nop instruction or the other way around. By changing the appropriate instruction, the program should end by reaching its last instruction.

Our task here is to find out which instruction needs to be swapped and calculate the value of the accumulator after the program terminates. The algorithm itself is not so different from what we have proposed for Part 1, we simply need to break the while loop if we have reached the last line of the program, i.e., if line_number == len(lines).

Now, we need to figure out which instruction needs to be changed. Instead of trying to brute force it, we can first look for all the jmp and nop instructions and save their indices. This would help us remember which instruction needs to be swapped next.

Finally, we also need to be careful to create copies of the initial program before modifying the instruction. This is to make sure that we always start from the initial program.

Here’s the full program that solves Part 2:

# Function that does almost the same thing as in Part 1
# The only differences are:
#   - In the return value to stop the loop used to swap instructions
#   - The test line_number == len(instructions)
def execute_program(instructions):
    line_number = 0
    visited_lines = []
    accumulator = 0
    while line_number not in visited_lines:
        visited_lines.append(line_number)
        instruction = instructions[line_number]
        operation = instruction.split(" ")[0]
        sign = instruction.split(" ")[1][0]
        value = int(instruction.split(" ")[1][1:])
        if operation == "nop":
            line_number += 1
        elif operation == "acc":
            accumulator = accumulator + value if sign == "+" else accumulator - value
            line_number += 1
        elif operation == "jmp":
            line_number = line_number + value if sign == "+" else line_number - value
        if line_number == len(instructions):
            print(accumulator)
            return True
    return False

swap_indices = []
for i, line in enumerate(lines):
    if "nop" in line or "jmp" in line:
        swap_indices.append(i)

for swap_index in swap_indices:
    # That is the most important part: we create a copy of the list
    # Like that, we are sure that we are starting always from the initial list
    lines_copy = lines.copy()
    instruction = lines_copy[swap_index]
    if "nop" in instruction:
        lines_copy[swap_index] = instruction.replace("nop", "jmp")
    elif "jmp" in instruction:
        lines_copy[swap_index] = instruction.replace("jmp", "nop")
    if execute_program(lines_copy):
        break

Concepts and difficulties

From my point of view, Day 8 is easier than Day 7. In Day 8, we are using data structures that we are used to manipulate (in this case, lists). But once again, the most important step to solve these problems is to think beforehand of the information that we need in order to write simple solutions. Here, one of the most important variable is the line_number because it is used to both fetch an instruction and check if the instruction was executed before. Once we have seen that, the problems get easier.

Another concept that we have not encountered yet in our resolutions is the one of copy. Because we are creating different “versions” of the program all based on the initial one given as input data, we have to create copies so that the initial program does not get modified. In programming, copies are something very specific and is a little bit more complex than what they may look like. Let’s look at the following examples:

a = 1
b = a
b += 1      # a <- 1; b <- 2

a = "Hello"
b = a
b += ", world!"     # a <- "Hello"; b <- "Hello, world!"

a = [1, 2, 3]
b = a
b.append(4)         # a <- [1, 2, 3, 4]; b <- [1, 2, 3, 4]

a = ["Hello", "world"]
b = a
b[0] = "Bonjour"    # a <- ["Bonjour", "world"]; b <- ["Bonjour", "world"]

We can see that, when working with primitive types, modifying b has no impact on a. But when working with lists or any data structure, a modification in a variable is repercuted on the other variable. This is because the two variables actually point towards the same memory.

With the instruction my_list.copy(), we are actually creating what is called a shallow copy (in opposition to deep copy). In a shallow copy, we are creating a new object and then inserts references of the original elements. That means that it is possible to actually modify the original list when modifying a shallow copy (see example below). In line 3, we are adding an element to the new list but because b is now a new object (with a different memory address from a), the change is not repercuted on a. Then, on line 4, we are now modifying on b an element that belongs to the original list a. Because we created a shallow copy, this change is repercuted on a.

a = [[1, 2], [3, 4]]
b = a.copy()
b.append([5, 6])    # a is unchanged, b <- [[1, 2], [3, 4], [5,6]]
b[0].insert(0, 0)   # a <- [[0, 1, 2], [3, 4]], b <- [[0, 1, 2], [3, 4], [5, 6]]

In Day 8’s, we are manipulating lists of strings or integers. Because these are primitive types, we can work with shallow copies without worrying about modifying the initial list. Otherwise, we would have had to use deep copies. If the notion of copies is still unclear, I suggest that you read a little bit on how variables are stored in memory to get a better understanding of why we have shallow and deep copies.