Advent of Code is an annual event where participants solve daily programming puzzles, each released in the form of a two-part challenge. The challenges cover various topics, and participants often use the opportunity to sharpen their problem-solving and coding skills.
I was aiming to:
- utilize my knowledge of algorithms and data structures;
- make solutions as general as I could;
- prioritize code readability over how fast I can write the solution — I didn't try to compete on global leaderboard.
In part 2 my idea was to iterate solely over differences of adjacent levels in reports, and look for anomalies. In case of an anomaly is found, we should remove some level, and simply reuse solution from part 1 on the new report. In general, when we encounter an anomaly, it consists of one or two diffs, and therefore at most three levels might contribute to it. I simply tro to remove each level, and if any of the resulting reports is safe, then we found a level that is safe to remove.
We can do it, because we can't skip an anomaly once we found it. If we wouldn't fix it, we'd have an unsafe report in the beginning.
Solution runs in O(N) time of input data, and in the worst case processes all the input 4 times. The worst case is an
anomaly in the beginning that can be fixed by removing 3rd level in the corresponding report.
Part 1 was about verifying if the slice is topologically sorted, and part 2 was about topologically sorting a given slice. Seems that the graph constructed in such a way that this sorting is unique.
I liked the fact that we need to return a middle element of a slice :) Because DFS returns topological sorting in reverse order, and we didn't need to reverse the slice to answer the question.
That's literally the first time when I implemented go1.23's iterators! And I like the result that I could separate iteration from business logic.
Trick to concatenate numbers using arithmetic operations is quite easy, but nevertheless is nice!
And despite it being on the surface, I like how I engineered the code to accept operations. It helped me to avoid code duplication, and, to be fair to double-check implementation. Because initially I guessed argument order, but I had to be mindful about it after I extracted operations into separate functions.
I used BFS to find all boxes that robot would push. Then I moved them one by one, from the most far to the nearest layer.
First part can be solved by BFS, but I used Dijkstra's algorithm for both parts, because I started modifying my solution to make it solve both parts.
To account for turns I represent map in 3D, where 3rd dimension is direction of a reindeer.
To find all shortest paths, for each visited tile I store list of previous tiles that lead to the current tile with the same score. It was a nice addition to Dijkstra's algorithm that I've never thought of before!
I wholeheartedly enjoy puzzles where you need to craft some sort of interpreter or virtual machine! I saw some design challenges and want to explore more about the VM architecture. For example, the most obvious flaw to me is that in my code I have too tight coupling between the VM itself and the instruction set.
Part 2 was the most difficult for me so far. I did spot the pattern that the program has a cycle until register A equals to 0, and did spot that we divide A by three every iteration. Unfortunately, it was not enough for me to draw any conclusions. So I had to resort to Reddit for hints, and the most groundbreaking one for me was that we should build the value for A by comparing the suffix of the program, instead of the prefix.
I wish I saw part 1 as dynamic programming problem from the beginning! This way part 1 was more difficult for me compared to part 2.
It was a fiasco in terms of how much time I spent on it. I didn't pay enough attention to the fact that there is only a single path from start to end, and I was expecting some tricky teleport to the other side of the finish line which would follow the way that did not belong to the non-cheating path. I also thought that you can travel through two walls in the part 1.
The idea of always jumping closer to the finish was always with me, but I couldn't persuade myself that it'll work. Apparently, it did work, and it's clear how dramatically simpler my code for part 2 looks compared to part 1. I guess, I want to leave it as is just to illustrate my thought process, and how it lead me to a dead end.
Today I learned about algorithm for enumerating maximal cliques! I did know about the term clique (although, forgot the term itself, and worded it as fully-connected subgraph), but I've never looked up how those cliques can be found.
And, actually, I've never heard about LAN-parties before as well.
I like the joke in this day's problem, which is about brute-forcing the solution for the literal brute force :)