Advent of Code 2023 using Rust
It’s time for this year’s Advent of Code!
Anyway, here I am, doing another year’s Advent of Code. You can find the code at wtchangdm/advent-of-code-2023 with a few things in mind:
It’s probably not idiomatic and efficient enough at this point.
Doesn’t include intensive error handling since the provided inputs are guarenteed to have certain patterns.
(The following content will be updated irregularly)
|🎄 Advent of Code
|🦀 “The Code”
The beginning of this journey should be relatively easy. However, I still managed to overcomplicate things for a while.
Consider the example:
You only need to find the first and last “digit” (as in, number) and concatenate them and parse as a valid number. If there is only a number per line, simply use it twice. I was wondering should I consider alphabets with ASCII code. And no, you shouldn’t.
The input now contains numbers in the form of words. I was about to replace all the way out but then I found a problem. Say,
"xtwone3four", which should be
"x2134" after transformed.
However, it comes with a order problem – if you replace
1 first, it becomes
"xtw134" instead of
So, instead of replacing it, iterate over the line and append the number when you see one, otherwise, check whether the position is the start of words like
The example below shows you can just split by
"; " and
" " to get game ID and the data of each round of the game.
And just check whether whethe every rounds of a game is under the limit of colors then sum the IDs.
Example is the same as above. Basically, a game wouldn’t be possible if there aren’t as many cubes of certain color as they once showed up. For example, we saw
6 red cubes and
4 red cubes in different rounds of Game 1. It’s imsspoble that there are only less than
6 red cubes.
For every game, gather the max number of each color and the multiply them together. Finally, calculate the sum of each game.
I definitely felt my iterator game is not very strong at this moment.
Anyway, my way to solve part 1 this day is just capture digits and then check their adjacent symbols along the way. The implementation is not very optimal because some neighbors will be repeatedly visited.
My attempt to solve this part is to group parts by adjacent symbols that are not
".". The final data structure will look like:
We actually don’t need symbols other than
"*" here if verification is not needed. Feel free to ignore them while grouping the engine parts.
Finally, we can just iterate over the HashMap under symbol
"*" and then filter out vectors which length is less than
2 (since we have to multiply them together). Adding results of each
"*" coordinate up you will get the final answer.
Today’s question starts with similar parsing from day2. Just don’t forget to trim the spaces between
"Card" and its ID because there will be some paddings from larger numbers.
Lastly, if we matched at least one number per card, calculate the number as
2^(num - 1) then sum them together.
I think there are probably way more efficient solutions, but I just used maps and a queue to caculate the times each card showed up and push the cards it won back to the queue. Finally, consume the queue until it becomes empty then sum the count values up. This feels slow but rather intuitive.
Update: After looking into how other people did it, I revised my solution a little bit. Pushing every card id into a queue is certainly intuitive but the performance is undoubtedly bad.
Instead of plussing one by one each time, we can take another approach. Since the cards are already sorted by its IDs, we can iterate through the cards with the following method:
First create a HashMap to track how many times each card has showed up before.
We will start at
Card 1— let’s add
Card 1to the map because… we do have one.
Card 1has won
4additional cards — which Ids are the
Card 1, so we have
Since we are done with
Card 1, it’s impossible for us to get any more
Card 1afterwards. Therefore, we can just safely add the count of
Card 1to its next
4Cards. Even though we haven’t started to work with these cards, we know we will at least get these additional cards at this point.
The map after finishing
Card 1 will look like:
- Let’s move on with
Card 2, We will add
1to the number to
Card 2. With the additional card from
Card 1before, we have
Card 2now. Since we are also done with
Card 2, it’s impossible for us to get any more
Card 2afterwards. And we know each
Card 2will win
2additional cards, which are
Card 4. So, we can just add the number of
The map after finishing
Card 2 will look like:
With the idea, the map will have the final answer once we have iterated through all cards.
I tried to sort the all of the resources by its starting endpoints. For example, consider the following
After tidying up, it will look like:
and we will continuously loop though this array and see if the specified ID (say, seed ID) is included in the corresponding maps (and break the loop of such resource). If the ID can’t be found, we will just carry the ID to next resource (i.e., soil ID).
This way saves the need of expanding every IDs in each map.
This is the part I struggled the most for now – even though I managed to skip the expansion process of the resource maps, I haven’t found the way to skip for the initial seed IDs. Therefore I just put rayon and moved on…after struggling hours after hours (I am sorry polar bears).
There must be a much more clever way but I guess this is the one I will have to revise in the future.
Day 6 seems to give people a break from last one – just skip the iteration where you press the button for
0 second and the whole
duration. There aren’t any caveats you need to notice.
Same, just mind the integer overflow issue.
I was occupied for several days. I just finished day 7 on…12/17.
Also, I actually applied things like
cmp::Ordering for the very first time. Hope I will get much more familiar with these.
I just give different type of hand an enum with corresponding ranks. The remaining processes are just comparing the types of these hands and if they are the same type, proceed to compare the their cards one by one.
Sort hands by these ranks and multiply and adding them up and you will have the answer.
(Looks like I just repeated the description here…since it’s really not much to say.)
Part 2 introduced the rule of
Joker – here it has lowest score as an individual card, but can act as wildcard for others.
KTJJT was originally a two pair and will become four of a kind since we can transform
T, therefore it results in
The key here is just make sure to lower the score of
J to at least less than
2 if you are storing it, and, check what’s the most frequent label (in this case,
T) and add the number of
J to it.
Part 1 is fairly easy as converting nodes to a map and then traverse through it, get the steps and it’s done.
At first, I just wanted to use brute force way to count the total steps. And after struggling a whole day on it (apologize to polar bears again), I finally gave up and admitted this will never do. I might just die in the sandstorm given the slow speed.
Bascially, you still count steps like part 1, but don’t do all of them at the same time.
Just count the steps of each of them like and the calculate the lease common multiple. It looks obvious on the hindsight.
BTW, I noticed that it just not worth using rayon when your collection is very small.
Looks like that a difficult day sometimes followed by a relatively easy day?
Just do what quiz told you. I am sorry if you are expecting something inspirational.
Well, one thing worth mentioning is that, ChatGPT actually gave me a good use of
std::iter::Zip. Really learned something from it.
Same. Instead of appending the new values, you need to prepend it. Since it require
O(n) time to move existing numbers in a
Vec, I changed to
VecDeque (double ended queue). But this is not the quiz where suboptimal performance will take you down.
The farthest point from
S is the total steps divided by 2, you can see that from the example provided in part 1.
Use BFS will be better than DFS as the recursion might be too deep (in this case it’s still fine though). I also spent significant amount of time to write the matching arms for the relation of each pipe, not sure if it can be easier.
Well, I am still struggling ATM. Even though Reddit or somewhere else definitely have clever solutions, I still tried to solve it on my own.
Since it already took a lot of time, I might leave this one for a while (hopefully not forever).