Advent of Code
-~*~-
/!\
/%;@\
o/@,%\o
/%;`@,\
o/@'%',\o
'^^^N^^^`Advent of Code is a race to solve programming problems as quickly as you can, using any language or resources you like. Twenty-five challenges are released through December; I have participated since 2018, although I missed 2020.
2019
In 2018, my goal was to complete all the problems. In 2019, I focused on writing clean code and documenting more of my experience.
You can find all of these solutions on GitHub: lazydancer/Advent-of-Code-2019.
Day 1: The Tyranny of the Rocket Equation
For Part 1, we simply divide each module's mass by 3, round down, and subtract 2. The only unusual part of my code is //, Python's floor-division operator.
For Part 2, we need to account for the mass of the fuel itself. A while loop repeatedly calculates the extra fuel until the formula returns zero or a negative value.
The puzzle's title refers to the ideal rocket equation, which is interesting to derive. We begin with conservation of momentum: the total momentum of a closed system remains constant.
With an appropriate sign convention, the momentum balance simplifies to m dv = -v_exhaust dm.
In other words, the change in the ship's momentum is balanced by the momentum of the expelled exhaust.
Rearranging and integrating, using the facts that the integral of 1/x is ln(x) and that ln(a) - ln(b) = ln(a/b), gives the ideal rocket equation:
v_final - v_initial = v_exhaust * ln(m_initial / m_final)
Day 2: 1202 Program Alarm
For Part 1, we run a program with an instruction pointer that advances four positions after each instruction. A simple for loop works here, although it would not handle instructions of different lengths.
For Part 2, we vary the two inputs until the program produces the desired result. Each input has 100 possible values, so there are only 10,000 ordered pairs to test. I generated them with the built-in itertools.product function.
Day 3: Crossed Wires
I solved this one in Rust.
For Part 1, we trace each wire and store the locations it visits. A HashSet makes it easy to find the intersection of those two sets of locations.
For Part 2, we find the intersection reached in the fewest combined steps along the two wires.
Day 4: Secure Container
For Part 1, we can find adjacent matching digits by shifting a copy of the sequence by one position and comparing it with the original.
For Part 2, we can count the length of each run of matching digits and check whether any run is two digits long.
Day 5: Sunny with a Chance of Asteroids
Back to Python.
For Part 1, I extended the code from Day 2 with input and output instructions. I made the INPUT value a global constant.
For Part 2, I added more instructions and separated the instruction pointer from the for loop.
Day 6: Universal Orbit Map
For Part 1, we create a map from each object to the object it orbits, then follow each chain back to the root. The root can be found by taking the difference between the sets of parents and children. A hash map makes each lookup quick.
For Part 2, we trace the paths from YOU and SAN back to the root. After removing the shared portion, the lengths of the remaining paths give the number of orbital transfers between them.
Day 7: Amplification Circuit
For Part 1, we use itertools.permutations to try every phase setting and keep the maximum output.
For Part 2, I did not finish in the time I had. The program needs to retain its state between outputs, so I planned to return to it with a stateful amplifier class.
Day 8: Space Image Format
For Part 1, we split the transmission into layers and use min and count to find the layer with the fewest zeroes.
For Part 2, a function examines each pixel position from front to back and returns the first non-transparent value, either 0 or 1.
Day 9: Sensor Boost
After debugging for a while, I left this one unfinished. I hope to return to the challenge.
Day 10: Monitoring Station
For Part 1, I tested each asteroid's line of sight by expanding a box around it and treating nearer asteroids as shadows that block those behind them.
2018
Advent of Code is a good way to grow as a programmer: you solve the problems, then read how everyone else did it. Two things I learned that year:
1. Assembly Language
I have always been interested in how computers work; see Making a Transistor. I had yet to program in assembly. That changed on Day 16, when the challenge introduced a small instruction set called Elfcode. Elfcode looked much like assembly.
4 0 2 0
13 2 0 2
2 2 3 2
4 3 2 3
3 3 2 2
13 2 1 2
6 2 1 1
10 1 2 3
4 2 3 0
13 1 0 1
2 1 1 1
The first number is the opcode, which could represent one of 16 operations, such as add, mul, or mov. The second and third numbers are inputs, and the last identifies the output register.
First, I wrote the code in Python. It was far too slow, even with PyPy and a better data structure. I reduced the runtime to one-tenth of the original, but stopped it after three hours.
To solve it efficiently, you need to watch how the Elfcode executes, find the pattern, and simplify the logic. I was curious whether the original program could instead run directly on the hardware.
Using C as an intermediate step, I produced the assembly excerpt below. A semicolon starts a comment, and l01, l02, l03, and l07 are labels. For example, the first command is jmp l17, which jumps to label l17.
jmp l17 ; L00: goto *jump_table[0+16+1]; //addi 3 16 3
l01: mov r11, 1 ; L01: reg[1] = 1; //seti 1 2 1
l02: mov r12, 1 ; L02: reg[2] = 1; //seti 1 1 2
l03: mov rax, r11 ; L03: reg[5] = reg[1] * reg[2]; //mulr 1 2 5
mov rbx, r12 ;
imul rax, rbx ;
mov r15, rax ;
cmp r15, r14 ; L04: reg[5] = reg[5] == reg[4]; //eqrr 5 4 5
sete al ; Grab the flag
movzx r15, al ; Move the flag to r15 extends with zeros
je l07 ; L05: goto *jump_table[reg[5] + 5 + 1]; //addr 5 3 3
jmp l08 ; L06: goto *jump_table[6 + 1 + 1]; //addi 3 1 3
l07: add r10, r11 ; L07: reg[0] = reg[1] + reg[0]; //addr 1 0 0
In the end, the assembly still was not fast enough, despite being roughly 20 times faster than my original Python implementation.
Along the way, I learned about x86-64 instructions, registers, flags, and jumps. I also learned why assembly is rarely written by hand. This code ran about as fast as my C version, but it was harder to follow and less portable. Below is code that writes a value to standard output.
print:
mov [value], r10
mov rax, 1 ; system call for write
mov rdi, 1 ; file handle 1 is stdout
mov rsi, value ; address of string to output
mov rdx, 8 ; number of bytes
syscall ; invoke operating system to do the write
mov rax, 60 ; system call for exit
xor rdi, rdi ; exit code 0
syscall ; invoke operating system to exit
All the code can be found on GitHub.
2. Python Imports
Most of the time, I avoid Python imports because the built-in data types do the job. During these challenges, however, I came to appreciate defaultdict, copy, and deque, as well as NetworkX for graphs and re for regular expressions.
defaultdict — Supplying a default value for a missing key is very useful.
somedict = {}
print(somedict[3]) # KeyError
someddict = defaultdict(int)
print(someddict[3]) # print int(), thus 0copy — Because variables can refer to the same mutable list, copying is useful when you want to avoid changing the original.
import copy
copy.copy(x)
copy.deepcopy(x)deque — A double-ended queue, useful when efficient appends, pops, or rotation are needed.
d = deque(xrange(10))
d.rotate(2)NetworkX — This was useful for many graph problems; I used its shortest-path functions several times.
graph = networkx.Graph()
# ...adding nodes...
result = networkx.shortest_path(graph)re — This popular regular-expression library was one I had previously tried to avoid.
Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.
list(map(int, re.findall(r'-?\d+', line)))
During the challenge, I read as much as I coded. Reading other people's code was enlightening: I could see how they approached each problem and which trade-offs they chose.
Thank you to Eric Wastl for creating Advent of Code, and to everyone who shared solutions online. I learned a lot.