Hello! We are on Day 08 of our Advent of Code journey. Today’s puzzle involves a lot of jumping, let’s see if we can hop around and solve it 😀.
Spoilers Ahead! The full solution to the problem below is available here.
Problem - Part 01
The input is a sequence of bootcode instructions, wherein each instruction consists of an operation (acc, jmp, or nop) and an argument (a signed number like +4 or -20).
acc
increases or decreases a single global value called the accumulator by the value given in the argument. For example, acc +7 would increase the accumulator by 7. The accumulator starts at 0. After an acc instruction, the instruction immediately below it is executed next.jmp
jumps to a new instruction relative to itself. The next instruction to execute is found using the argument as an offset from the jmp instruction; for example, jmp +2 would skip the next instruction and jmp -20 would cause the instruction 20 lines above to be executed next.nop
stands for No Operation - it does nothing. The instruction immediately below it is executed next.
Given the above input, for Part 01 we have an instruction that causes an infinite loop, and doesn’t allow the program to terminate. The solution for Part 01, is to return the value of the global accumulator
right before going into an infinite loop.
Let’s see how we can solve this. The algorithm would look something like:
-
Parse the input text file into a sequence of instructions ie an array / vector of (operation, argument).
-
Then we can write a function that processes these instructions. Initialize an accumulator varible to 0. Initialize a
curr
index, and use that inside a loop to iterate through every (operation, argument) pair in instructions. -
In order to keep track of instructions that we have been already processed, we have a HashSet that stores the index.
-
If the operation is
acc
we add the argument to it, and also increment the current index. -
If the operation is
jmp
we move curr index to curr_index + argument. This moves the current instruction to execute above or below the current line of execution. -
If the operation is
nop
we don’t do anything. We have to increment the current index however, as this is a valid instruction. -
While iterating through all the instructions, and performing the operations mentioned above, we also check if the HashSet has the current index. If so, that means we are going to go into an infinite loop, as we are starting to process an instruction that’s already been processed. So we break and return the global
accumulator
value.
The following snippet shows how we can parse the input into an array of instructions.
The parse
function trims the input lines, and then calls the parse_instruction
function which returns a tuple of (operation, argument). For example this would look like ("acc", 9)
.
Let’s write function that actually processes these instructions.
Alright! Once we call this function with the instructions, we would break right before the infinite loop, and return the acc value.
The line if curr == instructions.len() as isize { break Ok(accumulator); }
is not useful for Part 01, but will be for Part 02.
Problem - Part 02
Part 02 is an extension to Part 01, wherein we need to check if we can avoid the infinite loop, by changing either a nop instruction -> jmp or vice versa and are able to get the program to terminate.
We write a function that fixes the bootcode by iterating through our instructions and swapping jmp and nop with each other in a new copy of our instruction set, processing these new instructions again and checking if that swap resulted in a successful program termination.
The result of this function returns the answer to Part 02. That’s all for today. Ciao 👋