⚠️ SPOILER ALERT ⚠️
This is a post with my solutions and learning from the puzzle. Don't continue reading if you haven't tried the puzzle on your own yet.
If you want to do the puzzle, visit adventofcode.com/2020/day/8.
My programming language of choice is python and all examples below are in python.
Key learning
- Simple compiler
This puzzle is a really simple compiler where we execute one of three instructions and only keep track of one value in memory. For those beginning to learn programmingmthis is valuable lesson to start understanding compilers and some of the core concepts of code.
Puzzle
The puzzle about is to executing a set of instructions according to a specification. We have three operators jmp, acc, nop. Each instuction is one operator followed
by a value.
Quoted from advent of code:
- 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.
Example input:
nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6
Part 1
The instructions we receive as input creates a program with an infinite loop. The puzzle is to figure out what the accumulator is at the end of first loop.
I'm using a set for keeping track of where the instruciton-cursor has been. With that we know when the first loop is complete.
Parsing input
# Read in instructions from file
lines = [x.strip() for x in open('08.input', 'r').readlines() if x != '']
# Create tuples (x,y) where x is instruction and y is value
lines = [tuple(x.split()) for x in lines]
Solution: Quick
Just by reading part 1 one might write some code like this. A while-loop with some if statements containing operations to execute.
It might look like this:
def part1():
lines_executed = set()
cursor, accumulator = 0, 0
while cursor not in lines_executed:
instruction = lines[cursor][0]
lines_executed.add(cursor)
if instruction == 'jmp':
cursor += int(lines[cursor][1])
elif instruction == 'nop':
cursor += 1
elif instruction == 'acc':
accumulator += int(lines[cursor][1])
cursor += 1
else:
raise Exception('Unexpected instruction', instruction)
return accumulator
print part1()
Solution: Extendable
Those that competed in AoC 2019 might have some flashbacks of the intcode that has it similarities. A simple compiler with a few instructions. That puzzle came back multiple times and we had to built upon our compiler with new operations and features. Investing in good structure at the beginning might be beneficial for coming puzzles.
Therefore I suggest finding a structure that you find more extendable.
Here is a suggestion:
def execute_program(lines):
lines_executed = set()
cursor = 0
accumulator = 0
def acc(lines, cursor, accumulator):
return (cursor + 1, accumulator + int(lines[cursor][1]))
def jmp(lines, cursor, accumulator):
return (cursor + int(lines[cursor][1]), accumulator )
def nop(lines, cursor, accumulator):
return (cursor + 1, accumulator)
while cursor not in lines_executed:
instruction = lines[cursor][0]
lines_executed.add(cursor)
operations = {
'jmp': jmp,
'acc': acc,
'nop': nop,
}
operation = operations[instruction]
cursor, accumulator = operation(lines, cursor, accumulator)
return accumulator
print "Solution part 1: %d" % execute_program(lines)
Do you find it more readable? Do you have other solutions or tips on making the compiler more extendable?
Part 2
We find out that one jmp or nop should be the other for executing the program without infinite loop.
Our execute program needs minimal change. Just a variable (terminated) to keep track if we reached the last instruction.
Then we just have to iterate through all jmp and nop, switch them, execute the program, and see if it was terminated or not.
Solution
def execute_program(lines):
lines_executed = set()
cursor = 0
accumulator = 0
def acc(lines, cursor, accumulator):
return (cursor + 1, accumulator + int(lines[cursor][1]))
def jmp(lines, cursor, accumulator):
return (cursor + int(lines[cursor][1]), accumulator )
def nop(lines, cursor, accumulator):
return (cursor + 1, accumulator)
terminated = False
while not terminated and cursor not in lines_executed:
instruction = lines[cursor][0]
lines_executed.add(cursor)
operations = {
'jmp': jmp,
'acc': acc,
'nop': nop,
}
operation = operations[instruction]
cursor, accumulator = operation(lines, cursor, accumulator)
# Terminate if end at program
terminated = cursor == len(lines)
return terminated, accumulator
def part2(lines):
for i in range(len(lines)):
# Copy lines so that changes don't persist.
local_lines = [x for x in lines]
# Switch statement jmp/nop
if 'jmp' in local_lines[i][0]:
local_lines[i] = ('nop', local_lines[i][1])
elif 'nop' in local_lines[i][0]:
local_lines[i] = ('jmp', local_lines[i][1])
terminated, result = execute_program(local_lines)
if terminated:
break
return result
print "Solution part 2: %d" % part2(lines)
Thanks for reading!
I hope these solutions were insightful for you.
Complete code can be found at: github.com/cNille/AdventOfCode/blob/master/2020/08.py
Latest comments (0)