Finishing the Advent of Code in the Summer
Last winter, I discovered Advent of Code and decided to give it a go. While participating in real-time was not an option given my calendar, I decided to work on it at my own pace.
The summer is approaching and I am glad to report that I made it all the way through. So I thought I would share my solutions, focusing on the final days to Christmas (link to my github repo).
What makes AoC particularly interesting is that some problems require you to look at the data. So in an sense, it feels a bit like a mixture of a coding and a data challenge.
Day 20
We are given a graph representing nodes in a state machine. Part 1 requires coding the graph and nodes correctly to determine the number of low pulses and high pulses that would be sent after pushing the button 1000 times.
Part 2 is about determining the number of runs required for a specific node to send a high-pulse. It would be tempting to brute-force it, but alas… the graph is designed to make this intractable.
We need to look at the data. Let’s visualize the state machine (FlipFlop’s in green and Conjunctions in red).
We notice that the graph has a structure (four clusters converging into the target node rx
). Since rx
is a conjunction, we want the minimum number of cycles for all of its inputs to send a high-pulse.
For each input (nodes pb, dj, rr and nl), we use our simulator to determine the minimum number of cycles needed for it to produce a high-pulse. We get pb=3847, dj=3797, rr=4051 and nl=3877.
Since these numbers are prime w.r.t each other (i.e. their gcd is 1), the solution is 3847 x 3797 x 4051 x 3877 = 229,414,480,926,893 runs.
And so yes, that was intractable through brute-force.
Day 21
We are given a 2D map of a land with garden spots and rocks. In Part 1, the goal is to determine the number of spots that can be visited after moving exactly n steps from the center of the map. That part is easy and requires coding an iterative loop properly.
Part 2 is a lot more interesting. The map repeats infinitely in all directions and the number of steps is a lot larger: 26,501,365. As we will see in a minute, this number is not arbitrary :)
There is a strong temptation to approach this problem from a purely algorithmic perspective and to try to solve the general case. However, looking at the data reveals an interesting pattern.
Interesting… there seem to be a square-like pattern in this map. If we try to move 64 steps from the center, we observe the following pattern (reachable spots in red — remember that we consider the spots reachable after exactly n steps, not at most n steps).
This pattern is definitely not random. If we generate a random input with the same rock density as the original map (12.17%), we get something like this.
The original map has the nice property that after 64 steps, we get a nice square pattern and after 65 steps exactly, we get to the edge of the map right in the middle of each edge.
This means that if we run 64 + 1 + 64 steps, we get to the center of the neighbor tiles and after 64 + 1 + 64 + 1 + 64 + 1 + 1 steps, we cover exactly 3 squares, and so on.
From this observation, we can devise the general rule that we cover an exact number of squares after K = n * 64 + n/2 * 3 + 1
steps. It turns out that the required number of steps 26,501,365
corresponds exactly to that number for n=404,601
which leads us to think that we are onto something :)
So all we need to do now is to devise the rule for the number of squares covered for a given n
. In the example above (196 steps), we observe that we cover 9 squares. However, not all squares have the same surface: 5 of them correspond to 65 steps and 4 of them correspond to an in-between between 64 steps and 65 steps.
More generally, for a given n, we end up covering n^2
squares, with n^2/2
of them covering 65 steps and n^2/2-1
covering 64 steps.
We can pre-compute the number of spots covered after 64 steps (that’s 3716) and after 65 steps (that’s 3797) which leads to the following formula:
surface = n^2/2 *3797 + (n^2/2-1) * 3716
We are almost there. If we do this, we get a remaining offset which we need to model. Computing the ground-truth solution for up to 589 steps (corresponding to 9 squares), I found the following formula:
surface = n^2/2 * 3797 + (n^2/2-1) * 3716 + (q * (q+1) / 2 — 1) * 80
where q = math.ceil(n/2)
which leads to a final answer of 616,583,483,179,597
reachable spots.
Day 22
This puzzle is about bricks stacking vertically in 3D space. You need to determine which bricks can be disintegrated without making other bricks fall.
This is what the test set looks like once the bricks have settled.
Part 2 asks for each brick, determine how many other bricks would fall if that brick were disintegrated. What is the sum of the number of other bricks that would fall?
I did not find anything particularly hard about this one. All you have to do is write proper iterative loops while keeping track of which bricks sits on top (or under) which other. Standard dictionaries do the job well. The puzzle answer is 79,042. Below is what the bricks look like on the full dataset once they have settled.
Day 23
We need to find our way through a 2D maze consisting of open spots and rocks. Some nodes have a steep slope can be traversed only in one direction.
In Part 1, we need to find the longest path between an entry point and an exit point. Taking into account the steep slopes, the average degree of the graph is 1.99 which means that the maze contains few decision points. We can therefore brute-force the problem by searching for all possible paths and keeping the longest one. We find a longest path of 2,294 steps.
Part 2 is more interesting. We can now go up the steep slopes, which creates way more possible paths in the maze. We need to determine the longest path in the maze without stepping on the same spot twice.
If we look at the maze, however, we notice that there are a limited number of decision points (intersections).
Therefore, we can transform the maze into a graph where vertices represent intersections in the maze and edges represent the paths between those intersections. Once we’ve done that, finding the longest path in the maze means is equivalent to finding the longest path in the graph.
This problem is NP-complete in general. If the map was a DAG, we could throw topological sorting + dynamic programming at it. Unfortunately, that is not the case here.
However, we notice that the complexity of the graph is limited since each vertex has at most 4 degrees (and often just 3). The graph has just 36 vertices and 60 edges. We could therefore implement an exhaustive search.
A lazier alternative is a random search implemented with one optimization (since we can’t step twice on the same spot, every time we traverse a vertex in the graph, we disable the paths leading to that vertex).
Running this approach on the input returns a longest path of 6,418 steps in about 3 minutes.
Day 24
In Part 1, we are given a bunch of 3D rays (“hails”) specified by their origin and a velocity vector. Our goal is to determine how many pairs of rays intersect in 2D within the boundaries of a test area. This can be achieved using standard 2D linear algebra.
Part 2 is more interesting. Given the same bunch of 3D rays, we must determine a new ray (the “rock”) that intersects with all the rays at an integer location.
If the rock has position and velocity p0
and v0
and the hailstones p[i]
and v[i]
, then we know thatp0 + t[i]*v0 == p[i] + t[i]*v[i]
for every i
, and so (p0 - p[i]) x (v0 - v[i]) == 0.
The problem is therefore over-specified: we only need 3 pairs of rays to get a 6x6 equations in p0
and v0.
These equations are not linear due to the p0 x v0
component, but we can marginalize it out with a bit of linear algebra, ending with a set of 6 linear equations which yields the solution for p0
and v0.
Day 25
We are giving an undirected graph of components. We need to find the three wires that need to be disconnected in order to divide the components into two separate groups.
There is probably an optimal approach based on a graph cut. However, I followed a different route based on the following intuition: the three wires that need to be disconnected are likely to be “bottlenecks” in the network, i.e. wires that are often traversed on a path between two random nodes.
I sampled a large number of random pairs of nodes. For each pair, I computed the shortest path between the end nodes and incremented a global counter for each edge traversed on the path. Finally, I picked the three edges with the highest counters.
Here are the pairs sorted by decreasing count for the toy dataset:
[(('bvb', 'cmg'), 1874), (('hfx', 'pzl'), 1797), (('lsr', 'pzl'), 1415), (('jqt', 'nvd'), 1092), (('nvd', 'pzl'), 843), (('cmg', 'rzs'), 760), (('cmg', 'lhk'), 754), (('cmg', 'qnr'), 746), (('pzl', 'rsh'), 690), (('hfx', 'rhn'), 640), (('frs', 'lsr'), 598), (('lhk', 'lsr'), 570), (('bvb', 'rhn'), 540), (('cmg', 'nvd'), 538), (('lsr', 'rzs'), 476), (('hfx', 'ntq'), 475), (('bvb', 'xhk'), 467), (('bvb', 'ntq'), 455), (('hfx', 'xhk'), 413), (('nvd', 'qnr'), 403), (('bvb', 'hfx'), 400), (('frs', 'qnr'), 378), (('jqt', 'rhn'), 368), (('frs', 'lhk'), 310), (('rsh', 'rzs'), 273), (('lhk', 'nvd'), 251), (('jqt', 'xhk'), 188), (('qnr', 'rzs'), 187), (('jqt', 'ntq'), 175), (('frs', 'rsh'), 168), (('lsr', 'rsh'), 120), (('ntq', 'xhk'), 114), (('rhn', 'xhk'), 84)]
This is promising as the first three are indeed the solution to the toy problem.
Running the code on the test set gave me the right answer, with two components of size 734 and 767, yielding to 734 * 767 = 562,978
There was not Part 2 on Day 25. I assume the organizer wanted the participant to unplug from their screen and spend time with their family instead :)