In Day 8, we receive a set of custom instructions that uses some specific vocabulary:
acc nmodifies the value of an accumulator by
n. After an
accinstruction, the instruction immediately below it is executed next.
jmp njumps to the instruction that is
nlines before of above the current one.
nopmeans 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(" ") sign = instruction.split(" ") value = int(instruction.split(" ")[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
- sign, followed by an integer value.
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
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
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
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(" ") sign = instruction.split(" ") value = int(instruction.split(" ")[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 = "Bonjour" # a <- ["Bonjour", "world"]; b <- ["Bonjour", "world"]
We can see that, when working with primitive types, modifying
b has no impact
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
b an element that belongs to the original list
a. Because we created a
shallow copy, this change is repercuted on
a = [[1, 2], [3, 4]] b = a.copy() b.append([5, 6]) # a is unchanged, b <- [[1, 2], [3, 4], [5,6]] b.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.