Advento of code 2024
6 min read
The advent of code is a yearly event during which each day a new puzzle is served. Every puzzle is composed of two parts and every answer is a number or a series of numbers.
The beauty of this event is that anyone can challenge themselves the way they see fit. Some folks use it to practice DSA, others take it as a chance to try new technologies. Psychopaths compete on the ladder or optimize the solution to nanoseconds. There is some joy for anyone.
Last year I managed to answer up to day four, and I used the occasion to learn and fall in love with Golang. This year I got to day 17 using Rust. I will hold my opinions on rust, since I intend to use it a little longer. Today I would like to reflect on this experience.
I'm glad for the DSA throwback, it's one thing to study algorithms it's far different to be able to effectively use them to solve problems. The review included: BFS, DFS, Dijkstra and binary search.
Even if I would not consider myself a rust developer (sadly; missing a lot of status points) this couple of months give me enough confidence with the language. There is little doubt in my mind that I would be able to work on a rust project, if necessary. Having more tools under ones belt can't hurt.
Finally being able to share solutions and see how many different approaches could work is simply fun. My friends dropped earlier, but it was great to whiteboard together and discuss on possible solutions. I would like to give them a shout out for the effort and for indulging me. Here's the names: Gamberi Elia, Emiliano della Casa Gabriele Losi, Enrico Losi, Marco Buoninfante, Francesco Cuoghi.
Any line of code produced is under my git repo. You can find out more about the puzzles I liked (or cried on) by checking my blog or my youtube video.
Day 4: Ceres Search
This day we had to count the word xmas and samx (the revers). Here's an example:
MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
Here's valid matches.
....XXMAS.
.SAMXM....
......A...
.......S..
My struggle was due to the face that regex can't (well actually they can, I just wasn't aware) find sub matches. If I have a samxmas this is a double match. This can be solved by reversing the row and running it again (or getting better at regex). I then counted the rows, transposed the matrix, and run again. However this doesn't count the columns.
I also was not in the mood to write a parser, then my friend hit me a funny idea.
Just unroll the columns into rows.
Funny idea, it worked. Don't ask me how I implemented, linear algebra hurts my head.
Day 6: Guard Gallivant
A guard is patrolling the area. Each time the guard finds a wall (# symbol) it would turn right. Part one asked how many unique steps it took get out, which was trivial. Part two asked how many times it's possible to place a wall that would stuck the guard in a loop. The loop detection is trivial, if you walk on the same cell with the same direction, you are looping.
The idea is not hard: bruteforce by putting the wall on any empty space and run the algorithm a bunch of time. That however was slow, minutes level of slow. The situation called for optimization, and I did, but I jumped the shark.
I realized there is no need to test every single walkable cell, I can place one obstacle at a time and I already know the path of the guard. I also assumed that it's really not important if my guard starts at any point in the path, it will still be stuck in a loop. Wrong.
This silly mistake made my result of by one and it took some time before the realization.
Day 12: Garden Groups
This quiz provided you with a garden. Each letter is a plant. Any contingent plant of the same kind forms a plot.
AAAA
BBCD
BBCC
EEEC
Part 2 asked you to imagine fences around the plots, how many sides do we have? This problems sends shivers down my spine.
Idea number one was to count the change of the direction. This however fails any time there are adjacent fences.
(# is a fence and is only for clarity purpose)
######
#AAAA#
#A####
#AAAA#
######
Here it will under count.
Idea number two is to count the corners, and with a little tweaking it got very far! Unbeknownst to me a fatal and insidious bug was hiding. A bug that cost me hours.
###..
#A#..
#A#..
#A###
###A#
..#A#
..#A#
..###
See the central fence? If you eyeball it, those are two pieces. According to my code that is one piece... Clearly this approach is not working. Working on the fence is not the smart idea, I unintentionally got a hint from a neat animation of this problem.
The last and winning strategy is to count every possible side first by rows then by columns without using the fence.
Day 14: Restroom Redoubt
This is a controversial day. We have a bunch of robots that move around. The numbers on the cell describes how many robots are on that cell.
1.12.......
...........
1....3.....
......11.11
1.1........
.........1.
.......1...
Part two ask you to find out after how many iterations does the robots form a Christmas tree. I found it bizarre, but exiting. This is not about translating a text into code, some creativity is needed.
Indeed I read about a bunch of creative solutions: Chinese reminder theorem, image entropy and many more.
Mine was quiet simple, and I was shocked that nobody tried it. I figured if most robots make a figure, the should be touching each other. I ran a BFS at each iteration on every robot, if more than 50% are touching that must be a robot.
Well turns out some of them form a frame for the tree, I then decided to print the highest amount of contingent robots (which was 49% btw) and printed my funny mamma mia Christmas tree.
I used the trees as robots and the 🤌 as visited inside the BFS.
Day 16: Reindeer Maze
This can be summed up as maze solving. Any move costs one, every turn cost 1000.
##########
#..#....E#
#.##.#.#.#
#....#.#.#
#..#.#.#.#
#..#.#...#
#S.#.#...#
##########
S as in start and E as in stop. On principle this is quite simple. My brain somehow remembered the existence of Dijkstra. Even better a viewer of mine suggested me A* , which boils down to "biased dijkstra".
Turns out implementing A* is not trivial, took a couple of times but sure enough it got the me score of the best path. That worked fine on part one. Part two however asked every possible best path.
Took me a little thinking (a lot actually) to get a strategy which on reddit was referred to as "backtracking". Find the best possible path, save the partial score and check any neighbour node. If the node added to the partial result is equal to the best score, congrats you have a new best path. Ideally there would be one best path and some slight variations on that. I was dead wrong.
The correct result was 1024 and my output 576. Well damn, that's weird.
After a lot of pain an suffering I occurred to what I could consider cheating. I downloaded another result and outputted the solved maze to check for differences. Turns out my implementation of A* was formally wrong. You see the input is not a graph therefore there is one slight complication that costed me one week.
This little bastard.
##########
#...O...E#
#.##.#####
#..#.....#
##.#####.#
#S.......#
##########
You see if you approach the cell "O" from underneath the score in "O" is 3015. If you approach the "O" from the left the score is 4007. Too bad that coming from below the total score is 4019 while the total score from left is 4013. My naive ass did not took direction into account. This was a hard bug to find, relatively easy to fix.
Full of hope and angry happiness I run the code and got 985...Devastating. Turns out I had one giant bug in my backtracking: I was only checking the neighbours of the main path. This was close and yet far away.
Naturally I started putting any of them inside my queue. This way I won't loose the new nodes. One program latter the output is 985. Can't say I wasn't confused. There should've been some kind of effect.
Out of despair I also tried add any path that is less or equal than optimal, which skyrocketed my result to thousands. Unexpected but I can work with this clue. Turns out I forgot to add the partial result to my partial runs of A*.
That did it, happy and stressed I was out.
Conclusion
Unfortunately day 17 break me. To be clear I did not hate the puzzle, it is actually clever and a good challenge. However my term for AOC is January and I was sure to not make it in time. The other reason is the burnout had caught up. Too much rust and too much time. There are more interesting projects in my queue.
I don't regret takes this detour, but next year I will limit my self further. Advent of code stays in the 25 days of the event and no day later.