Advent of Code 2024 Week 1 Reflection

I decided to take on this year’s Advent of Code for a personal challenge. While I might miss out on a few down the road due to final exam season, I will try to be consistent as possible. My solutions can be found here.

The language of choice was Python3, as I am most comfortable with it (and can sometimes do really hacky things to speed up the coding). I could have been ambitious to practice more low-level languages like C, Go, or Rust, but I concluded that my first try should be as less painstacking as possible or I might lose interest in the first place. For the sake of not spending too much time, I set my standards not on making the best classes and frameworks for each question, but rather a function-based top-down approach, where I declare all functions needed to solve the problem first, then go onto the main body to utilize the functions. Also, optimizing the code for performance wasn’t a big consideration, unless the question actually forced me to think about cutting corners in terms of runtime.

These posts will mainly be about reflecting on my coding practices and decision-making procedures, before I forget what I actually did during the coding sessions. Not all of the comments are going to be exactly coherent, but here it goes.

Day 1: Historian Hysteria

Really nothing much to comment here, since there were no room for optimization nor was there an obvious need for it. Implementing the feature word-by-word was sufficient.

• Time: ~ 10 min
• Difficulty: 1/5

Day 2: Red-Nosed Reports

Deceptively challenging. Part 1 was a breeze since a single pass was enough to fully determine both the increasing/decreasing status from the first two elements, and things are easy from there. However, Part 2 did not allow a naive solution. Eventually, I had to come up with a way to circumvent the fact that the first two elements could be misleading if one of them were supposed to be removed, and I am pretty happy about how I did it. It extensively exploited the fact that only one element could be removed, and tested from both sides. If the first two elements were the problem, they would be the last two elements on the reversed list, and the new first two elements can be tested safely. I acknowledge that my code wasn’t the most handsome-looking since there were considerable repetition for the checkIncreasing and checkDecreasing functions, but I felt that it wasn’t worth trying to abstract it beyond this point.

• Time: ~ 40 min
• Difficulty: 2.5/5

Day 3: Mull It Over

Remember that I mentioned Python can sometimes to hacky stuff? This was one of them. The hardest part of this problem wasn’t algorithm implementation but me struggling with regex, trying to get it work with all of the escape sequences. Once I cleanly parsed all of the relevant strings, I simply called eval() on each of the multiplications, and that was that. Part 2 was barely an overhead, too.

• Time: ~ 25 min (Fighting with regex probably took like 15)
• Difficulty: 1.5/5

Day 4: Ceres Search

This question folded up nicely because the structure I built on Part 1 was also perfect for Part 2. Maybe lucky, maybe skill. There were some overhead in hard-coding the direction vectors for both parts, but it wasn’t too much of a hassle compared to the satisfying solution I ended up with. The question looked quite complicated, but my initial structure of checkIndex->checkDirection was strong enough to declutter most of the difficulty. Moral of the story: just the right amount of abstraction is the best.

• Time: ~ 25 min
• Difficulty: 2/5

Day 5: Print Queue

Around this point, I was thinking about whether the data structures or algorithms I learned in school might be useful. And at first glance, this problem looked like a DAG structural problem, with the page numbers as vertices and each left-right page rule as edges. But turns out, that was way too much thinking. Part 1 was solved easier than I expected, without the use of any sophisticated CS knowledge. Then, Part 2 was when my studying shined. It wasn’t exactly an implementation of a specific algorithm, but I noticed that after traversing the entire ruleset and swapping and inconsistencies, the number of inconsistencies must decrease by at least one, inspired by the local search method and properties of DAG I learned in CS188(Intro to AI). Thus, the number of traversals of an inconsistent page list could be bounded by the number of total rules. This made computation much more managable, and I fearlessly looped entire traversal without worrying about runtime or infinite loops. A satisfying moment, to say the least.

• Time: ~ 20 min
• Difficulty: 2/5

Day 6: Guard Gallivant

Now we are getting into the deep forests more and more, where brute force methods might or might not be the best answer. Complexity of the system was obviously much greater than anything I had encountered before, since the state space was in 2-D instead of a 1-D array. This meant some clever tricks needed to be employed, if I don’t want >10 minutes of just running the python script. I had to declare a lot more functions than before, since there were significantly more moving parts of the problem, such as keeping track whether the guard is out of bounds or dealing with change of direction. Nonetheless, I managed to write up a fairly compact mechanism for updating the guard in each timestep, with some ideas inspired by linear algebra and physics (hence, the variable names position and velocity). Critisisms are welcome for the messy notation of accessing the board elements, though. At second glace, I could have just made getter/setter functions for the board to mimic OOP a little bit. Part 2 was a bit of pain, as I missed out on the edge case when two or more consecutive turns are needed for the correct behavior. Was it intentional that Part 1 didn’t have any of these? Maybe. Also, I realized half-way through that the only tiles that are relevant to Part 2 were exactly the set of tiles I have colored in Part 1, which greatly improved the runtime, not exactly asymtotically but heuristically a lot.

• Time: ~ 1 hr 10 min (Debugging though…)
• Difficulty: 3/5

Day 7: Bridge Repair

Ok, I have to admit that I made a pretty stupid mistake on my first run. Implementing the tree search recursion itself wasn’t too hard, and I managed to pass Part 1 on the first try. The real trouble was in Part 2, where I knew the “hard” recursion step wasn’t what’s broken but still not getting the correct answer. Eventually, I gave up and debugged by comparing the outputs of a correct answer from Reddit. Again, feel free to criticize for “cheating”, but I am not trying to challenge the leaderboard at any rate, and me getting to enjoy the process was more important that adhering to strict morals when all I am trying to do is a personal challenge. Ultimately, the incorrect part was a simple fix of enforcing the list to be empty when there is a match between the calculated number and the goal number, a minor oversight that cost me more than half an hour. What was truly interesting was that I managed to pass Part 1 again without accouting for the obviously incorrect treatment of edge cases that caused an issue in Part 2. Now I am truly beginning to suspect that the creator of the problems intended some incorrect implementations to pass Part 1 but not Part 2. Frankly, this was annoying and deeply motivating at the same time. I will definitely try not to make these mistakes going forward.

• Time: ~ 1 hr 20 min
• Difficulty: 2/5 not counting the bug, 3/5 in reality

Conclusion

Even though I am a firm believer that doing is superior over seeing for studying, it was always difficult to just stand up and start tackling some coding problems. But the mere fact that I am working with other people on the same problem at the same time (even if there are no explicit interactions) enabled me to thoroughly enjoy the Advent of Code experience up until now. I expect the problems to increase in difficulty much more on the following weeks, and I can’t say for certain that I will be able to keep up with the pace, especially since Finals are coming up. Regardless, I hope I will be writing my second AoC post next week.