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.