Advent of Code 2021
Its about that time of year, Advent of Code is back! I'll be updating this post with my thoughts and any visualizations throughout the challenge. The full source for my solutions can be found in this git repo. I'm taking this year on using Rust, but I may have to switch to Python later if Rust is slowing me down too much.
Today was a good start! The problem was fairly standard and simple,
expected for the first day. Turns out I remember almost nothing
about how to use the Rust standard library and I had to lookup
how to get the length of a vector (its
Iterate over the list of provided numbers, keeping track of the previous (initialized to the MAX value), and increment a counter every time the current number is greater than the previous.
Convert the input lines into a vector, converting to integers along
the way. From 2 to the length of the vector, iterate while
keeping track of the previous sum, and increment a counter
the current window
v[i-2] + v[i-1] + v[i] is
greater than the previous.
This was another standard AOC problem, I think every year has several "grid movement from commands" types of problems.
Keep track of x position and depth. For each line of the input, split out the command and its value. Based on the command, increment/decrement the correct values. Multiply x and depth at the end.
Same as above but now up and down modify a new variable instead of depth, aim. Now, when moving forward, we update depth using aim and the current value. Multiply x and depth to get the answer.
Today was a grind. I could not shake the feeling that I was missing an obvious bit manipulation trick, but I eventually went on to using strings and vectors.
Loop over all of the numbers, keeping count of how which digit occurred more in each column. Go over the counts, and construct the bits back into two integers before multiplying them and returning the result.
The strategy here was iteratively remove numbers from the list until one was remaining. Each iteration would calculate the digit counts and then remove all rows that did not match the key so far. Do this for the first and second rule before multiplying them and returning.
Today was a mess. I am not experienced enough with parsing in Rust, and today's puzzle format amplified that. I also made the mistake of trying to mutate a struct/vec in a loop while using its iterator. This can't be done since it would require 2 mutable references to be alive at the same time. The easy solution is to fallback to a simple for loop that iterates an integer over the length of the array, then getting a mutable reference for each element on every iteration.
Parse out the draws and boards. Created a board struct with 2 methods. Iterate over the list of draws. For each draw, iterate over all boards. For each board, mark off (set to -1) the draw then check for Bingo. If there is a bingo, get the sum of all values that aren't -1 and multiply this sum by the draw number before returning.
Part 2Parse out the draws and boards. Created a board struct with 2 methods. Iterate over the list of draws. For each draw, iterate over all boards. For each board, mark off (set to -1) the draw then check for Bingo. If there is a bingo and there are other boards remaining, remove the board from the board list. If there is a bingo and this is the last board, return its score.
Today wasn't bad at all! Parsing the input was straightforward and the problem itself was fine. I had some hiccups with using HashMaps in Rust, but didn't have any issues once I refreshed my knowledge on them.
Parse out each line into a start and end point. For each pair,
skip if they are not on the same line. Then, iterate over the line
and add each point to a
count how many times we see the point. At the end, return
the number of values in the hashmap that have a count greater
Same as above except for non-linear points, connect them with a line of slope 1 or -1, which can be determined by looking at their difference.
This puzzle was one of my favorite types of AOC problems, where part2 is just part1 but scaled up. This usually involves some kind of exponential growth and greatly punishes the naive approach. I suspect there is a straight numerical solution (this whole thing screams rings), but I'll search for that later since my solution is more than fast enough.
I back-ported my solution for part 2 here, but I initially implemented the naive approach. Parse the list of input numbers into a vector. For 80 iterations, look at each element in the fish age list. If the current age is 0, set it back to 6 and add a fish to the end with age 8. Otherwise, decrement the current age. Return the length of this array.
Instead of keep a list of fish directly, I instead chose to keep
two lists, fish and new_fish. These vectors have length 7 and 9
respectively with the value representing the number of fish
at the age represented by the index. So if
fish = 12
that means there are 12 2-day old fish. Using this, I can
simply move over these vectors and "slide down" the groups of fish.
I keep 2 separate lists due to the different age resets: a new
fish starts at 8 and an old fish starts at 6. We perform the
same shuffle and add between these lists in each loop before
returning the sum of their sums.
These problems were fairly straightforward, but I messed myself up on some integer rounding. I picked up on some statistical values like median and mean being relevant, but didn't go with them on the first try. I ended up brute forcing both parts and getting my solutions before going back and optimizing my solution based on others posted online.
For every possible position, calculate the total cost and see if it is less than the minimum, saving if it is. Or, find the median and calculate the cost to it.
Same as above, except the cost function is the sum from 0 to x.
Or, recognize this as the gaussian function
and that the solution will be at either integer directly above
or below the mean.
This day was hard, and I actually had to finish it the next day which is never enjoyable. The first part is trivial, but the second is not so much. I was able to come up with a solution, but it was a grueling experience.
Parse the input into "uniques" and "outputs". Count the number of output strings with lengths 1,2,4, and 7.
The approach I used is far from the most efficient but was the only way I was able to logically step through the problem. Given the easy to find numbers from above, compare them and start to uniquely identify segments. The top is the segment present in 7 but not in 1. The middle is the segment present in 4 and all of the 5 length strings. Carry this on, comparing what segments using their size and previous segments until a full mapping is defined. Iterate over the outputs and convert them to digits using this mapping, then add the number they make to counter. Return the counter.
These problems were much better than yesterday's.
Parse the input into a grid. For each number in the grid, check if it is smaller than all of its neighbors. If so, it is a minimum. Track the indices of these minpoints. Return the amount of minpoints found.
For each minpoint, perform a breadth first search where 9s are not considered neighbors and return the size of the explored set. Collect these sizes into a (max) binary heap, then pull off and multiply the 3 biggest, returning their product.
I was unable to get to AOC on the day this problem came out, so I did it on Day 11, along with that day's problem. I enjoyed these two problems, and found that they were pretty easy to solve. With all of these bracket matching type questions, a stack is your best friend.
Initialize a stack, the provided point map, and a points counter. For each line, iterate over its characters. If one of the opening brackets is found, push its corresponding closing bracket onto the stack. Otherwise, pop the top of the stack and check if the current charcter matches the one on the top of the stack. If it doesn't, perform the point lookup and update the counter. At the end, return the total count.
Start with all of the above, except perform the counts per line. If the point total for a line is not 0, it was corrupted and we can skip it. Otherwise, the autocomplete_score will be the score calculated using the characters remaining on the stack. Create an autocomplete_score_map, and use that with the provided algorithm to calculate the autocomplete_score. Return the autocomplete_score over all lines.
This day was straightforward but enjoyable. The gotcha with these automata-type problems can be nasty, but this specific setup wasn't too bad.
Read the input into a grid. Create a step function that modifies the grid and returns the number of flashes. This function first increments everything in the grid by 1. Initialize the flash counter and a boolean to keep track of if a flash happened (default to true). While a flash has happened, set the flash boolean to false and loop over all of the cells and check for one > 9. If so, set it to 0 and increment all of its neighbors by 1 that are also not 0. Set the flash boolean to true and increment the flash counter by one. Return the flash count. In the main function, create another counter. Call the step function 100 times, adding each flash count to the total counter. Return this total count.
Do the same as above, but ignore the flash_count. Loop until all of the cells in the grid are 0, keeping track of how many iterations its takes. Return the number of iterations.
This was rough. It took me way too long to recognize that I should use DFS over BFS. In my implementation of DFS, I made the mistake of having top-level logic along with logic inside of the neighbors loop. This lead to me missing some edge cases in part 2 and wasting a lot of time on a simple mistake. Also, given that we are often revisiting nodes, a visited set is better replaced with a path vector. Removing from the set can remove items that are in the middle of the path, which is invalid and leads to infinite loops and hard to debug stack overflows.
Use the input to build a map from node to list of neighbors. Starting with the "start" node, perform dfs with an additional check for revisiting small rooms. Count the number of paths that lead to "end" and return this sum.
The same as above, except we introduce a boolean to keep track of whether or not we've used our one small room revisit. It starts as false, and is set to true when we revisit our first small room. On subsequent calls, when we revisit another small room, we return 0 and exit early if we've already used our revisit. Part 1 is the same as Part 2 where this boolean starts as true.
This problem was great! I enjoyed this one a lot and did not anticipate the direction of part 2. I didn't have any issues with today, which was much needed after yesterday.
Split the input into two big chunks using "\n\n". The first chunk
lays out all of the dots and the second contains the fold
instructions. Parse out the Points from the dots and
the folds. I used a Point2d struct to represent the (x,y) coords
and a Fold struct that holds the axis and line for each fold.
For the first fold, iterate over all of the dots. If the fold
is on the y axis, and the current dot's y value is greater than
the folding line, reflect the y value over the line. Otherwise,
return the dot unchanged. It the fold is on the x axis, do the
same but with the x values. Reflecting the value is as easy as
line - (v - line), thanks to the fixed folding
direction. To handle overlapping, I store the dots in a HashSet
instead of a Vec. This allows me to just return the length of
the set for the answer
These are my favorite kinds of solutions. Throw all of the above logic into a loop over all of the folds. After performing all of the folds, get the max x and y values from the dots. For each point on the grid they lay out, print out the empty string if there is no dot, or a # if there is a dot at that point. This will print out a grid that will draw out the 8 capital letters that make up the answer.
Today was a bit tricky, but went smoothly once I recognized how to get the answer for part 2. I figured this would be one of the problems where the naive approach in part 1 would not be feasible in part 2, but it took me a few minutes to figure out a faster solution.
Split out the input into the template and list of rules. Create a HashMap to keep a count of the characters. For 10 iterations, do the following. Get the 2 character windows over the current string. For each window, lookup its new value and insert it. Increment the count of the new character. After 10 iterations, get the maximum and minimum counts then return their difference.
Increasing the iterations to 40 here makes actually building
the list unfeasible. Instead, we will keep track of the count
of each pair of characters. Each iteration, save the current
state of the map and loop over all
of the known keys. Since the updates are supposed to happen
at the same time, we can't modify and read from the same
HashMap during the key loop. Get the count from the copied
HashMap and increment the counts for the new pairs by its values,
decrementing the value of the original pair.
AB -> C, and
count[AB] = 3, count[AC] = 0, count[CB] = 0, then
count[AB] = 0, count[AC] = 3, count[CB] = 3.
This builds the count of each pair, but does not account for or
encode their overlap. To remedy this, we also keep track of
character count. At the end of 40 iterations, we return in the
same fashion as part 1 using these individual counts.
Welp, the holidays happened and I didn't start this problem until early January. Looks like I'll be playing catch-up yet again. This problem was fairly straightforward, it is just shortest path with a larger graph in the second part. This is most easily accomplished with Dijkstra's algorithm. I had to actually use the min-heap optimization for part 1, which the Rust docs contain a great example for. This was fast enough to solve part 2 as well.
Parse the text into a grid of danger values. Run Dijkstra, return result.
Follow the rules to create the new 5x5 megagrid. Run Dijkstra, return result.
I am currently trying to build my habits back, which includes finishing up these problems. This problem was a bit of a pain, as it took me a bit to get the parsing right and once I did, I completely forgot that I was defaulting one of my return values to the empty string. It took an embarrassing amount of time to spot this, but I eventually got everything working. As is tradition with AoC, I was rewarded with building a full parser in the first part by making the solution to part two as easy as adding a method to my Packet struct.
I am going to trim out the specific part comments for the rest of these as I am trying to breeze through these problems and wrap up AoC 2021 by March 2022.
This day was fun, but challenging up front. I figured there would be both a brute force method and a mathematical solution, but neither one was clear. I took some time to think through the constraints of the problem, and slowly was able to build up my velocity nested loop bounds one by one. The maximum x speed is going to be the further x point away in the target area. Anything faster immediately fails after a single step. Almost identically, the minimum y speed is the minimum y value in the target area, since anything faster always misses regardless of x value. I first ran the program with a minimum x velocity of 0 and a maximum y velocity of 1000. This was clearly inefficient but worked, allowing we to get both solutions.
I further refined the loop bounds by recognizing that I could figure out the minimum x speed with some pre-computation: this speed is largest one whose Gaussian sum that is less than the minimum x value in the target. Every speed less than this falls short. Then, due to conservation of momentum I realized that the maximum y velocity is the absolute value of the minimum y value in the range. This works since all targets (that I have seen) are below y=0. After going up, the projectile comes back down and passes y=0 with its starting velocity but negated. And velocity greater than the furthest target point away immediately misses on the first tick.
While a bit of a grind, I enjoyed these problems.
This day took me way too long. From my Haskell experience, I immediately saw that a recursive data structure could represent the problem nicely, but that is usually not a good idea in Rust. I eventually realized that keeping track of values and depths would probably be enough to get it done. Throw in a busy week, some misreading of the problem, and few off-by-one errors and this problem goes from fun to painful in a flash. After solving, I looked at some other solutions and saw that my Haskell intuition was correct and lead to elegant answers. I also saw that this may have been a great situation for a struct-of-arrays instead of my usual array-of-structs approach. I'll try to keep this in mind going forward.
This problem stunk. I struggled understanding the question for a bit, and it took me even longer to realize that subtraction can be used to find when two sets of points are similar but offset from each other. I then spent a few hours trying to understand why my solution wasn't working only to realize that I simplify forgot to add an offset back in to a calculation. I did not enjoy this problem, and it makes me want to finish up and put AOC2021 behind me.
This problem wasn't too bad, and I actually found myself enjoying an AoC puzzle again. All of the fun stuff was here: parsing, 2D grid data, binary number creation, cellular automata, and a final solution that contains a cool visual. I got hung up by the weird infinite grid aspect, but sorted it out with an additional boolean. I predicted that part 2 would just be a scaling up of part 1, and I was correct. My solution averages around 1100ms to solve both parts, but I would like to speed it up more. If every day was like this, I would be enjoying this process much more.
This problem was enjoyable. I expected to be thrown off with some ring math again due to the clear modulo in the problem structure, but the problem did not go that way. Part 1 was easy enough, once I sorted out how to do modulo [1,n] (subtract 1 before the modulo and add 1 after). Part 2 was daunting at first, and the shear scale of possible games made recursion seem unfeasible. I looked to see if the Chinese Remainder Theorem could apply, but nothing of the sort popped out. I then realized that we only care about the result of the 3 rolls, not each roll individually. Since take the sum of these 3 rolls, we can greatly reduce the search space thanks to the repeated sums. There are 27 permutations with repeats for 1,2, and 3. However, there are only 7 unique sums from these 27. Instead of recursing for each of the 27 permutations, we can recurse for each of the 7 sums and multiply the result by the frequency of that sum. This worked first try, and I was proud to see this approach on my own. I'm sure there is a faster way to do this, and likely strip out some other branches too but I am not interested in that right now. I am hoping for more problems like this in the last 4.
Part 1 was great! Create some sets, do some adding and removing, then count up the result. With part 2, this won't work. I realized that I needed some way to either break apart cubes when intersected, or manage the intersections correctly so that I could add their volume for the answer at the end. I struggled with this for so long, trying both approaches. I could not get either one to work, so I had to cave and checkout someone's solution on Reddit to see what I was doing wrong. I was being a little naive about how I was building my list of intersections, and also missed a trick with the on value to correctly cancel out intersections. I had the majority of the code written, but had things a bit out of order. I did not enjoy this problem.
This day wasn't too bad. I was sure that I knew how to get the answer from the start using BFS, but I wasn't sure if this would work for the second part. I went ahead anyway, and luckily the second part did not increase the search space to the point that BFS was not feasible. The complexity here could be improved quite a bit using Dijkstra's or getting fancy with A*, but I'd rather finish the other problems first.
This day was horrible. This was easily the most difficult problem I have seen in AoC and could not get the solution on my own. I had to look at hints and solutions on the subreddit in order to finally solve this. I appreciate the spirit of these reverse engineering style questions, but picking out the pattern in this one was next to impossible for me. I used the method from this solution, and was able to actually implement it in code instead of doing it by hand. So while I completely failed this problem, I was still able to implement a general purpose solution which I understand has been difficult for many other people. At the time of writing (03/13/2022 oops), only ~12,000 people have completed both parts of this problem.
I am not against this style of problem, if anything my inability to solve it means I should be exposed to more problems like it. If there was a way to make a hint towards the solution and/or provide test data without spoiling the solution completely, it may have helped with the completion rate of this problem. I did not enjoy this experience, but at least I am now aware of a style of problem that I struggle with.
I enjoyed this problem. A nice, straightforward cellular automata iteration problem. My solution could be so much better, but it worked first try. I was aware of the tradition that the last star is given for free, so I didn't worry about having to adapt my solution for part 2.
This whole process did not go the way I wanted it to. I got busy with the holidays and completely lost discipline to work on this the way I should have; but I am happy to finally complete it. If I prepared ahead of time by doing old puzzles, I could have solved some of the early problems faster. This would have made it easier to fit into my schedule and the whole effort easier to stick to. If I try to do this again this year, I will definitely prepare in November. Although, I may just save the problems to do throughout the year and spend December on something else.