This is part of a series of posts, starting with Advent of Code 2019 in 130 ms: introduction.

Day 6: Universal Orbit Map

Challenge 6 is about constructing and then traversing a tree. My solution runs in 260 μs.

Part one makes the tree directed and asks how many paths exist in it. A consequence of this is that each node has at most one edge pointing away from it. If there is an edge from node A to node B, we say that B is the parent of A. We therefore know that the number of paths from a node equals 1 plus the number of paths from its parent, or 0 if it has no parent, as shown in figure 1. This can be easily computed using a memoized function. The function takes a node as a parameter; the first time it is called with a given argument, it checks if the node has a parent. If it does, the function calls itself recursively with the parent as the argument, adds 1 to the result, stores the result in a cache and returns it. Subsequent calls with the same argument simply look up the result from the cache. The sum of these results for each node give us number of paths in O(N) time.

Figure 1: Example directed tree annotated with the number of paths from each node: 1 plus that of the parent node.

Part two asks for the length of the shortest path between two nodes. Again we can exploit the fact that the graph is a tree: we simply walk from each endpoint node toward the root, recording the number of steps taken to reach each node along each path. When one path encounters a node already visited by the other path, the solution is the sum of the step counts for each path to reach that node. In figure 2, this sum is 3 + (5 + 1) = 9.

Figure 2: Example directed tree annotated with the number of steps from two designated nodes.

Day 7: Amplification Circuit

Day 7 has you run several Intcode engines in parallel and find the arrangement that produces the greatest output. My solution does nothing fancy, just a plain brute-force search through all permutations of computers, and still finishes in 1.1 ms. Without reverse-engineering the given Intcode program, which I deliberately choose not to, there’s not much else you can do either.

Day 8: Space Image Format

Challenge 8 is also fairly straightforward data processing. My solution is again just a bunch of standard for loops, and finishes in 340 μs by simply being a Rust program.

Day 9: Sensor Boost

Day 9 introduces the final upgrades to the Intcode engine, and simply asks you to run an Intcode program that uses the new features. My solution is just a call to my Intcode engine, and its runtime of 4.9 ms depends entirely on the performance of the Intcode engine. Now that the Intcode engine is feature complete, I’ll discuss performance optimization for it in the next post.

Day 10: Monitoring Station

Challenge 10 is about lines of sight in a lattice of points. My solution runs in 13 ms and relies on partitioning the lattice by rays emanating from the origin.

Part one asks which asteroid is the best place for a monitoring station, where “best” means it can detect the largest number of asteroids:

A monitoring station can detect any asteroid to which it has direct line of sight - that is, there cannot be another asteroid exactly between them. This line of sight can be at any angle, not just lines aligned to the grid or diagonally.

This rule means that if we’re looking out from the origin (0, 0), two asteroids are on the same line of sight - and one will obscure the other - if and only if their positions (x, y) satisfy the equation (x1, y1) = (k * x2, k * y2) for some k > 0. An important consequence is that we can define a canonical representation C(x, y) = (x / gcd(x, y), y / gcd(x, y)) for all points on a line. For any two points on a line, C(x1, y1) = C(x2, y2) since gcd(k * x, k * y) = k * gcd(x, y). This means that we don’t need to compare each pair of asteroids to determine whether one obscures the other - all we need to do is compute C(x, y) for each asteroid location and count the number of different results we get. This count will be the number of asteroids that can be detected from the origin.

So in order to compute the same count for a would-be monitoring station at any point (x0, y0), we can translate the plane so that the new monitoring station would be at the origin. This means that we now partition the asteroids by C(x - x0, y - y0) instead of C(x, y). So for each asteroid (x0, y0), we construct a hash set containing C(x - x0, y - y0) for each other asteroid. The best asteroid will be the one that generates the largest-sized hash set.

Part two asks which will be the 200th asteroid obliterated by a laser that sweeps clockwise around the monitoring station. For this we need to keep track of all the original asteroid positions, not just which line they’re on, but we’ve done most of the work already. Instead of building a hash set of lines, we build a hash map mapping each line canonical C(x - x0, y - y0) to a vector of the positions (x - x0, y - y0) of asteroids on that line, then sort each vector by ascending distance from the origin. Finally, we transform the hash map into a vector of pairs, and sort this vector by the angle between the y axis and the line’s canonical point. This gives us a vector of vectors of asteroids, sorted on the first level in the order the laser will sweep over them, and sorted on the second level by the order the laser will vaporize them. Now we can simply delete one asteroid at a time from each line in turn until we delete the 200th one. In fact, we can get a little bit of extra performance by sorting the second level by descending order from the origin and deleting asteroids from the back instead, since vectors have O(1) element deletion from the back but O(N) element deletion from the front.