Python Tips & Tricks for the Advent of Code 2019

I signed up for the Advent of Code after a coworker of mine mentioned that he was doing it. I was instantly hooked on collecting gold stars. I collected my last star a few days after Christmas and thoroughly enjoyed the process. There’s something very satisfying about working on problems with clear right and wrong answers!

I wrote all my solutions in Python, which may come as a surprise given that I recently published a book on TypeScript. But for very small command line programs, it’s just hard to beat the convenience of Python.

There are a few Python tricks that I found helpful in setting up my solutions. If you’re new-ish to Python, you might find them helpful! Read on.

Day 1: The Tyranny of the Rocket Equation

problem / solution

This one introduces the format for the problems and solutions (two per day, solutions are numbers) and the idea that you get your own sample input. I found Python’s fileinput module to be an extremely natural fit for all the Advent of Code problems. To read input using fileinput, you do something like this:

import fileinput
if __name__ == '__main__':
    lines = [*fileinput.input()]
    process(lines)

Then you can invoke your program from the command line in a few different ways:

echo 'input' | ./day1.py
cat input.txt | ./day1.py
./day1.py input.txt

The echo form was convenient for small sample inputs in the problem description. The last form was convenient for my own puzzle input.

Day 2: 1202 Program Alarm

problem / solution

This one introduces Intcode, which proved to be a recurring theme in this year’s Advent of Code. Doing this one with Alex made me appreciate that part 1 ensured you got the basics right before part 2 forced you to think more clearly about memory/state.

Day 3: Crossed Wires

problem / solution

This was the first day with a grid input, another recurring theme in the Advent of Code. The most common ways to represent a 2D grid are with an array of arrays or a 2D array (in a language that supports it). But a more convenient form in Python is a dict indexed by (x, y) tuples:

grid = {
  (0, 0): '.',
  (0, 1): '#',
  (1, 0): '#',
  (1, 1): '.',
}

This has a few advantages over lists of lists or 2D arrays:

• You don’t have to worry about row-major vs. column-major order.
• You don’t thave to worry about bounds checking: grid.get((-1, 0)) is valid and returns None, whereas negative indexing in a list will do something different.
• You don’t need to know the size of the grid in advance. This is especially helpful if you’re starting in the middle and exploring a space, as on Day 15. Negative indices are OK.

Here’s a compact way to read a grid in this form using fileinput, enumerate and a dict comprehension:

grid = {
  (x, y): v
  for y, row in enumerate(fileinput.input())
  for x, v in enumerate(row.strip())
}

You can get the range of indices using min / max with a generator:

def minmax(it):
    vals = list(it)
    return min(vals), max(vals)
minx, maxx = minmax(x for x, y in grid.keys())
miny, maxy = minmax(y for x, y in grid.keys())

And you can find unexplored nodes in a grid using another generator expression:

explored_nodes = {...}
moves = [
    (-1, 0),
    (+1, 0),
    (0, -1),
    (0, +1),
]
new_nodes = {
    x + dx, y + dy
    for x, y in current_nodes
    for dx, dy in moves
    if grid.get((x + dx, y + dy)) == '.'
    and (x + dx, y + dy) not in explored_nodes
}

If the repetition of x + dx, y + dy bothers you, you can eliminate it using one of Python 3.8's assignment expressions (aka the "walrus operator"):

new_nodes = {
    node
    for x, y in current_nodes
    for dx, dy in moves
    if grid.get(node := (x + dx, y + dy)) == '.'
    and node not in explored_nodes
}

Python doesn’t have a comma operator, so writing grid[x, y] and grid[(x, y)] are equivalent. It still scares me though!

Day 7: Amplification Circuit

problem / solution

Part two of this was the first one that gave me real trouble. I refactored my Intcode runtime into a class but didn’t update all the references from memory to self.memory. There happened to be a global of the same name, which meant that (surprisingly to me) all five of my amps were sharing a single memory. It was unclear from the problem statement when the system halted: was it when the last amp terminated? Or all of them? This was a big headache until I spotted the bug.

Day 10: Monitoring Station (Asteroid lines of sight)

problem / solution

I found this one quite fun. Two asteroids are in the same line of sight if (x1, y1) and (x2, y2) reduce to the same fraction. Python’s math module has a gcd function (greatest common divisor) which helps with this. Indexing the asteroids by (dx / gcd(dx, dy), dy / gcd(dx, dy)) does the trick.

A few other tricks for this one:

• itertools.combinations(xs, 2) returns an iterator over all pairs.
• math.atan2 is a version of arctangent that takes x and y as two separate arguments (unlike regular math.atan, which takes y/x). This ensures you get an angle back that's in the correct quadrant: key for part 2!
• defaultdict(list) is a convenient way to index a list by something. For example, to index the asteroids by their angle (as in part 2):

Using math.atan2 and defaultdict(list) to index the list of asteroids by angle

Day 12: The N-Body Problem

problem / solution

I really struggled with part two of this one. In retrospect, calling this “gravity” and introducing the concepts of potential energy and kinetic energy in part one were red herrings. I looked for patterns in how frequently a subset of bodies repeated their positions + velocities and found a few intriguing patterns but nothing I could turn into an answer. Then I looked for patterns in each coordinate (x, y, z) and realized that “gravity” in this problem operated on each axis independently, so you could run three separate simulations.

Day 13: Care Package (Breakout game)

problem / solution

This was probably my least favorite problem. Usually I’d implement anything visual in JavaScript in a browser, but I wanted to reuse my battle-tested Python Intcode implementation. So I implemented the game using curses, something I wouldn't wish on anyone. I thought this would be the hard part of part 2, but the game itself turned out to be extremely difficult!

I tried a series of measures to make it easier:

• Adding a save/restore feature.
• Adding an indicator for where the ball would land on the bottom.

But I kept getting stuck and found playing the game very much not fun. I figured my two paths forward were to make the computer play the game itself, or to reverse-engineer the scoring function. I wound up doing the latter.

If you look at the puzzle input, there’s a big section of 0s, 1s and 2s which corresponds to the breakout board. After that is scores for each square. But if you add up all the scores for squares that are blocks, you’ll get the wrong answer. There’s some trickery going on. I logged whenever a block was broken and when a memory address in that range was read but didn’t see a clear relationship. So I set a breakpoint and stepped through the Intcode. It winds up being a sort of hash function. Just enough obfuscation to make this non-trivial. Here it is:

def address_for_block(x, y):
   return 1664 + ((((((25 * x + y) * 521) + 1011) % (64 * 1025)) % (8 * 1025)) % 1025)

Day 14: Space Stoichiometry

problem / solution

This was the first one I did where runtime performance was a limiting factor. I tried working my way back from FUEL to ORE by greedily running the least-wasteful reactions. Predictably, this didn’t give optimal results. A full recursive search was too expensive. I tried keeping track of the least amount of ORE needed to date to prune, but this was ineffective. I noticed that there were always a few chemicals that were directly convertible to ORE, so I added these to the filter. This helped some but not enough. As I was tweaking this, I noticed that you could split the reactions into distinct “generations”. Each chemical produced in generation 1 is used as a reactant in generation 2. No chemical is in multiple generations. This lets you implement a very fast greedy solution.

I really liked part two. It reminds me of why you can phrase complexity problems as “maximize f(x)” vs. “is there a value v such that f(x) > v”. If you know the max then the second formulation is trivial. But if you have an algorithm for the latter and some sort of upper bound, you can get to the former in log time using binary search.

Day 15: Oxygen System

problem / solution

aka exploring a space with a robot. I tried programming the robot to explore in an intelligent way (trace the shortest path to open nodes) but kept getting stuck in loops. Eventually I realized that random movements + time work wonders.

Day 16: Flawed Frequency Transmission

problem / solution

This wound up being the last problem I solved. I figured there was a clever math way to do this, but the problem size isn’t that big (10,000 x ~600 values in input = 6M element array). So I sped things up a bit using a numpy array and np.cumsum to calculate the cumulative sums. This gave me a program that would complete in something like 2-4 hours. I could have spent more time thinking about the math to speed it up, but I was getting social pressure to take my Christmas vacation more seriously. So I just let it run and went to enjoy some hammock time. Easy decision!

I decided to hang out on these hammocks while my slow solution to Day 16 ran.

Bob pointed out later that the position of interest is in the latter half of the array, which makes all the math much simpler.

Day 18: Many-Worlds Interpretation (Maze & Keys)

problem / solution

I found this to be the hardest problem of the season. I just couldn’t get the second-to-last sample (the one with lots of optionality) to terminate.

The first trick is to realize that solutions are just a sequence of keys, and you can precompute the distance between all keys and the set of doors you go through on that path. There are never alternative ways to get between keys that go through different sets of doors.

I implemented a recursive version that iterated over the set of next keys in order of distance. This quickly gave me an upper bound on the total number of steps but took forever to converge. To get a sense for how far off I was, I took my best answer so far (4816) and guessed a multiple of 100 that was lower (4700). Much to my surprise, this was the correct answer!

For part two, I had to come up with a real solution, though. I decided to use a breadth-first search and a heap to do something Dijkstra-ish: always continue exploring the shortest paths so far. That way as soon as you found a solution, you’d be guaranteed that it was optimal. This was an improvement but was still too slow. De-duping the set of possible paths helped, but the real trick was removing non-optimal paths through any given set of keys. This was wildly effective and got me a solution in ~2 minutes.

Bob said he memoized his recursive solution, which I think is equivalent to this de-duping.

Day 20: Donut Maze

problem / solution

This was a good one for NetworkX’s shortest path algorithms. Given the grid representation discussed above, this one was pretty straightforward. Even making the maze “recursive” just involved adding a z coordinate to the tuple.

Day 21: Springdroid Adventure

problem / solution

I found this one surprisingly hard. The restriction to two registers (T and J) and just 15 instructions is quite onerous. After some flailing, I eventually found a few organizing principles:

• You can split the problem into three cases: there’s a blank immediately in front of you (in which case you must jump), a blank two in front of you and a blank three in front of you. You always want to decide to jump, rather than not to jump.
• For each case, you can take all the examples in which you want to jump, OR them and simplify the resulting boolean expression.
• To implement a boolean expression in SpringScript, you need to get it in a form that starts with a NOT (since another case might have set the T register) and does not branch. I’m curious if there’s a name for this form.

I found it helpful to implement my logic in regular Python (with unit tests) and then convert to SpringScript and reduce the expressions bit by bit, ensuring that I never broke anything. Breaking the problem up this way helped me keep my sanity by preventing regressions.

Day 22: Slam Shuffle

problem / solution

This was perhaps my favorite of the problems. The trick is to realize that all the types of shuffles take the form y = ax + b (mod n). This lets you easily compose them and invert them. A property like associativity, which seems so simple when you write it in equation form, is pretty mind boggling when you think about it in a context like this one.

Fun fact: Python’s pow function optionally takes a third argument, a modulus. As of Python 3.8, the exponent can even be negative to find a value's multiplicative inverse for a given modulus:

> pow(2, 3, 7)
1  # 2 ** 3 % 7 == 1
> pow(2, -1, 7)
4
> 2 * 4 % 7
1

Day 25: Cryostasis (Christmas!)

After the challenges of the previous few days, Days 23 and 24 were comparably easy—a welcome relief! I was prepared for part two of Day 25 to be a real monster of a problem, but much to my surprise it was just a congratulations!

I had a great time doing Advent of Code this year and I’ll definitely do it again next year. I only started it on the 14th so I never escaped the sense that I was behind and needed to catch up. Next year I’ll start on December 1st!