Advent of Code 2024¶

Advent of Code 2024

Every year, there are new challenges for programmers on Advent of Code. They are mostly hard stuff, but begin mostly beginner friendly. Each day has a part 2 which makes it harder to get all stars. Do not pressure yourself and have fun solving harder problems.

How to read my code¶

My code follows some ideas. First, I have a single main function inside of main.rs, which handles everything for this AoC year. You can run all days with cargo run/test -p adventofcode24 .. inside of Rust/ folder. Replace .. with the day you want to run e.g. 6 for day 6. The main function will take care to run all days in parallel and provide the results in a structured way, but the days themselves do not run in parallel.

Every day follows the same structure: it has a single day function which is public and returns a String with the results for part 1 and part 2. In the code, these are the entrypoints for you to look for code. See day1.rs as an example. Most times, I try to follow the rustacean way to code, so you will see more code in comparison to other solutions. If you want to look at the code, you should start with the part1 or part2 functions at the bottom of the day files and start from there your investigation. Do not try to understand the structs at the top of the file first. This will help you to understand what is going on and why the structs or functions are the way they are.

In most cases the code is not optimized or restructured after finishing, so there can be some ugly stuff in it. But mostly it should be readable for rustaceans or for people who want to become one. Sometimes I am trying to implement stuff from the std library by myself in context of an AoC day, so do not be too confused if you see more code than needed.

Day 1: Wrapper structures are good for separation of concerns¶

This was a pretty easy and straight forward solution. No hard things to think about. In my solution, I go the hard Rust parser way with FromStr trait, but it is a much cleaner implementation. I am using this approach for some AoC now. It helps a lot to split implementation details.

Also, you can find a good use case for wrapper structures in Rust. For each step in my implementation I am using a separate structure to make it cleaner to work with intermediate steps. I implemented UnsortedLocations, SortedLocations and SimilarityLocations. With this approach, you cannot call get_score for part 2 without the needed steps taken.

Day 2: Brute force can win too, sometimes¶

Okay. Part 1 was easy and not much to talk about. After some time (2 hours) part 2 was too. But after those 2 hours, I took a different approach from the first one and used the brute force approach. In those 2 hours, I tried to find the smart solution, but there is no such thing for me. The brute force approach is already fine for the sample set. After this lightbulb moment I got it done very quickly. Use your approach for part 1 and remove every element in your array and you are done. Not much to mention or learn from.

Day 3: No regex, more compiler stuff¶

This day was a little more typing work. On Reddit, there were some spoilers about regex. After reading the task, it came to my mind that the second part would do something that would break regex and my study of compilers came closer for my solution. A quick look into my notes and it became clearer. Now you can see a small lexer and parser (2 step compiler) in my solution. First I parse the text into Items, but do not throw an error on unwanted characters. This will help us later to parse the logic and run over the items and handle them appropriately.

Some typing work later, part 2 becomes an easy task, which would be much harder with regex. Both parts run in 647.7µs with release profile, so I am very happy with it. :)

For a much closer solution to normal compiler theory, I implemented a more native and basic lexer so the parser does not need a window on the iterator anymore. So this could be the starting point for a real compiler or interpreter. day3.rs Funny thing: it is mostly, but not exactly as fast as the windows solution, but more generic. The only ugly stuff is that I repeat myself and that do and don't are very similar, so they are sharing some code. But no magic needs to be done, except some else case handling. :)

Later the same day, after some scrolling around on Reddit: okay, regex also has a great and easy solution. But I am not here to do easy things. :) I had fun implementing a small interpreter again. Regex is also very easy, but stands on bright shoulders. So mostly it is an easier approach on the same idea. I am also happy not to be the only one who takes this approach.

Day 4: First hard day¶

Okay, now we are getting serious. This needed some more attention on my side. At the end, the logic is pretty simple, but my first approach was a little too biased toward window iterators, so I implemented it by myself for 2D vecs. But this ignored the fact that a single X can be the starting point for multiple words and that I count the same XMAS twice or more.

So I needed a new approach, which looks for X as the starting point. But with the iterator approach, I had a lot of work done already and so it was pretty easy to adjust to this. Same thing for part 2, because I took the same approach and looked for the A as the starting point. With a little pattern recognition (and code explosions), this is a pretty good solution, also for other use cases or input.

And I learned how to implement my own iterator and windows in Rust. So yeah, it is a win for me.

Day 5: HashMap and inverted logic to the rescue¶

Okay, this was the first one that is easy in part 1 and a lot harder in part 2. Until today, this year was pretty biased toward part 1 on my side. Part 1 was pretty straight forward and easy going; I inverted the provided logic from the task text with the help of a hashmap and so I can find the numbers in false order pretty fast. After some thought for part 2, skipping the first approach with swapping around the elements or using a power set, I found the approach to sort the vec with a pretty simple Ordering with the help of the hashmap created for part 1. And so it did not escalate like day 4.

The only thing I rushed today was the data struct, which is pretty ugly. But I used a wrapper struct for better usability, so I take it as a win.

Day 6: When your mass in code hinders you to achieve the goal¶

What a trip. I worked approximately 12 hours on this one. Not part 1, which was easy and pretty straight forward. Part 2 is easy to understand, but my code was optimized for part 1 and part 2 was incompatible with it, so it got messy and my debugging was very frustrating. But a sleep later, I got it fixed. Obviously you have to remember, when checking for loops, where the new obstacle was placed. And that it does not get placed on a field the guard visited already to come to the current position. These 2 conditions were violated by my code. The loop recognition is done via a hashset and a check if the current field can be saved as visited. If this cannot be done, you were there already and so it is a loop.

Day 7: A heart between mathematicians and computer scientists¶

My first approach was to implement a simple power set algorithm with calculating all bit variations and so I can figure out all operation combinations. And after this, calculate all results. This is the brute force stuff with a cool approach to generate the operator sets.

But the mathematician inside of me recognized pretty fast that there has to be a more skilled approach, so I took a sheet of paper and a pen and calculated a little bit. But I made a mistake and got a false result. After day 6 I looked for a quick win and went back to my first approach.

After getting it done, I thought a little bit and saw that every multiplication has to be a divisor, which needs to be at the right side of numbers. This seems to be the right solution, because if the divisor is not on the right side, it has to be a subtract operation. When no number is on the right side and the left value is not 0, it has to be not true.

And for part 2 it would be better to calculate directly the solutions instead of generating every combination. Maybe I will find the time to make this happen.

Day 8: A day for maintenance and frustration¶

Today was a simple day, but my first approach does not work as expected. So I sat there and tried to debug it for several hours. At last, I implemented the discrete way and this worked immediately. Sad, because my inner mathematician would like to write linear functions and no discrete loop stuff.

But okay, it is fast enough. And after finding an optimized solution for day 7, also this was satisfying.

Day 9: DRY and pattern matching¶

Okay, a second day in a row that is not very hard but fun to implement. In my implementation, I tried to reuse my structs from part 1 and use wrapper structs. On this day, you need to learn how to access an array without violating the borrow checker. But working on arrays with Rust feels a lot like C and the borrow checker is not so rigid as in other situations.

I am a little bit proud of my solution, maybe not the fastest one. But I think it is pretty straight forward and you can learn a lot about the pattern mechanics of Rust and see the if let whirlpool to swoosh. :)

Day 10: First pathfinding problem¶

As every year, there is a pathfinding problem. And on this day, I solved part 2 before part 1. This seems also a thing for most active redditors, because the memes were real. There is not much to do, except the lookup logic and finding the next steps. Part 1 wants to know how many niners you can reach from a specific starting point. Part 2 asks for the alternative routes. But part 2 is the basic approach for part 1. So in my solution, it is mostly a copy paste. Maybe I will DRY my code. But not today.

Day 11: Memoization and dynamic programming¶

Yep, like the day before, we need a classic approach to complete this task. First, I implemented the naive approach. The second part asks for the same but for more iterations. So, you need a memoization approach. Try not to calculate all stones every time. Instead count them up, because you know that every stone changes on blink. And the next iteration could show up numbers you already saw. So there have to be some loops. With the help of a table, you do not have to calculate such loops, only the unique ones. In fact, with memoization you group up all stones by their numbers and only unique ones have low numbers. All looping numbers count up quickly but do not need a lot of CPU work because they are grouped. The code is pretty straight forward and well structured. So this is a very good task to test your dynamic programming skills.

Day 12: Clustering¶

Okay, I am a big late to the party because I was on vacation. So I was happy to see that this task was a clustering one. It is heavy typing work, but not so much head work. So most time went into the cluster algorithm. At first, I create a hashmap to prepare the cluster finding algorithm. Now it assumes that all characters are a single cluster. With a simple neighbor check, a cluster becomes bigger if the neighbors have the same char. Because of Rust, I used the take and swap trick to not relocate around and satisfy the borrow checker. The algorithm is done if nothing changed anymore.

After this, we can do the dirty work to finish the task. The perimeter is pretty simple, because a field is on a side perimeter (it has a maximum of 4 sides) if a neighbor is not in the cluster. If it does not have any neighbor, it is on all 4 sides. Area is counting.

For part 2, you need the idea that any side equals the corners. How can you find the corners? Right, you look for diagonal neighbors, so you have an interior corner (L shaped one). Also you have to check if the current point is in the edge of such an L, so you are the corner itself: then it is an exterior corner. After you get this idea, it is pretty fast to implement on a grid or a list with the contains method.

Day 13: Math task¶

Today, I had no problems solving this task. First you need to understand that you have two unknown variables and two equations. So you can do homework like in school and find an equation to solve both variables. Next you need to parse the input (I do it the hard way). Part 1 was harder than part 2, because I had some small issues with my datatypes (division is different for float and integer). After fixing this, I solved both pretty quickly.

Day 14: Cheated day¶

Part 1 was pretty simple after recognizing that I have to use the Euclidean remainder. Part 2 was tricky, so I spoiled myself after an hour without an idea.

Day 15: A hell for typing errors¶

This day was the worst by far this year. I needed 3 complete rewrites for part 2 until I made no mistake with the first approach (I knew that it was the correct one, because it was BFS to find any obstacles in a path). Furthermore I do not know where my error was. The code was very similar. Maybe a little bit frustrated after a code loss from misusing git. Not so friendly as the last days.

Day 16: Dijkstra to the rescue¶

Yep, it is this day. We all know it would come. Pathfinding is here. Part 2 is a modified Dijkstra, so be aware to understand what Dijkstra really does. It needed some attempts to get it correct, but after figuring out that valid paths do not need to have the same distance, it was straight forward. Mostly typing work. You should know about Dijkstra and track the looking direction, because it will affect the next distance. Also be aware that you do not skip essential positions (offset by one).

I tried to make the code readable through functions and wrapper types. So functions are only usable after calling a specific other function, so you cannot misuse it.