Advent of Code 2020: Day 8

, 11 min read
advent of code 2020

Part 1

Your flight to the major airline hub reaches cruising altitude without incident. While you consider checking the in-flight menu for one of those drinks that come with a little umbrella, you are interrupted by the kid sitting next to you.

Their handheld game console won’t turn on! They ask if you can take a look.

The boot code is represented as a text file with one instruction per line of text. 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, jmp +1 would continue to the instruction immediately below it, 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.

For example, consider the following program:

nop +0 acc +1 jmp +4 acc +3 jmp -3 acc -99 acc +1 jmp -4 acc +6

This is an infinite loop: with this sequence of jumps, the program will run forever. The moment the program tries to run any instruction a second time, you know it will never terminate.

Run your copy of the boot code. Immediately before any instruction is executed a second time, what value is in the accumulator?

You can read the full text here. Yes - emulation is back! For those of you who missed advent of code last year, we had a series of problems which walked us through the process of producing an Intcode interpreter. I really enjoyed this series of puzzles last year, and I hope they are back.

For this problem, we just need to parse the input into our program, and then executing the instructions is quite simple. This input format is not particularly difficult to parse using string manipulation; however, I’m going to use regex anyway. I define my pattern as,

1
std::regex pieces_regex("([a-z]{3}) ([+-]\\d*)");

Where the first match is a three letter word, made of [a-z] characters e.g. “jmp”, “nop”, “acc”. The second is a (multi digit) number prefixed with ether a “+” or “-” character.

With our pattern defined, we can just loop through the input and store the instructions.

1
2
3
4
5
6
7
8
std::vector<std::pair<std::string, int>> instructions;
std::string line;
std::regex pieces_regex("([a-z]{3}) ([+-]\\d*)");
std::smatch pieces_match;
while(std::getline(myfile, line)){
	std::regex_search(line, pieces_match, pieces_regex);
	instructions.push_back({pieces_match[1], std::stoi(pieces_match[2])});
}

The code makes a vector of pairs where each pair stores both a string and an int. We just loop over the lines in the file, apply our pattern matching and store the instructions as we identify them.

Now we are onto the fun part. We have have to implement our own interpreter. This can be done as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int computer1(std::vector<std::pair<std::string, int>> &instructions){
    std::vector<int> visited(instructions.size());
    int acc = 0;
    int i = 0;
    while (true){
		std::string instr = instructions[i].first;
		int offset = instructions[i].second;
        visited[i] += 1;
        if (visited[i] == 2)
            return acc;
        if (instr == "nop"){
            i++;
        }
        else if instr == "acc"){
            acc += offset;
            i++;
        }
        else if (instr == "jmp"){
            i += offset;
        }
    }
    return 0;
}

The above code shows a fairly simple while loop. We use this to loop over every instruction. The noop instruction does nothing, the acc instruction accumulates to a sum and finally jmp changes our instruction pointer.

For this problem I’ve also included a vector of integers, which keeps track of how many times each instruction has been executed. If we attempt to execute an instruction for a second time we must return, to prevent recursion, as stated in the puzzle description.

We can run this code on our input and unlock the first ⭐!

The full code can be found on github

Part 2

After some careful analysis, you believe that exactly one instruction is corrupted.

Somewhere in the program, either a jmp is supposed to be a nop or a nop is supposed to be a jmp. (No acc instructions were harmed in the corruption of this boot code.)

The program is supposed to terminate by attempting to execute an instruction immediately after the last instruction in the file. By changing exactly one jmp or nop, you can repair the boot code and make it terminate correctly.

You can read the full text here.

We now have to modify our code and identify which instruction we need to change to make the program run successfully. First of all, I’m modifying the interpreter code to make it more useful for this part,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
if (i == instructions.size())
	return acc;
// We shouldn't reach here
if (i > instructions.size()){
	return -9999;
}
// We've probably found an inf loop, let's break
visited[i] += 1;
if (visited[i] > 1){
	return -9999;
}

Adding the following code to the loop ensures we return the accumulator when we pass the last instruction. We also make sure the code returns an error value, -9999, when we enter an infinite loop, or if we reach the wrong final value. [Note: it would be very unlucky if my solution happened to be -9999!]

With the changes to our computer in place, we can loop through the puzzle input, changing the instructions and re-running the code,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
std::vector<std::pair<std::string, int>> instructions2;
for(int i=0; i<instructions.size(); i++){
	instructions2 = instructions;
	if (instructions2[i].first == "jmp"){
		instructions2[i].first = "nop";
		ans2 = computer2(instructions2);
	}
	else if (instructions2[i].first == "nop"){
		instructions2[i].first = "jmp";
		ans2 = computer2(instructions2);
	}
	if (ans2 != -9999)
		break;
}

In the code above, I loop through the input and look for “jmp” or “nop” instructions. When we find one of these, we swap it for the other, and then test the new program with our new interpreter. When the code exits successfully, it should return any number which is not -9999, so we break in that case. And that’s it, we are done. Both ⭐⭐!

The full code can be found on github

Reflections

I don’t believe there is a lot that can be optimised today. For part 1 we read every instruction into memory, and then loop through this vector of instructions to run them. Recursion is not allowed, so each instruction is only executed once. Thus, this problem scales as O(N) for both space and time, where N is the number of instructions.

It is possible to process the instructions without reading them all from the file at once. However, given that each instruction can only be executed once, there needs to be some level of book keeping which likely yields O(N)-space complexity, anyway.

For part 2, the input processing and instruction execution are the same. However, we also loop through the initial instructions, modifying them and re-trying them. Thus, for part 2, our time complexity increases to O(N * N)-time, the space complexity remains the same.

I’m not sure if it is possible to reduce the time complexity of part 2 unless it is possible to analyse the input and derive the instruction change required. Initially, I don’t see how this is possible, but I’ll update if that changes.

Anyway, I hope you enjoyed the journey today. Get ready for more puzzles which will expand this interpreter, I’m sure they are coming!

Updates (09/12/20)

After being motivated and pushed by Corentin I went in search of an optimised solution for part 2. There are actually a couple of ways to improve this.

The first method, which I did not come up with, is to start at the desired endpoint and work backwards until you find a path that takes you to the start of the program. This involves first looping through the instructions and generating a graph of nodes which are either “jmp” and “nop” instructions. As each instruction can be reached by many paths, it can be stepped into or jumped into, then finding the way from the endpoint to the origin requires a tree search. This search can be optimised with Dijkstra’s algorithm. You can see Corentin’s python implementation here. The solution is approximately O(N log(N)) where N is the number of instructions.

I think it is possible to solve the second part in O(N)-time and space. For this, I played around on pen and paper. This idea was completely inspired by two suggestions from Corentin on Twitter. The first was about how I could make my brute-force solution slightly more intelligent, and the second was the implementation of a DFS algorithm. I was then able to combine these to produce a forward DFS, without revisiting, which scales better than either of the previous two alone.

Consider starting at instruction 1 and traverse every instruction you can reach, keeping track of everywhere you go, until you reach the first “jmp”/“nop”. At this point, we know the solution requires at least one change, so we swap the “jmp”/“nop” command, and continue. We go as far as we can, again keeping track of every instruction we visit in the same global vector. We abandon the route as soon as we reach an instruction we have already visited.

As we reached a repeated instruction, we know that the route was flawed AND we know that every instruction we have already visited is flawed. As any instruction which is part of a bad route cannot be a part of the good route. We continue from “jmp”/“nop” we encountered, but now we don’t switch it. We move along until we reach the next “jmp”/“nop” and switch that. Then we try to reach the end again, with the switched instruction. We are still using the same global visited vector so we cannot visit any instruction we have previously tried. The code for it looks like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// We must loop through and find the change in instruction that produces
// the correct code
std::vector<int> visited(instructions.size());
int i = 0;
while(i < instructions.size()){
	ans2 == 0;
	// Try flipping the instruction
	if (instructions[i].first == "jmp"){
		ans2 = computer2(instructions, visited, i+1);
	}
	else if (instructions[i].first == "nop"){
		ans2 = computer2(instructions, visited, i+instructions[i].second);
	}
	// Mark instruction as visited
	visited[i]++;
	// Have we found the good path?
	if (ans2 == 1) break;
	// Continue as if the instruction wasn't flipped
	if (instructions[i].first == "jmp")
		i += instructions[i].second;
	else
		i++;
}

We start at the first instruction and loop through flipping each “jmp”/“nop” instruction as we reach them. However, we have global visited vector which prevents us from ever visiting an instruction twice. This solution, despite being two-nested loops, (there is a loop in computer2), can only be visited once and thus the solution is O(N)-time and space. You can see the full optimised solution here: github

Note: each “jmp”/“nop” actually counts as two instructions because they can be flipped. We can visit an instruction and not flip it and find that it is flawed. But, we still need to try the instruction when it is flipped, as it may not be flawed. In the case every instruction is “jmp”/“nop” then we have 2 * N instructions to visit, so the problem is still O(N).

My input contained 623 instructions, with 302 “jmp”/“nop” so 925 instructions in total, from the point of view of the algorithm (double count the “jmp”/“nop” instructions). The algorithm then visits just 700 instructions, once each, before finding the optimal solution. Then we can just run the computer as in part 1, with the instruction fixed, which is again O(N).

. . . .

I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators

Back to my advent calendar

Comments

Back to all posts