Day 2 of the Advent of Code is a classic – implement a virtual machine for a simple assembly like. Eric Wastl, the creator of the AoC, has been writing challenges like this for years before the AoC even existed! All the way back in 2012, he made the Synacor Challenge, a programming challenge where you have to implement a VM with a few different instructions. The VM we have to implement for day 2 is much simpler than the one in the Synacor Challenge. We only need to implement three different instructions.
I did pretty well on day 2. I finished part 1 in six minutes and part 2 in another three. Those times were good enough to place me on the global leaderboard. I came in 82nd place for part 1 and 54th place for part 2. Now let’s dig into these problems.
For part 1, we need to implement a simple virtual machine called Intcode. Intcode has three different instructions: add, multiply, and halt. The input to the problem is a given as a list of comma separated integers, representing both the memory of the VM and the Intcode program to run. Each set of four numbers represent an instruction. For an instruction:
- The first number, the opcode, represents the instruction to run.
- 1 means add.
- 2 means multiply.
- 99 means halt.
- The second number is the memory location of the first argument to the instruction.
- The third number is the memory location of the second argument to the instruction.
- The fourth number is the memory location to write the result to.
One interesting detail is that since the memory serves both as memory and the code to run, Intcode programs have the ability to modify themselves. I’m sure this is a mechanic that’s going to be used in future AoC problems. Once we write our Intcode VM, the answer is the value that ends up at address 0 after running the input Intcode program.
Since the input to this problem is a comma delimited list of integers, we can reuse our readInput function from day 1 which read in a newline delimited list of integers. The only change we need to make is to split on commas instead of on newlines. We can also reuse our main function from day 1. All that’s left is to write is the solve function which takes the Intcode program, runs it, an returns the result.
When implementing a VM, the typical approach is to have a program counter (pc) that points to the location of the next instruction to execute. To run the program you perform the instruction at the current location, update the pc, and repeat. Since the program halts when the opcode for the current instruction is 99, our solve function will look like:
|
1 2 3 4 5 6 7 8 9 10 |
func solve(insts []int) int { pc := 0 for insts[pc] != 99 { // execute current instruction. // update pc } return insts[0] } |
Next, let’s fill in the code to execute the current instruction. To execute the current instruction. We need to look at the four values starting at pc. Let’s start by assigning these values to variables:
|
1 2 3 4 |
opcode := insts[pc] arg1Loc := insts[pc+1] arg2Loc := insts[pc+2] outputLoc := insts[pc+3] |
Then, to execute the instruction, we look at the opcode. If the opcode is 1, we read the two values at the input locations, add them together, and write the result to the output location. Likewise if the opcode is 2, we multiply the arguments together instead. With the given variables, this becomes this block of code:
|
1 2 3 4 5 |
if opcode == 1 { insts[outputLoc] = insts[arg1Loc] + insts[arg2Loc] } else if opcode == 2 { insts[outputLoc] = insts[arg1Loc] * insts[arg2Loc] } |
The last thing we need to do to execute an instruction is update the value of pc. To do this, we just add 4 to it since every instruction has a length of 4:
|
1 |
p += 4 |
One last detail I’ve omitted so far is that we are supposed to set the values of two different memory locations to specific values before executing the code. For me (it may be different for other people) I’m supposed to set memory location 1 to the value 12 and memory location 2 to the value 2. Putting everything we have so far together gives us our solve function for part 1:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
func solve(insts []int) int { insts[1] = 12 insts[2] = 2 pc := 0 for insts[pc] != 99 { opcode := insts[pc] arg1Loc := insts[pc+1] arg2Loc := insts[pc+2] outputLoc := insts[pc+3] if opcode == 1 { insts[outputLoc] = insts[arg1Loc] + insts[arg2Loc] } else if opcode == 2 { insts[outputLoc] = insts[arg1Loc] * insts[arg2Loc] } pc += 4 } return insts[0] } |
For part 2, we are supposed to figure out what inputs to the program result in a specific output value. The output value I’m supposed to achieve is 19690720. The two inputs, called the “noun” and the “verb” are to be written to the memory location 1 and 2 of our program. After we figure out the noun and verb, the answer to our problem is
|
1 |
100*noun + verb |
We are told that the noun and verb are somewhere between 0 and 99.
Since we are going to have to run the program repeatedly to figure out what inputs need to be fed to it, let’s rename our solve function from part 1 to runProgram. The runProgram function will also take two additional inputs, noun and verb:
|
1 |
|
1 2 3 4 5 6 7 8 |
func runProgram(insts []int, noun int, verb int) int { insts[1] = noun insts[2] = verb // rest of the function return insts[0] } |
Our new solve function will iterate through each possible value of noun and verb and determine which combination of values results in the target output. One thing we have to be careful about is we have to copy the input program each time before passing it to runProgram since runProgram does modify its input. Our new solve function looks like:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
func solve(insts []int) int { for noun := 0; noun <;= 99; noun++ { for verb := 0; verb <= 99; verb++ { instsCopy := append([]int(nil), insts...) if runProgram(instsCopy, noun, verb) == 19690720 { return 100*noun + verb } } } return -1 } |
And that’s it for part 2! You can find the code for this problem on my GitHub profile. I’m looking forward to seeing what’s in store for tomorrow.