Advent of Code 2022
This is my first year trying the Advent of Code. I'll be keeping my journal here.
I'd heard about it on podcasts on the TWiT network for a few years now (specifically, Security Now), and I'd like to see for myself how hard the puzzles get toward the end.
I am writing my solutions in python 3 — usually just the minimum effort to get the answer, perhaps with some comments here and there. I am not looking for hints on reddit or anything, as the Advent of Code site suggests.
I've made my code available on GitHub. Obviously, THERE ARE SPOILERS ahead. Don't continue reading if you want to solve these puzzles yourself.
Completion
— a few weeks later ... —
As of the morning of January 16th, I've finished all the puzzles! I only needed hints from others for part 2 of day 11, for part 1 of day 20, and part 2 of day 21. For all the rest of them, I struggled my way to a solution. Since the Advent of Code website says all solutions are possible to achieve with running times of "less than 15 minutes on 10-year-old hardware," some of my solutions are obviously vastly suboptimal. A good example is day 17 part 2 (dropping a trillion rocks) which my script solved after running for about 4 days: by actually simulating all of the one trillion rocks!
For part 2 of day 17, I don't know why cycle detection didn't occur to me (since I used it for day 24). I guess I figured the positions of all the rocks would never repeat themselves, and certainly not at the exact point in the jets and rocks patterns. But I should have realized that the puzzle probably was set up intentionally to allow a cycle to be detected. After I finished all the puzzles I went back and implemented a better version of my day 17 part 2 script that runs in a bit less than 2 seconds. Oh well, it was fun to optimize (for python and pypy anyway) my script to drop over 3 million rocks per second.
I'm especially fond of my general solution to the day 22 part 2 puzzle (which I believe will work for any flattened cube shape), and my day 16 solutions, but most of the puzzles after day 11 were very rewarding to incrementally improve upon until the solution was found.
This type of challenge appeals to me quite a bit. The site and design of the puzzles was very impressive and very well done. I learned a number of things about python while doing these puzzles, and a few computer science concepts as well. It devoured most of my free time and thought cycles from early December to mid January, which is fine, but at this time I'd rather not commit myself to the idea of doing this again next year. Maybe after a few years off, when wanting to improve my skills with another programming language, I'll try the Advent of Code again.
Day 1: Calorie Counting
Trivial.
Day 2: Rock Paper Scissors
Trivial.
Day 3: Rucksack Reorganization
Trivial.
Day 4: Camp Cleanup
Trivial
Day 5: Supply Stacks
Ohh, a tad harder.
Day 6: Tuning Trouble
This was easier than expected.
Day 7: No Space Left On Device
This one was a bit more complex. The trickiest part was finally realizing the puzzle solution was looking for directories of size "at most 100000," not "at least 100000." So I've learned to read these specifications very closely.
Day 8: Treetop Tree House
Straightforward, a bit easier than the previous day.
Day 9: Rope Bridge
Seemed to be not any easier or harder than Day 8. For part 2, I thought we'd progress from one rope segment to two, not to 9! This was as fun one.
Day 10: Cathode-Ray Tube
This was fun to implement. Part 1 was pretty easy, and it very nicely set things up for part 2. For part 2, it was a bit odd how the display pixels and cycles were numbered with a 1-based system, while a zero-based system was actually needed to get the proper result.
Day 11: Monkey in the Middle
Part 1 was straightforward. Part 2, on the other hand, seems impossible at the moment. I must be missing something. We are squaring some values on each iteration, so the worry reduction step cannot be a subtraction, right? I wrote some code to brute force a bunch of tests. I don't like how the “puzzle” is worded. It's not clear. I can think of a zillion ways to reduce worry, and I don't like how I am doing "guess and check" to try to duplicate the example results. The worry reduction part should be more well-defined or bounded in some way.
After finishing all the other puzzles, I went back and tackled this one. I had just done LCM (least common multiple) stuff for the day 24 puzzle, so it occurred to me to incorporate that somehow with the divisors. The divisors are all primes, so I figured the LCM was just the product of all of them. I briefly looked at some discussion on reddit, and people mentioned modulo math... I figured it wasn't likely to work by just taking the modulo of the LCM of the divisors. But to my surprise, it worked!
I still don't like how part 2 of this puzzle is worded. In part 1, an arbitrary math operation (dividing by 3) is done to keep the "worry level" small. There's no indication in the puzzle text that some other similarly-arbitrary math operation will not work for part 2.
Day 12: Hill Climbing Algorithm
This was fun to solve. I used a simple recursive function. The input was large enough to exceed python's recursion depth limit, so I came up with a quick way to save function parameters/state out to a separate list and execute the recursion in smaller chunks.
Day 13: Distress Signal
This might have been the most challenging so far, but still not too bad. I had a little trouble with the "ran out of items to compare" situations but luckily I was able to spot my bug and finish both parts more quickly than expected.
Day 14: Regolith Reservoir
This was another fun one. I like these puzzles that are straightforward and produce some cool-looking output. Writing this out to the terminal as an animation would be fun.
Day 15: Beacon Exclusion Zone
This was fun to work on, and deceptively challenging due to the large search space. My first naive solution was straightforward to write, and I was able to easily replicate the example results. That example-solving code was keeping all coordinates in memory, so it wasn't viable for solving the full part 1 puzzle. But it was pretty easy to use what I'd written to solve part 1 after a little re-arranging. I thought I might have to expand the x-axis bounds a little beyond the sensors located at the extremes to find all the eliminated coordinates, and indeed that was necessary.
For part 2, I wrapped my part 1 solution in a loop. I started one instance of my initial, naive python code at y=0, going row-by-row up to y=4_000_000. It was taking forever, so I started a second instance of python at y=4_000_000 going backwards down to y=0. Those were still taking forever. I made my code a little bit more efficient by storing each sensor's beacon distance at instantiation time instead of calculating it whenever asked for. Then I started two more instances at the midpoint (y=2_000_000) where one progresses up toward y=3_000_000 and one down toward y=1_000_000. My back of the napkin math showed this would take 115 days to complete, assuming 10 seconds per row, with the search space split among 4 processor cores. I'd have a 50% chance to have a solution before 58 days have passed.
Obviously, a better algorithm was needed. Firstly, I could eliminate some sensors from consideration for a line: if they were too far away, they'd never eliminate any x-coordinates on that line. This change was quick to make. This change alone allowed my code to run at 2x or 3x the original speed, meaning would take around 10 days to complete if I split the search space up across 8 processor cores.
The final optimization was to find only the edges where each sensor's "diamond of elimination" touches each y-coordinate line. I could then eliminate all x-coordinates between those edges, without having to compute and check each one. To accomplish this, I wrote a class that handled integer range subtraction. All that was needed then was to print out whenever a line ended up without an empty range of candidate x-coordinates — and only one line did, with only one candidate x-coordinate. Yay.
Day 16: Proboscidea Volcanium
This one took me until the evening of the 19th to finish (for part 1) including in-the-shower epiphanies on two separate days, one of which led me down a wrong path. There were many false starts, wrong paths and rabbit holes, and re-writes.
I initially had a script that arrived at the correct answer for the example input after just a second of running time. Building on this idea to try to find a solution for the full input, I spent a lot of time working on heuristics to disqualify bad sequences early on (before lots of time was sunk into them).
The realization that the recursion should fork when the next (flow>0) target valve is selected, not when all possible neighbor valves are visited, finally put me on the right track.
The last stumbling block was my recursive function. I was trying to output the completed sequence as the function's return value. This would allow the function to compare its child function call results, and itself only return the best one. This approach would work fine for a smaller-scale problem, but I quickly ran into recursion depth problems again. Trying to track the return values when restarting the recursion function was not working. Eventually I gave up on that idea and used a simpler method of comparing completed sequences against a global "best sequence." This allows the recursive function to have no return value, so inferior sequences don't need to occupy any memory and can be eliminated as soon as possible.
For part 2, I was able to track the elephant's sequence, location, and target valve separately. The tricky part was forking the recursive function once for every human+elephant move pair. Some of the work I'd done following dead-end ideas for part 1 helped here.
I started running my script, which I think tested around 52,000 complete sequences per second. With a few testing things commented out, and other improvements, I restarted it running at 120,000 complete sequences per second. This seemed like it would still take a couple weeks of runtime to do an exhaustive search, but to my surprise, after only 9 hours it completed!
Day 17: Proboscidea Volcanium
Part 1 was simple, which I did with an object-oriented approach.
For part 2, where a trillion rocks are dropped, I refactored it to eliminate irrelevant rows that are blocked by previously-fallen rocks. That idea works fine, but the script was of course way too slow to be usable: at 100k rocks per second, it would take 115 days to run. After lots of incremental improvements, I got the script up to 170k rocks per second, which would take 68 days to run. I tried refactoring to use bitwise operations, and that turned out slower than the original. I also tried a refactor to get rid of the object-oriented approach, and again that was slower than my original approach.
I then tried running all these scripts using pypy instead of python and amazingly my fastest script runs at 1.9 million rocks per second! While more than 10 times as fast before, it would still take 6 days to drop a trillion rocks.
After a few more iterations, I found that the non-OOP approach was faster when run with pypy. The final script I ran for part 2 drops 3.2 million rocks per second. It does not instantiate an object for each rock, which provides the biggest speed increase. It also lowers each rock three steps before checking for previously-dropped rocks. At 3.2 million rocks per second, the time estimate is 3.6 days to completion. I think it took closer to 4 full days, since it was occasionally running a bit slow when I checked on it.
I suspect that using bitwise operations is even faster with pypy, but rather than work on that I let my solution just run in the background while working on other subsequent puzzles.
Day 18: Boiling Boulders
This was was pretty straightforward, and much easier than the previous two days.
For part 1, I used an integer representation of each cube position, which allowed me to populate them in a set and easily check all neighboring positions.
Part 2 involved adding a recursive algorithm to find a path to the exterior of the rock. I added another set of discovered positions on the "exterior" of the rock, and another set for the cache of visited positions. The tricky part was realizing I needed to run the algorithm multiple times until the number of discovered "exterior" positions stopped increasing.
Day 19: Not Enough Minerals
I designed my solution to pass the time while on an airplane of the holiday break. I was able to complete part 1 with a relatively straightforward "dynamic programming" approach. As I gather, this is just fancy terminology for my brute force recursive function, which checks for previously-visited states. This avoids re-computing the same states over and over again.
I was pleasantly surprised to find that python's namedtuple could be used as a dict key. I could then use a single namedtuple to represent all the state information, and easily check for previously-visited states with the in keyword. This allowed my script to be pretty concise.
For part 2, I ended up changing the main function to run iteratively, not recursively. The first attempt at a recursive solution, largely the same script from part 1, ran for about 18 hours or so before it was automatically killed (by my MacOS zsh shell) while processing the 2nd of 3 blueprints. I presume it was consuming a ton of memory.
The iterative function saves each reached "state" to the visited_states dictionary, and also to a states_to_try list, then returns. The function is then called again after pop()ing a saved state from the list. It runs in a breadth-first fashion, which allows the script to handle all sequences with say 30 minutes remaining, then eliminate all those visited states from the visited_states dictionary since no sequence with 30 minutes remaining will be visited again. Pruning memory like this is not possible with a depth-first recursive approach.
The script calculates a "theoretical maximum" number of geodes each sequence can reach once 7 or fewer minutes remain. (The maximum is assumed to involve creating geode robots as quickly as possible — the "7 or fewer" number was a first guess.) If a sequence can never reach the current "best" sequence's geode quantity, that sequence is terminated early. When the script ran it terminated a few hundred million sequences early based on this criteria.
In total, when run with pypy, the part 2 solution took about 15 hours to run. It spent most of the time processing 10,000 sequence steps per second or so, and occasionally spiked to a few hundred thousand per second and even well over a million sequence steps per second. I'm not sure why the running speed was so variable, but it ran fast enough. If the "theoretical maximum" calculations were started a minute or two earlier, the script would run much faster, I assume.
Day 20: Grove Positioning System
This one was relatively straightforward. I, again, originally worked out my doubly-linked list design while on an airplane. After I implemented the doubly-linked list, I could not figure out why my result for part 1 was not correct. To move each node, I proceeded along from node to node the correct number of hops. I looked at some discussion on reddit, and it dawned on me that what I had failed to realize was that I needed to not count the original node itself (when the number of moves was higher than the total length of the list). If I had simply first pulled the moving node out of the list, I would not have run into the issue.
Fresh with the "don't count the node itself" requirement in mind, I was able to quickly finish part 2 by moving the huge required number of moves but modulo list_length - 1.
Day 21: Monkey Math
For part 1, I used a tree-less approach with two dicts of monkeys: those with known values, and those with "unsolved" values. I repeatedly iterate through the "unsolved" monkeys, finding any that depend on two known values. I then moved these newly-solved monkeys out of the "unsolved" dictionary and into the known dictionary.
For part 2, I tried the same approach, guessing all incremental humn values starting from 1. I reset the known and unsolved dicts for each new humn guess. Using pypy, it was running at about 2,500 humn guesses per second. After trying over a million guesses without finding the solution, I still resisted implementing a proper tree solution. Instead, I track which monkeys did not change their value over the first 50,000 humn guesses, and moved those into the initial known values dict. Since most of the initially unknown monkey values did not change depending on the humn value, this increased the guessing speed from 2,500 guesses per second to over 15,000. This was still too slow.
After 100 million guesses with no solution, I implemented a proper tree of monkey operations and values. Resetting the humn value now involved only traversing that node's parents, recursively, and re-computing their values. Solving the root node was also a simple recursive procedure. This script ran much much faster at about 395,000 guesses per second.
After about 1.6 billion guesses, I realized I probably shouldn't be using the value -1 as a placeholder for tree node value-less left and right children, and I switched to using None instead.
Then I waited for my script to run... 2.7 billion guesses, no luck yet... 7 billion (when do I stop this? I'm starting to think I should just implement algebra to solve for the humn value)... stopping it after 10 billion guesses.
I figured the math operations are linear, right? So it might be possible to use a binary search. A brief peek at the discussion on reddit showed that yes, folks are using a binary search to find the value (it must be large!)
The code I wrote to quickly test a guess for the humn value was still useful. I first performed a bunch of guesses to find which of root's left/right-hand operands are constant over all humn guesses — if neither is constant, then a binary search probably can't be used. Then, I saved the boolean value for comparing root's left > right when humn is 1. Then, I doubled the guess until left > right no longer has the same boolean value as the original. Initially I stopped doubling once the guess exceeded a trillion. The humn vale was either higher than a trillion, or my code wasn't working. Since it worked on the example input, I set the doubling limit to 100 trillion, and (finally!) started to approach an answer.
I set the last doubled guess where the original left > right boolean held as the minimum guess, and the first doubled guess where left > right no longer held as the maximum guess. Then, I checked the halfway point between those min/max values, and repeat. Once the difference between the minimum and maximum was less than 100, I stopped.
I then tested all values from the minimum to the maximum with my old brute-force loop, and quickly found the answer. The script runtime is about a tenth of second, wow.
Day 22: Monkey Map
Part 1 was fun, and straightforward. I had to add a bunch of print() statements to debug my code, but it ran fine as originally intended.
Part 2 involves figuring out how my map (which is not shaped like the example) can fold into a cube.
After several days of brainstorming, drawings, and nearly giving up, I was finally able to get my solution working the evening of January 10th. The core of my solution is a pathfinding algorithm to rotate a simulated cube around on top of the flattened cube shape (the "board"). The algorithm finds a series of movements and rotations that re-aligns the cube face we are leaving to another valid position where this movement would re-enter a different cube face.
Whenever we are about to move across the edge of face of the cube, off the flattened shape, we need to figure out where to re-enter and at what orientation. I think of the paper/board being oriented as follows: left and right along the paper are in the negative and positive X directions, respectively, up and down along the paper are in the positive and negative Y directions, respectively, and away and toward the paper are positive and negative Z. To perform the rotation, I track two 3D "vectors" — one "normal" vector initially representing "up" with an (X, Y, Z) value of (0, 0, 1), and one vector representing the movement direction as we leave the cube face. For example, if moving up along the paper in the positive Y direction, this movement vector is initially (0, 1, 0).
For the vector rotation, I hand-wrote a dictionary used as a lookup table. I can look up the resulting vector for any vector (with one +1 or -1 value, and two 0 values for the X, Y, and Z), for a positive or negative rotation of 90 degrees around the X or Y axes. We never "spin" the imaginary cube around the Z axis, so those rotations aren't accounted for by the lookup table. For example, a vector pointing "up" in the positive Z direction, (0, 0, 1), when rotated +90 degrees around the Y axis, ends up facing to the right (1, 0, 0).
As the cube is rotated, to follow along the flattened shape, I update those two vectors according to the rotation lookup table. Then we simulate rotations of the cube, following along the flattened shape, and at every point, we try to rotate the cube "off" the flattened shape, which would place our original face floating next to the flattened shape. After we rotate the cube "off" the flattened shape, if the "normal" vector is again facing "up", and the movement vector is moving along the paper toward a cube face, we are done: we've found where the movement resumes and at which direction. If the original face is at the wrong orientation, we go back and try another sequence of rotations.
Day 23: Unstable Diffusion
Thankfully, parts 1 and 2 were faily easy to complete compared to some recent puzzles. I relied heavily on my new favorite feature of python: tuples as set entries and dict keys.
Day 24: Blizzard Basin
This was another one I had fun working on while on an airplane. I realized there must be some number of minutes P after which the basin resets all of its "blizzards"/"gusts" to their original positions, after which the basin state loops with a period of P minutes. Therefore the nodes are reachable/passable depending on the minute mod P.
Using this, I can calculate a set of minutes at which each position is passable.
A 3-dimensional graph can be built, where each node is a 3-tuple: (row, column, minute % P). Moving in any direction up/down/left/right from a position at minute m, if the neighbor position contains m + 1 % P in its passable minutes set, that neighbor at that minute is a connected node.
This 3D graph contains more than 873,000 nodes.
For my part 1 solution, I first tried a naive brute force search. I abandoned any sequence that was longer than the best known solution... and this was obviously running far too slowly. I think if I took the time dimension into account I could abandon sequences more often, but this would likely still be far too slow. I tried another heuristic involving a multiple of the remaining taxicab distance to the finish, and comparing that to the best known solution, and that was still running far too slowly.
Next, I tried the Floyd–Warshall pathfinding algorithm. It was fun to implement, and worked nicely for the example input, but requires memory usage on the order of (at least) 873,0002 bytes, and time usage on the order of 837,0003... so this algorithm cannot feasibly be used for this graph. I tried think of a way to split the graph into smaller subgraphs, but it didn't seem worth the effort to find a way to use it. While trying to implement this, I did realize that I could start from each "start adjacent" position and find the best path to every "end adjacent" position, which solved the complication of "waiting" at the true start positions.
Then, I tried Dijkstra's algorithm, which I had written in python for my day 16 solution. This immediately seemed like the right choice. My initial implementation was only visiting 40 nodes per second, which was far too slow. The bottleneck was finding the next node to visit — the "unvisited" node with the smallest known "tentative distance," for which it had to (initially) search over the full set of 873,000 nodes. By keeping a separate smaller dict of all visited nodes' neighbor nodes, the search space for the next node to visit was much smaller, and the algorithm ran vastly faster at over 50,000 visited nodes per second. After finding the best path from each "start adjacent" node to each "end adjacent" node, I could then add the required minutes to wait at the start, and one more minute at the end, to find the best overall solution. Running with pypy, my part 1 script's running time was a few minutes under one hour.
For part 2, I ran the above twice: once from start-end and once from end-start. By keeping all the best paths from each start-adjacent node to each end-adjacent node, and also from each end-adjacent node back to each start-adjacent node, I could brute-force string together every combination of those, with the required waiting times at the start and end, to find the best overall start-to-end-to-start-to-end solution.
I found that there are so many combinations of start-to-end and end-to-start paths that it's infeasible to test them all. If the number of start-to-end paths is S, and end-to-start is E, then the total number of combinations, I believe, is S x E x E x S x S x E. By abandoning inferior sequences before even completing them (that are slower than the fastest-known solution), this end stage of finding the best solution runs in a fraction of a second.
Overall, my part 2 solution still takes about 2 hours to run with pypy. I suspect there's a way to speed up the Dijkstra's portion of the script, by ignoring some unvisited positions, or by using the A* algorithm instead or something.
Day 25: Full of Hot Air
This last one seemed to be smaller in scope and more straightforward than I feared it would be. It was a bit of a challenge to wrap my head around to how to find the SNAFU-expressed version of the decimal value, but it was solvable much more quickly than recent days' puzzles.
Since the left-most, most-significant digit must be a 1 or 2, I could determine which it is. If the decimal value is less than (or equal to) the largest value starting with 1, which is 12222... then the first digit is a 1. Otherwise, it must be 2. From there we work on the next-most significant digit.
For example, say the first digit is a 1 and we are working on the 2nd-from-left digit. If the value is less than 12===..., then the 2nd-from-left digit cannot be a 2. If the value is less than 11===..., then the 2nd-from-left digit cannot be a 1, and so on. Continuing with this method, each digit from left to right can quickly be found.