Advent of Code 2024 Week 2 Reflection

A day late, but still going strong. I really shouldn’t be doing this considering I have finals in two days, but I excuse myself for developing “problem solving skills.” And in fact, some of the concepts in scope for my finals popped up in some of the problems, so maybe it wasn’t all for nothing. I started taking notes after each day instead of trying to recall all questions at once, so expect each section to be much more concise.

Day 8: Resonant Collinearity

Reused some components from Day 6, adding some helper functions to increase productivity (by a lot). I also made use of some imports, which were also very helpful in turning high-level ideas into code. The implementation was straightforward using some vector manipulation techniques. This probably when I started noticing that sets are pretty useful data structures…

Time: ~ 40 min
Difficulty: 2/5

Day 9: Disk Fragmenter

Basically brute forced both parts, but I had to employ a fundamentally different data structure for Parts 1 and 2. Not the most ideal situation, but it was hard to expect what was coming out in Part 2, so I greedily optimized for Part 1 only. And then I misunderstood Part 2, costing me at least 30 minutes. In retrospect, I feel like finding the index of each file could have been much more efficient with the appropriate use of heaps or stacks, but I was too lazy to do some clever tricks at this point. The final solution runs in a reasonable amount of time, and for me, that’s that.

Time: ~ 1 hr 50 min
Difficulty: 3.5/5

Day 10: Hoof It

Somehow misunderstood Part 1 and solved Part 2??? Turns out I wasn’t the only one, according to reddit. As soon as I read the description, my mind was all into DP, which turned out to be what Part 2 was asking for. Part 1 was more of a typical DFS search problem. Unexpectedly, both parts were correct on the first try, which saved me a bunch of debugging time.

Time: ~ 35 min
Difficulty: 2.5/5

Day 11: Plutonian Pebbles

Beware of the short Part 2… It was alright for me, though. Part 1 was straightforward BFS, and Part 2 was an exponentially bigger problem, unable to brute-force with a naive search tree expansion. I used a quick and dirty memoization table to cache all previous results. Of course, this is not the optimal way to cache results, since I could have memoized all subproblems (stones after 1 blinking, 2 blinkings, etc…) for a given instance, but turns out my “suboptimal” strategy still gives a perfectly fast enough runtime. In fact, it was able to give 125 blinks a quick answer! The only quirk I had with this problem was after solving it on my own, realizing there was a @cache decorator in python which basically achieves what I implemented by hand, probably much better.

Time: ~ 30 min
Difficulty: 2/5

Day 12: Garden Groups

THE hardest question so far, by a large margin. Part 1 was a pretty solid example of a DFS “flood fill” type problem. The issue came in Part 2, where the implementation of finding the sides of a polygon involved a lot of edge case handling, which meant that debugging was more or less a given. In the end, my code turned out to be a rambling of functions to somehow patchwork and make my existing (broken) code work properly. For debugging, I had to backtrack a small 2D board by hand to figure out the very small detail I was missing. Unfortunately, only one out of five examples provided in the website actually triggered the bug, so I was confused for a good while. Still, tiring but satisfying to break the challenge by myself.

Time: ~ 2 hr
Difficulty: 4/5 (nasty bugs!)

Day 13: Claw Contraption

As soon as I saw the problem description, I knew I had to solve this problem with (I)LP. And I did. Just to visit reddit and find out that the 2x2 matrix could have simply been solved using the “Cramer’s Rule.” Oh well, but I would like to regard this as a good practice for my upcoming CS170 finals, which covers LP anyways. For Part 2, the package I used was somehow not robust enough (?) to find all ILP solutions, and there was no way I was going to fight with this random python package that really has nothing to do with my problem solving skills. So I just found a reddit solution what checks integrality by rounding and observing its difference with the original. Don’t regret it, wise use of my time.

Time: ~ 1 hr (time mostly spent on parsing & studying the scipy.optimize.milp package)
Difficulty: 2/5

Day 14: Restroom Redoubt

Extremely straightforward Part 1, and then perhaps the most un-straightforward Part 2? The easter egg reveal in Part 2 really fely like one, and after trying out some ideas for a while, I looked up reddit for some insights. Turns out the answer was quite a simple heuristic that I might have been able to guess if given enough time. However, I had a nasty off-by-one error in my output, which cost me some time. Seems like this got some undeserved hate in reddit, but I truly appreciate the problem designer for this one.

Time: ~ 50 min
Difficulty: 2/5

Day 15: Warehouse Woes

Vector operations from Day 8 coming back clutch and saves the day! This was probably the most amount of code I had to write for a single problem so far. The logic itself wasn’t too hard to grasp in principle, but implementing pushing boxes up and down in Part 2 involved some convoluted recursive condition checking. At first, I tried being sneaky and attempted to check for conditions and move the boxes at the same time, but I quickly realized that the effort wasn’t worth it and resorted to splitting up into two parts, one pure and the other nonpure. Fortunately, I had no critical bugs on my first implementation round such that I was able to reproduce the sample input fairly quickly. I went for modularizing each condition-checking phase and did some leap of faith that each function works as intended, which boosted my productivity a lot. Definitely needed some structure for a problem this involved, and it paid off nicely.

Time: ~ 1 hr 40 min
Difficulty: 3.5/5

Conclusion

Still learning a lot by solving problems. While these may not be challenging as Leetcode Hard (or even Medium) problems, the spirit of “anything’s allowed” really motivates me to think outside the box when devising approaches. The most absurd solution I saw was somebody on reddit compressing each board state into a .png file for Day 14 and observing ones with the smallest file sizes! Also, intended or not, this week’s batch of problems let me implement ideas I learned in CS170(Algorithms) in a concrete problem setting, which was very rewarding.

I’m probably taking some time off of Advent of Code until my finals are over on the 20th, which means the next post will most likely cover all of the remaining days (Day 16-25).