Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!
In this installment, I share my Python solution to Day 8 of Advent of Code, titled Handheld Halting.
Spoiler alert!
Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 8 challenge.
The Day 8 challenge, part one
The challenge
Here’s the text from part one of the challenge:
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.
You narrow the problem down to a strange infinite loop in the boot code (your puzzle input) of the device. You should be able to fix it, but first you need to be able to run the code in isolation.
The boot code is represented as a text file with one instruction per line of text. Each instruction consists of an operation (
acc,jmp, ornop) and an argument (a signed number like+4or-20).
accincreases or decreases a single global value called the accumulator by the value given in the argument. For example,acc +7would increase the accumulator by 7. The accumulator starts at0. After anaccinstruction, the instruction immediately below it is executed next.jmpjumps to a new instruction relative to itself. The next instruction to execute is found using the argument as an offset from thejmpinstruction; for example,jmp +2would skip the next instruction,jmp +1would continue to the instruction immediately below it, andjmp -20would cause the instruction 20 lines above to be executed next.nopstands 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 +6These instructions are visited in this order:
nop +0 | 1 acc +1 | 2, 8(!) jmp +4 | 3 acc +3 | 6 jmp -3 | 7 acc -99 | acc +1 | 4 jmp -4 | 5 acc +6 |First, the
nop +0does nothing. Then, the accumulator is increased from 0 to 1 (acc +1) andjmp +4sets the next instruction to the otheracc +1near the bottom. After it increases the accumulator from 1 to 2,jmp -4executes, setting the next instruction to the onlyacc +3. It sets the accumulator to 5, andjmp -3causes the program to continue back at the firstacc +1.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.
Immediately before the program would run an instruction a second time, the value in the accumulator is
5.Run your copy of the boot code. Immediately before any instruction is executed a second time, what value is in the accumulator?
Importing the data
Every Advent of Code participant gets their own set of data. I copied my data and went through my usual process of bringing it into a Jupyter Notebook running a Python kernel.
This involves pasting it into a triple-quoted string and then assigning its value to the variable main_raw_input:
main_raw_input = """acc +37 acc -4 nop +405 jmp +276 acc +39 acc +40 acc -3 jmp +231 acc +44 acc +12 jmp +505 acc +35 jmp +282 acc +23 jmp +598 nop +392 acc +18 acc +44 acc +18 jmp +297 nop +460 jmp +152 nop +541 acc +33 jmp -11 acc -5 acc +9 jmp +327 acc +30 acc -1 acc -3 jmp +50 acc +22 acc +18 acc +33 acc +37 jmp +57 acc -17 acc -6 acc -2 jmp +535 acc -15 jmp +279 acc +34 acc +44 acc +41 jmp +349 acc +2 acc +6 nop +351 nop +252 jmp +505 jmp +1 jmp +1 nop +61 jmp +524 nop +351 jmp +399 acc +1 nop +397 acc +39 nop +141 jmp +134 acc +46 acc +14 acc +26 jmp +236 acc +7 acc -6 acc +35 jmp +397 acc +15 jmp +140 acc +3 acc -4 acc +37 acc +12 jmp +86 jmp +416 jmp +1 jmp +55 acc -19 jmp +536 jmp +1 acc -11 acc +15 jmp -61 acc +25 jmp -25 acc +50 acc +43 jmp +1 jmp +140 acc +46 nop -53 acc +1 nop +440 jmp +488 jmp +396 nop +443 acc +41 jmp +168 acc +25 nop +383 acc +12 acc -19 jmp +21 acc +29 acc +30 jmp +497 jmp +502 jmp +417 nop +351 acc -15 jmp +243 acc +21 acc +16 jmp +332 acc +28 acc +22 acc +38 jmp +476 acc +8 acc -11 jmp +458 acc +9 jmp +246 acc +40 acc +31 acc +26 jmp +218 acc +27 acc +9 nop +347 jmp +478 nop +28 nop +106 acc +25 acc -15 jmp +397 acc +31 jmp +231 acc -4 nop +136 acc +14 jmp +181 jmp +361 acc +16 acc +11 jmp -108 nop +299 acc +21 acc -2 jmp -106 jmp +246 acc +31 jmp +407 jmp +377 acc +43 acc -12 nop +142 acc +8 jmp -91 jmp +1 acc +34 acc +5 acc +31 jmp +12 acc +34 acc +7 acc +34 acc +20 jmp -45 acc -11 acc +41 acc +10 jmp +310 nop -106 jmp -36 acc +23 acc +46 acc +46 jmp +112 acc +41 nop +179 acc +17 nop +356 jmp +147 acc +42 nop +49 jmp +119 acc +0 acc +7 acc -18 acc -8 jmp +11 acc +12 acc +38 acc +39 jmp +281 nop +186 jmp +162 acc +44 acc +20 jmp +153 jmp +395 acc +49 jmp +1 acc +2 jmp +1 jmp -31 jmp +301 nop +97 jmp -102 jmp +262 acc +28 acc -15 acc +44 acc -13 jmp +191 jmp +281 acc +36 acc +1 nop +15 jmp +211 acc +6 acc -4 jmp +42 acc +34 acc +0 jmp +104 jmp +311 jmp +84 acc +43 acc -8 acc -10 acc +38 jmp -90 acc +49 jmp +303 nop +132 jmp +301 nop +60 acc +37 nop +96 jmp +182 acc +16 acc +18 nop +152 acc +19 jmp +325 jmp -63 acc +28 jmp +56 acc +18 acc +29 acc +33 jmp -115 acc +47 acc +19 jmp +1 nop +41 jmp +1 jmp -207 nop -62 acc -9 acc +42 acc -12 jmp -56 acc +28 jmp -163 acc +25 acc +17 jmp -217 acc +7 jmp +272 acc +43 acc +22 jmp +70 acc -17 jmp -117 acc +24 acc +26 nop -275 jmp -46 nop +87 acc +19 acc +28 jmp -34 acc +4 acc +9 acc +6 jmp +1 jmp +28 acc -6 nop -67 acc -10 jmp +271 acc +40 acc +25 acc -4 jmp -63 acc +46 jmp +78 acc +41 nop -126 nop +70 jmp +1 jmp +172 nop +270 jmp +30 jmp +1 acc +38 nop +68 acc +29 jmp +253 acc -18 jmp -89 acc +18 acc +30 jmp +147 acc +24 acc +11 acc +50 jmp -225 jmp -210 acc -18 acc +1 acc +38 jmp +1 jmp -79 acc +45 acc +12 jmp +209 jmp -207 acc +32 acc +4 acc +32 acc +14 jmp +83 acc +13 acc +1 acc +46 acc +38 jmp +28 nop +153 acc -17 jmp -73 acc +11 jmp +248 acc +29 acc +45 acc +16 jmp +96 jmp -273 acc +34 jmp +87 nop +99 acc -3 jmp -74 acc +12 nop -119 jmp -141 acc -18 nop -79 acc +1 acc +6 jmp +9 acc +3 acc +44 acc +39 jmp -165 acc +6 jmp +44 acc +25 jmp -133 acc +0 jmp +14 jmp +1 acc +1 jmp -223 jmp +71 nop -1 acc +22 acc +11 jmp -274 jmp -330 acc +45 jmp +1 acc +15 jmp -158 jmp -128 acc +50 acc +26 jmp -73 nop +99 jmp +71 acc +35 acc +7 jmp +192 acc +13 jmp +190 acc +4 acc -1 acc +40 acc -15 jmp +50 acc +29 jmp -337 jmp -75 acc +41 jmp +1 jmp -387 acc +28 acc +18 acc +19 jmp -62 nop -196 jmp -410 jmp +1 acc -17 jmp -267 acc +22 jmp -301 nop -98 acc -15 jmp -124 acc +45 acc -18 acc +15 acc +42 jmp -296 nop -10 acc +29 jmp -371 acc +3 jmp +1 nop +61 acc +5 jmp -361 acc -5 nop -326 jmp -379 acc -10 jmp +1 acc +44 jmp -231 acc +3 jmp -94 acc +1 jmp +113 jmp -336 acc +4 jmp -299 acc -13 jmp +1 acc +13 jmp +143 acc -11 acc -19 acc +18 nop -390 jmp -27 acc +42 jmp -232 acc +15 jmp -228 acc +21 acc +39 acc +47 acc +6 jmp +57 acc +28 acc +27 acc +50 jmp -397 acc +12 jmp -445 acc +30 jmp -352 acc -4 acc +26 acc +48 jmp +1 jmp -205 jmp +22 nop -284 acc -1 nop -361 acc +0 jmp -368 acc -17 nop -223 jmp -41 acc +4 acc +46 jmp +79 jmp -370 jmp -260 acc +42 jmp -14 acc +30 acc +50 acc +13 jmp -61 acc +46 jmp -63 nop -55 nop -320 jmp -11 acc +10 jmp -424 jmp -11 acc +3 jmp -71 acc +42 acc -13 jmp +4 nop -155 nop -138 jmp +62 acc +11 acc +19 acc +15 acc +17 jmp -73 acc -11 jmp -273 acc +8 acc +6 acc -7 acc +41 jmp -311 jmp -111 jmp -260 jmp +50 jmp -60 jmp +1 nop -89 acc +36 acc +14 jmp -220 nop -415 acc +28 jmp -402 acc +41 jmp -165 acc +9 acc -13 acc -18 acc +18 jmp -504 acc -9 acc +29 acc +44 jmp -444 acc +5 acc +47 jmp -545 acc +23 acc +7 nop -240 jmp -320 jmp -141 jmp +1 acc +28 nop -287 jmp -118 acc +44 acc -7 jmp -550 acc +10 acc +20 acc -3 jmp -401 acc +45 acc +36 jmp -375 jmp -485 acc +9 jmp -338 jmp -510 jmp -196 acc -16 jmp -372 acc +0 jmp -380 acc -3 nop -473 nop -361 jmp -311 acc +0 nop +20 jmp -436 acc +9 jmp +1 jmp -215 acc +19 jmp -451 jmp -43 acc -13 acc -10 acc -5 jmp -208 acc -11 jmp -156 acc +11 acc -2 nop -357 jmp -73 acc +21 jmp -159 acc +28 acc -16 acc +12 acc +1 jmp -282 jmp -131 acc -11 acc +45 acc +0 acc +28 jmp +1"""
Building the data structure
With the data imported, the next step was to build an appropriate data structure. Since today’s puzzle was based on simplified microprocessor instructions, I thought that the data structure should do the same.
I wanted my data structure to look like the table below, which shows the instructions from extracted from the first five lines of the data given to me:
| Index | Opcode | Operand |
|---|---|---|
| 0 | acc | 37 |
| 1 | acc | -4 |
| 2 | nop | 405 |
| 3 | jmp | 276 |
| 4 | acc | 39 |
Here’s the function that I wrote to convert the input data into the data structure:
def input_to_instructions(input_data):
instructions = []
split_input = input_data.splitlines()
for item in split_input:
instruction = {}
opcode_operand = item.split()
instruction["opcode"] = opcode_operand[0]
instruction["operand"] = int(opcode_operand[1])
instructions.append(instruction)
return instructions
With the function defined, here’s how I used it to create the data structure, which I assigned to a variable named instructions:
>>> instructions = input_to_instructions(main_raw_input)
>>> print (instructions)
[{'opcode': 'acc', 'operand': 37},
{'opcode': 'acc', 'operand': -4},
{'opcode': 'nop', 'operand': 405},
{'opcode': 'jmp', 'operand': 276},
{'opcode': 'acc', 'operand': 39},
...
]
I then wrote accumulator_value_at_first_repeat(), the function that would use the data structure contained within instructions to solve the first challenge:
def accumulator_value_at_first_repeat(instructions):
program_length = len(instructions)
program_counter = 0
accumulator = 0
executed_instructions = set()
repeat_instruction_encountered = False
while 0 <= program_counter < program_length:
current_instruction = instructions[program_counter]
if program_counter in executed_instructions:
repeat_instruction_encountered = True
break
else:
executed_instructions.add(program_counter)
if current_instruction["opcode"] == "jmp":
program_counter += current_instruction["operand"]
continue
elif current_instruction["opcode"] == "acc":
accumulator += current_instruction["operand"]
elif current_instruction["opcode"] == "nop":
pass
else:
print("Something went wrong in accumulator_value_at_first_repeated_instruction().")
print(f"pc = {program_counter} acc = {accumulator}")
print(f"instruction:\n{instruction}")
program_counter += 1
if repeat_instruction_encountered:
print(f"The accumulator's contents at the first repeated instruction is: {accumulator}.")
else:
print("Reached end of instructions without repeating any of them.")
When run, it sets up the following variables:
program_length: The number of instructions in the data structure.program_counter: The program’s equivalent of the “program counter (PC)” register in a microprocessor; contains the index the instruction to be executed.accumulator: The program’s equivalent of an accumulator in a microprocessor. For those of you who aren’t familiar with what happens at the microprocessor level, think of the accumulator as a “scratchpad” variable where you do all the math.executed_instructions: A set (which means that every value in it is unique) of the indices of all the instructions that have already been executed. We use it to determine if a given instruction has already been run, at which point we should stop the program and see what the value in the accumulator is.repeat_instruction_encountered: A flag that should be set toTruewhen an instruction is about to be executed a second time.
The function’s main loop performs a greatly simplified version of a microprocessor’s “fetch-decode-execute” cycle:
- Fetch the current instruction, which is the one whose index is specified by
program_counter. - See if the instruction has been executed before. If this is the case, exit the loop; otherwise, recording this instruction as having been executed.
- Decode the current instruction:
- If the instruction is jmp, add the operand value to
program_counterand go back to the start of the loop. - If the instruction is acc, add the operand value to
accumulator. - If the instruction is nop, do nothing.
- If the instruction is anything else, display an error message.
- If the instruction is jmp, add the operand value to
- After the loop is done, if the
repeat_instruction_encounteredflag is set, we’ve found the value we’re looking for — display it! Otherwise, display a message saying that we’ve reached the end of the instructions without ever repeating one.
I ran the function…
>>> accumulator_value_at_first_repeat(instructions) The accumulator's contents at the first repeated instruction is: 1801.
…and got my result: 1801.
The Day 8 challenge, part two
The challenge
After some careful analysis, you believe that exactly one instruction is corrupted.
Somewhere in the program, either a
jmpis supposed to be anop, or anopis supposed to be ajmp. (Noaccinstructions 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
jmpornop, you can repair the boot code and make it terminate correctly.For example, consider the same program from above:
nop +0 acc +1 jmp +4 acc +3 jmp -3 acc -99 acc +1 jmp -4 acc +6If you change the first instruction from
nop +0tojmp +0, it would create a single-instruction infinite loop, never leaving that instruction. If you change almost any of thejmpinstructions, the program will still eventually find anotherjmpinstruction and loop forever.However, if you change the second-to-last instruction (from
jmp -4tonop -4), the program terminates! The instructions are visited in this order:nop +0 | 1 acc +1 | 2 jmp +4 | 3 acc +3 | jmp -3 | acc -99 | acc +1 | 4 nop -4 | 5 acc +6 | 6After the last instruction (
acc +6), the program terminates by attempting to run the instruction below the last instruction in the file. With this change, after the program terminates, the accumulator contains the value8(acc +1,acc +1,acc +6).Fix the program so that it terminates normally by changing exactly one
jmp(tonop) ornop(tojmp). What is the value of the accumulator after the program terminates?
Here’s the function I wrote to solve this challenge:
def accumulator_value_and_halt_at_first_repeat(instructions, switch_opcode_address=-1):
program_length = len(instructions)
program_counter = 0
accumulator = 0
executed_instructions = set()
while 0 <= program_counter < program_length:
current_instruction = instructions[program_counter]
if program_counter in executed_instructions:
return {
"halted": False,
"program_counter": program_counter,
"accumulator": accumulator
}
else:
executed_instructions.add(program_counter)
opcode = current_instruction["opcode"]
operand = current_instruction["operand"]
if program_counter == switch_opcode_address:
print(f"Changing opcode at address {program_counter}")
if opcode == "jmp":
print("- Changing jmp to nop")
opcode = "nop"
elif opcode == "nop":
print("- Changing nop to jmp")
opcode = "jmp"
if opcode == "jmp":
program_counter += operand
continue
elif opcode == "acc":
accumulator += operand
elif opcode == "nop":
pass
else:
print("Something went wrong in accumulator_value_at_first_repeated_instruction().")
print(f"pc = {program_counter} acc = {accumulator}")
print(f"instruction:\n{instruction}")
program_counter += 1
return {
"halted": True,
"program_counter": program_counter,
"accumulator": accumulator
}
The function, accumulator_value_and_halt_at_first_repeat(), is an expanded version of the function from part one, accumulator_value_at_first_repeat().
In addition to a set of instructions, it takes an additional parameter: the address of an instruction that should be changed — either from jmp to nop, or from nop to jmp.
The function still performs the “fetch-decode-execute” loop, and it exits the loop if it’s about to execute an instruction that’s already been executed. The main difference is that if the current instruction is the one flagged for change, it changes the instruction appropriately.
I wrote the accumulator_value_and_halt_at_first_repeat() function to be used by the function below:
def run_instructions_with_mods(program):
for index in range(len(program)):
instruction = program[index]
if instruction["opcode"] != "acc":
print(f"Found jmp or nop at address: {index}")
result = accumulator_value_and_halt_at_first_repeat(program, index)
if result["halted"]:
print(f"Found it! {result}")
break
else:
print(f"Not the correct instruction.")
This function goes through all the instructions in the set, looking for any jmp or nop instructions. When it finds one, it runs the program using accumulator_value_and_halt_at_first_repeat(), marking the jmp or nop instruction as the one to be changed.
This lets us modify the program, one jmp or nop instruction at a time, in order to find which change to a jmp or nop instruction is the one that allows the program to reach the end of the instructions.
Here’s an abridged version of what happened when I ran the function:
>>> run_instructions_with_mods(instructions)
Found jmp or nop at address: 2
Changing opcode at address 2
- Changing nop to jmp
Not the correct instruction.
Found jmp or nop at address: 3
Changing opcode at address 3
- Changing jmp to nop
Not the correct instruction.
Found jmp or nop at address: 7
Not the correct instruction.
Found jmp or nop at address: 10
Changing opcode at address 10
- Changing jmp to nop
Not the correct instruction.
...
Found jmp or nop at address: 207
Changing opcode at address 207
- Changing jmp to nop
Not the correct instruction.
Found jmp or nop at address: 209
Changing opcode at address 209
- Changing jmp to nop
Not the correct instruction.
Found jmp or nop at address: 210
Changing opcode at address 210
- Changing jmp to nop
Found it! {'halted': True, 'program_counter': 623, 'accumulator': 2060}
I entered 2060 as my answer, and step two was complete.