README
¶
Advent of Code 2021
Index
-
Day 7: The Treachery of Whales - part 1, part 2
I enjoyed the second part of this exercise as I was able to use a simple minimization algorithm to bound and search the space. I divided the parameter space in half and then looked to see which half had a lower value.
-
Day 8: Seven Segment Search - part 1, part 2
This one was a great way to code up a set of deductions. I also ended up taking advantage of bit operations, representing each display as a byte.
-
Day 12: Passage Pathing - part 1, part 2
I love the path searching problems. This one is a fairly small set of states, so I used a recursive search and kept track of if I had revisited a small cave by changing the maximum allowed small cave visits as I called the recursive function.
-
Day 14: Extended Polymerization - part 1, part 2
I thought this one pretty straightforward, but I thought the trick was clever. The polymer itself is too long to track effectively, but each pair gives rise to two daugher pairs which share the same new central atom. By tracking the pairs it is possible to get sums for each atom pair in the polymer. I saw a lot of people counting this one strangely when they went to total up the atoms. Many people were summing all letters then dividing by two and accounting for each end. I thought it was much easier to count the first atom from each pair, knowing that the second atom is the first atom of some other pair. Then just add the last atom to the bunch.
-
Day 15: Chiton - part 1, part 2
This is another path search. Generally it is possible to do a breadth first search and not rely on algorithms like A* and Dijkstra, but I had never used Dijkstra before, so I decided to implement the algorithm and make use of Go's heap library. The toughest part of Go's heaps turns out to be figuring out when to use and not use pointers, but after you get the hang of them, they are pretty straightforward. They definitely speed up the implementation.
-
Day 16: Packet Decoder - part 1, part 2
I loved this problem. I used Go's big integer library to construct the bitfield and then just right shifted and masked the section of interest. I left the values as big integers just in case there were any gigantic numbers, but it was not necessary. I wrote a nice String method which printed the packets with levels of indentation to make them more easily readable as well.
-
Day 17: Trick Shot - part 1, part 2
This one sucked for me. I hard coded my solution initially and miscopied my lowest y value, so I was getting the wrong answer for a good hour before I thought to check my input. Don't hard code things! The second part was easy because I spent so much time on the first part.
-
Day 18: Snailfish - part 1, part 2
Another favorite. I first built a tree representation of each snailfish number, then I built a list with pointers to all number elements up to 4 levels and all pairs nested 4 levels. This allowed me to easily navigate left and right to do the explodes as well as search through to do the splits. I thought my solution was one of my most elegant of this advent.
-
Day 19: Beacon Scanner - part 1, part 2
This was some of my worst code. I found the rotations rather easily, but when it came time to find similar distances between two regions I ended up calculating metropolis distance, ordered element distances, and in the end I think I calculated too much. Better to just go through the rotations. In the end it does work though.
-
Day 21: Dirac Dice - part 1, part 2
I really liked this problem as well. I think I took a slightly different tack recording separately for each player the number of universes produced for each player state. The player state included the position on the board, the player's score, and the turn number. I calculated all states up to where the score first surpassed 21. Then I looked at all winning states (i.e. scores above 21) and multiplied them by the other player's losing (less than 21 score) states which had the appropriate number of turns. When looking at player 1's wins, I would look at losses from the previous player 2's turn. When looking at player 2's wins I would look at the losses from player 1's same turn. This complication in turns is because player 1 goes first.
-
Day 22: Reactor Reboot - part 1, part 2
I ended up doing a recursive solution of this. The idea is to move up the instructions from first to last. For each "on" instruction I added all the lights that were never turned on or off in subsequent instructions. For each intersecting subsequent instruction I would subtract off those positions which never intersect further instructions, and so on. It ended up being reasonably fast because there are only a limited number of overlapping instruction intersections.
-
Day 23: Amphipod - part 1, part 2
It took me a long time to figure out how to define the state of this problem, then I had an error which I couldn't find for a long time. It's interesting, but I did not have a good time doing it.
-
Day 24: Arithmetic Logic Unit - part 1, part 2, part 1 (slow), part 2 (slow)
I used a depth-first search keeping track of states I had already seen in order to solve this during Advent of Code, but a few days later I came back to this problem and worked out the pattern. Each digit was read with the same subroutine save for a few constants which were changed each time. The input was essentially being added onto a stack in register z with an added constant and some inputs were being popped off and compared to these values with the addition of a second constant. Once the pairings and constants are worked out the maximum and minimum solutions can be derived. This problem was a pain, and I needed help with the stack register idea.
Directories