Project website: Advent of Code 2021.
Previous years: 2015, 2016, 2017, 2018. 2019. 2020.
I use Perl for all the solutions.
Most assume the input data is in a file called input.txt in the same
directory as the file.
Ratings
I’m giving each puzzle a subjective rating between 1 and 5. This is based on difficulty, “fiddliness” and how happy I am with my own solution.
A note on scoring
I score my problems to mark where I’ve finished a solution myself or given up and looked for hints. A score of 2 means I solved both the daily problems myself, a score of 1 means I looked up a hint for one of the problems, and a zero score means I didn’t solve any of the problems myself.
My goals for this year (in descending order of priority):
- get a total score of 40 or more (75%)
- solve all problems up until day 15 without any external input - not fulfilled
- solve all problems within 24 hours of release - not fulfilled
Final status: score of 46/50.
Day 1 - Day 2 - Day 3 - Day 4 - Day 5 - Day 6 - Day 7 - Day 8 - Day 9 - Day 10 - Day 11 - Day 12 - Day 13 - Day 14 - Day 15 - Day 16 - Day 17 - Day 18 - Day 19 - Day 20 - Day 21 - Day 22 - Day 23 - Day 24 - Day 25 - Day 31
Day 1 - Sonar Sweep
And we’re off!
I wonder if I got a bit too clever by half in this solution, as I’ve been looking over older solutions and can’t even remember solving them. But that’s how it goes I guess.
Puzzle rating: 3/5
Score: 2
Day 2 - Dive!
A “standard” Perlish solution (well, my kind of Perl, anyway): a dispatch table for the else/if “switch” construct, and a compact hash containing the state of the two solutions.
Puzzle rating: 3/5
Score: 2
Day 3 - Binary Diagnostic
I was honestly surprised that the canonical solution to this wasn’t some esoteric bit-twiddling trick that reduces it to a one-liner.
In part 2, the naive solution is to loop through each “column” to determine which values to count so as to determine whether they are most frequent or not. I used an index for each “set” to keep track of the values already assigned to that set.
Puzzle rating: 3/5
Score: 2
Day 4 - Giant Squid
Fairly straight-forward, although part 2 threw me for a loop. I didn’t find a good way to determine the exit condition.
Puzzle rating: 4/5
Score: 2
Day 5 - Hydrothermal Venture
Finally ok with my solution.
The first attempt got the job done, but was super-scruffy. I realized after I’d finished that I could treat the direction as unit vectors and work from there, so I re-wrote my solution, but only in as so far as to use the direction as a “selector” to chose which subroutine to call to “paint” the map.
After adding that to the repo, I finally remembered what I’d decided before the rewrite - to use the value of the vector in the paint routine itself.
Note that just using atan2 blindly to determine the direction will point the Y axis incorrectly. It’s probably only an issue if you’re printing the results, but I found that very helpful in debugging.
If anything good can be said about this method is that I eliminated a lot of weirdness along the way. It wasn’t all wasted effort.
Puzzle rating: 3/5
Score: 2
Day 6 - Lanternfish
I got off on a bad start with this puzzle, because it worked perfectly for the test input but failed for my puzzle input. I whinged about it on IRC, mentioning I had a very old fish (41 days!). Turns out that was a mispaste and fixing that gave me the correct solution.
I got the answer to the second part 40 seconds later.
Puzzle rating: 4/5, just because my solution was so smooooth
Score: 2
Day 7 - The Treachery of Whales
A quite fun one, and the first this year I managed to solve within 1hr of release. This might be TMI but I usually perform my morning ablutions and brew a pot of coffee before starting on a puzzle.
Thinking about this led me to try the average (mean) of the values as the natural solution, but that gave incorrect values. So I just checked the fuel consumption for each and every possible end point, selecting the minimum value. This went plenty fast, as did part 2 once I didn’t actually step through each distance calculating fuel as I went (hint: google “Gauss sum 100”).
When I had both solutions, I checked the various IRC chats and subreddits and discovered a raging debate on whether taking the median for part 1 and the average for part 2 always gave the correct result for every input. For me they did, so I just restricted by search space to the span of these values, plus a few extra integers for safety. This shaved a couple more milliseconds off the run time.
Puzzle rating: 4/5, I like grade school math
Score: 2
Day 8 - Seven Segment Search
Today was a tough one - not the problem, per se, but commitments that made it hard to me to get to a solution that I was happy with.
In the end I just went for brute-forcing every possible permutation, which is 7! or 5,040. The solution takes around 2s to run on my VPS.
Puzzle rating: 3/5, bit fiddly
Score: 2
Day 9 - Smoke Basin
This was a straight-forward problem.
I’m a bit surprised my BFS solution worked first time.
Puzzle rating: 3/5
Score: 2
Day 10 - Syntax Scoring
Not the most elegant solution but it gets the job done.
Puzzle rating: 3/5
Score: 2
Day 11 - Dumbo Octopus
Nice and easy, got 2 stars within one hour of downloading the input.
I don’t think my handling of some flags ($has_changed, $has_synced) is the most elegant. I’m pretty sure I’m doing an extra scan of the entire map every step to ensure everything has settled down. But I get a result within 1s (just) so let’s do some weekend chores instead.
I suspect tomorrow will be… more challenging.
Puzzle rating: 3/5
Score: 2
Day 12 - Passage Pathing
I had to look up a solution for this, which was kind of embarrasing for such an early problem.
Full credit in source.
Puzzle rating: 3/5
Score: 0
Day 13 - Transparent Origami
As usual, a breather after the weekend.
I was tearing my hair out, running spot checks on my code, before I realized I had coded my output incorrectly.
The rest of my issues was making it read the right way up…
“Best” result so far, around rank 6,500 for part 1…
Puzzle rating: 3/5
Score: 2
Day 14 - Extended Polymerization
Day 14 - complete solution Day 14 - part 1
A tough but fun problem.
Part 1 only for now.
Update 2021-12-15: finished both parts.
Puzzle rating: 4/5
Score: 2
Day 15 - Chiton
I think I finally figured out A*Dijkstra’s. With the help of a lot of cribbing from previous solutions (like 2018 day 22).
I’ve only included part 2 because I can’t be bothered bounding the box for part 1 so it doesn’t choose a cheaper solution outside those limits.
Puzzle rating: 4/5
Score: 2
Day 16 - Packet Decoder
Day 16 - complete solution Day 16 - part 1
Many people went “BERR” when they saw this: Binary Encoded Register Rodeo!
I had a lot of problems with this, mostly because I managed to get the correct solution for part one a bit by accident, which didn’t help solving part 2.
After a day of tearing my hair trying to pass data between recursion levels I managed to solve it.
Puzzle rating: 4/5 - tough, but fair
Score: 2
Day 17 - Trick Shot
Suspiciously easy.
This year’s last weekend is coming up.
Brace yourselves.
Puzzle rating: 3/5
Score: 2
Day 18 - Snailfish
Day 18 - complete solution Day 18 - testing
Completed 2021-12-31
Actually less complicated then at first glance. The main issue was figuring out how to implement the rules where “explode” had higher precedence than “split”, but I managed that with a stack.
Puzzle rating: 4/5
Score: 2
Day 19 - Beacon Scanner
Completed 2021-12-28
A fun problem. I found a list of all possible rotation transforms and used them to generate the set of rotations to try, then just compared each and every one to find offsets. Runtime is around 15s.
Puzzle rating: 4/5
Score: 2
Day 20 - Trench Map
Back on track after a tough weekend - which I had to skip due to travel.
This was a fun problem once you figured out the trick.
Puzzle rating: 4/5
Score: 2
Day 21 - Dirac Dice
A fun problem, but part 2 was too tough for me. I copped out and took a “free” star. Full credit in source!
Puzzle rating: 4/5
Score: 1
Day 22 - Reactor Reboot
Day 22 - part 1 Day 22 - part 2
Cubes - IN SPACE!!
I only had time for part 1 on release day.
Part 2 completed on 2021-01-04.
Puzzle rating: 4/5
Score: 2
Day 23 - Amphipod
Completed 2021-12-26
A fun problem but one I had to skip on release day due to preparations for Christmas.
We’ve seen this sort of thing before, I solved it using Dijkstra’s.
In general, we have a start state and an end state, and we can generate new states based on the given rules. These intermediate states can be seen as nodes in a graph we’re constructing on the fly. Applying the movement costs for each amphipod gives the total cost for moving form start to end, and Dijkstra’s algorithm gives the lowest cost.
Puzzle rating: 4/5
Score: 2
Day 24 - Arithmetic Logic Unit
I had to crib a solution (credit in source, of course) but I gave myself a point because it was Christmas Eve and that’s when we get presents here, damnit.
Puzzle rating: 4/5
Score: 1
Day 25 - Sea Cucumber
And… it’s a wrap.
Not the most elegant solution but it’s a star. I’ll take it.
Puzzle rating: 3/5
Score: 2 (assuming I fix the missing stars!)