Day 6: Universal Orbit Map
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.
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.
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
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
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
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)
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
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)
So for each asteroid
(x0, y0), we construct a hash set
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.