Advent of Code 2021 is here and so am I. I've decided to start a pattern of learning a new language for each AoC I participate in. Last year I learned Python; this year I'm learning Rust! At the time of writing (on the first day of AoC21), I have almost finished reading the Rust Book. As I go, I will try to document my thoughts on each day's solution, both in terms of the solution itself and it's implementation in Rust. Note that this is written assuming you are familiar with what the problems are. You can find the 2021 problem set here.
Day 0 / Day 1 / Day 1.1 / Day 2 / Day 3 / Day 4 / Day 5 / Day 6 / Day 7 / Day 8 / Day 9 / Day 10 / Day 11 / Day 12 / Day 13 / Day 14 / Day 15 / Day 16 / Day 17 / Day 18 / Day 19 / Day 20 / Day 21 / Day 22 / Day 23 / Day 24 / Day 25
Before going into this, I wanted to have at least some working knowledge of how to work in Rust. I was reading through the book, but to gain some more hands-on experience, I redid some of the AoC20 problems. While doing so, I made the infrastructure used to run the solutions. main.rs was made to select a day to run and pass the input to the relevant function as an array of strings. While doing problem 2 in AoC20, I was faced with string decomposition. I spent considerable time trying to generalize the solution to that problem and came up with this. It's far from a perfect solution. For example, I hoped to find a way to try to parse the strings into the given type, but I couldn't find a way to work that much type wizardry. For now it simply returns a list of strings and type conversions have to be done outside the function.
This problem reminded me a lot of the example in the book about using iterators, so that's the route I took for my solution. I was surprised by how powerful chaining methods functions could be. The meat of the solution is only 4 "lines" long (if you bring all the chained method calls together on a single line). I like how you can go through the logic I would normally implement in a for loop, but do it all operating on the iterator as a whole.
Between days 1 and 2, I decided that enough was enough. I wasn't going to download the inputs manually any longer! Thus began my several hour excursion into the rabbit hole of http requests and writing files in Rust. For making http requests, I was hoping to find some simple API like the requests module in Python, but settled for the only thing I could (eventually) get to work. There was a similar process for creating and writing the file of trying desperately to understand why things aren't working until finally things come together. The whole process was a bit of a headache, but I'm glad I went through it. Even though in the grand scheme of things it's not too much code, I feel like I accomplished something.
This problem was perfect for the match statement. The actual logic of the problem was very quick thanks to it. Honestly, my only stumbling point today was trying to figure out how to destructure the split string in one line rather than simply doing it on multiple lines (which is what I ended up doing anyway).
This problem proved to be quite enigmatic for me. If you look at the day 3 file, you'll see it's the first day where I used tests. That's because there were several places where I had bugs I couldn't iron out only using the input data. However, let's go through things in chronological order.
My initial solution to part 1 involved breaking the string representation of each number into individual characters, then parsing them into numbers (either 1 or 0). Once I had that, I iterated through and summed the values in each digit into a vector with the same number of elements as there were digits. By comparing the sum to half the number of digits, I could determine whether 0s or 1s were more common. I had to iterate through the numbers and sum them up individually because of the way the two nested iterators were structured. The outer iterator went through all the numbers and the inner iterator went through the digits. If I were able to take the "transpose" of the iterators, the solution would have been much simpler. If the outer iterator went across the digits, I could map each inner iterator to it's sum and turn it into an iterator of the sums of each digit. From that point it would be the same as when I had my vector of sums. However, I am not aware of any way to transpose iterators like that. This was an instance where I thought using numpy arrays would be exceedingly effective.
Part 1 went fairly easily, but when I saw part 2, I immediately thought I had to take my "most common digit" code and extract it into its own function. Doing this proved more problematic than I had originally expected. I have since cleaned the most common bit function, but the original implementation can be found at this commit. You can still see the idea of summing the digits and comparing to length/2, but part 2 introduces the case where there is a tie. At first I was returning 2 instead of 0 or 1 with the idea that I would deal with the even cases in the usage code, but further analysis of the problem led me to change that to being able to return 0 or 1 (depending on the parity of the length). It depends on the parity of the length because if the length is odd, the .5 gets lost in the integer division, so the equal case is really a less case in disguise. The current implementation takes a different approach inspired by Bradon Zhang to subtract one for each 0 rather than adding 0, then comparing the total sum to 0 instead of length/2. This achieves the same result, but in my opinion, it is a cleaner way than dealing with the parity of the length. Actually, while writing this I realized the parity of the length could be ignored entirely. Since the only case that depends on the parity was the equal case and that can only occur if there is an even count of numbers, we can assume the parity is even for that case and return a value accordingly. Getting the details of this function right was difficult, which is why 3 of the 5 tests are dedicated to making sure it works. Once I got that snafu worked out, making the actual solution for part 2 wasn't terribly hard.
I think the way things work currently could use a lot of cleaning. I may go back and do that once the advent is over, but I'm happy with it for now. I have to do a lot of type casting that I think typing my variables smarter would alleviate. There were also smaller issues that I had throughout the process. Two notable ones in my memory were dealing with a test that kept failing because I forgot to but "0b" in front of the binary number being defined in the test, and trying to work out a way to parse the string as a binary number rather than a decimal one.
I think I could've done this one faster than I did, but in a significantly less clean way. Instead, I tried to use the object oriented features of Rust to make the solution cleaner, rather than faster. By using an enum, I avoided having to store two boards: one with numbers and one with booleans, since I could encapsulate whether the square was marked using the enum cases and store the number inside the enum.
enum Status {
Marked(u64),
Unmarked(u64),
}
struct Board {
nums: Vec<Vec<Status>>,
}Once I was able to abstract most of the important functionality into methods on the Board struct, solving both part 1 and part 2 were pretty simple.
I have learned from previous advents that in situations like this where you have a grid of points, rather than creating a 2d array of the entire board and storing it that way, it is better in many situations to create a hashmap who's keys are the coordinate pairs. Not only does this not require you to know the dimensions of your working space from the beginning, but it easily generalizes to higher dimensions in a memory efficient way. I know it feels weird to call a hashmap memory efficient, but since it's only storing the points of interest (as opposed to an array which necessarily stores all points), it's memory efficiency compared to an array gets better as the density of points of interest goes down. And this is on top of the aforementioned benefit of not needing to know the size when creating the hashmap. I specifically like hashmaps in Rust because of features like the .or_insert method. The number of times I've written code like if x not in map: map[x] = 0 pains me. .or_insert creates the same behavior, but in a much cleaner way. Then, doing the final count was as easy as creating a filter on the iterator across the hashmap.
As I assume many people did on today's puzzle, I did part 1 in way which is very inefficient, but switch over to a better solution for part 2. I've kept my original solution to part 1 commented out in the solution file. The original solution was done by mapping each fish to the number beneath it, then keeping a count of how many new fish get born, then appending that number of fish. The second solution only has a vector of 9 values, each storing the number of fish with that internal counter (0 through 8, inclusive). Using a drain iterator, I'm able to effectively roll the values down by one, then add on the new fish. It's a similar idea to using np.roll in Python. However, this problem's solution was larger than an unsigned 32 bit integer can hold, so I had to switch from using u32s to using u64s. Because of the way the AoC infrastructure I made works (see Day 0) and Rust's static typing, I had to retroactively change all previous solutions from using u32s to u64s. Not a difficult task by any measure, but an unfortunate consequence.
I did pretty good on today's problem: top 700 for part 2. This was because of how similar parts 1 and 2 were, so solving part 2 mainly entailed copy-pasting my solution to part 1 and changing (i - x).abs() to (i - x).abs() * ((i - x).abs() + 1) / 2. When I initially did the problem, I looped through the range 0 through max and kept track of the minimum fuel level, but I later went back and converted the loop to an iterator operation on the given range. Because of the simplicity of the problem, the super-iterator solution can be done in a single expression, so the answers are calculated in the return value; the first line of the function is a solution which truly does the whole problem in a single line. This is just a flattening of the prettified solution below it, but it does mean that everywhere that uses the nums variable in the pretty solution has to go and parse the input again. In total, this one-line solution is ~500 characters long. Overall, an easy problem. I am growing ever fonder of iterators in Rust with every problem that can be solved by leveraging them.
Part 1 was pretty easy, so I will spent my time here discussing part 2. One key thing to note was that the solving path is the same regardless of what the input is. The process goes something like this:
- We know which of the input is 1, 7, 4, and 8 because they have a unique number of segments activated.
- Top = 7 - 1 (note that the arithmetic is done on the sets of segments making up each digit, not the literal numbers).
- 4 + 7 = 9 - Bot
- For this, there are two unknowns, Bot and 9. However, 9 is the only number which has one extra segment beyond 4 + 7. Therefore, by finding which number for whom |x - 4 - 7| = 1, x must be 9 and the one element must be Bot. This operation is performed in the
find_one_morefunction.
- For this, there are two unknowns, Bot and 9. However, 9 is the only number which has one extra segment beyond 4 + 7. Therefore, by finding which number for whom |x - 4 - 7| = 1, x must be 9 and the one element must be Bot. This operation is performed in the
- BotL = 8 - 9
- 7 + Bot + BotL = 0 - TopL
- 4 - 1 - TopL = Mid
- Top + Mid + Bot + BotL = 2 - TopR
- BotR = 8 - AllOtherSides
Once we know which letter corresponds with which side, we invert the key to get the reverse key and decrypt the numbers given. There are certainly other solving paths that work just as well, but I don't think it can get any shorter, since each step beyond the first one involves finding one of the seven sides and I don't think it's possible to find multiple sides in a single step.
Once I had managed to read the problem properly (a surprisingly difficult task today. For example, I didn't realize the problem was 2D at first, and it wasn't until after I had nearly finished part 2 that "adjacent" wasn't including corners in this problem.) part 1 took some thinking on how to structure a clean solution. At first, I didn't have the BasinMap struct used currently, so indexing the 2D Vec while checking for any Nones was ugly. However, ugly code can still be functional code, so after misreading the problem 5 times, I got the right answer. Part 2 required the introduction of the BasinMap struct. BasinMap just holds a 2D vector of tuples. The first element stores the depth number, and the second is an index of the basin it's in. a basin-index of 0 means it's in no basin (yet), so all non-low-points start with an index of 0, and all 9s keep that index of 0 throughout the process. The advantage of wrapping the 2D vector into a struct is I can define my own get function which goes through the hassle of two dimensions of Options. The ? operator is great for this since it provides a way to chain together operations on Options without clunky syntax of always checking for Some values. Since each point is guaranteed to flow into only a single low-point, I assign an index to each low-point in the first pass for part 1. Then by flood-filling each non-9 point until we find a point with a non-zero basin-index, we can determine the basin-index of the entire flood. Finally, keeping track of the size of each basin in a separate vector means finding the largest 3 is trivial.
After completing the problem, I created a visualization of the map to print to the console. To do this, I used the colored crate to display the basins in different colors and the rand crate to generate the random colors. Currently there is no visualization flag in my interface, so it always displays the visualization. I'm thinking of creating this flag, but since I only have one visualized day so far, it's not too big a deal.
My initial thought for this problem was to have two enums: Orientation and BracketType, and have the BracketType enum store an Orientation in each value, but while this direction made more sense in my head, it didn't work as well with the problem, so I ended up doing things in reverse: having Orientation store a BracketType. However, this is still clunky so I think I will end up doing neither and instead having a struct storing both. I think I fell into the trap of wanting to use the shiny new features available to me in Rust even if they're not the best for the job. This is something I will have to make an effort to avoid doing for the rest of AoC, or indeed the rest of my Rusting.
Because of how similar the problem and the input was today and day 9, I was able to reuse a significant portion of the code from day 9. Most problems in AoC have a part one that's mainly there to prepare you for the punchline in part 2, but today was different. Part 1 was too good at preparing me for part 2. Once I had part 1 done, part 2 took 2 minutes of changing the main loop and fixing an off-by-one error. I went into the problem not exactly knowing how I would handle the flashes, since I wanted to avoid double-flashing the same octopus. The solution was to increment the octopus index regardless of whether it had already flashed, and only flash if its index is exactly 10. Then all the octopuses that flashed will be at least 10 once everything has settled. They may go higher than ten, but 10 is the lower bound. Setting all these to 0, then counting the number of 0s gives the number of flashes that cycle.
Because of the little intricacies in day 12, there were many little details beyond your usual depth first search. I end up passing around a bunch of variables that don't get changed between calls, only passed around. Getting all the little details right was an interesting challenge, especially for part 2. A part of what I did today that I am particularly proud of is my optimization of the get_adj function. Previously, it returned a vector of the adjacent caves, but immediately the vector got turned into an iterator. So with some research and following the instructions of the all-knowing compiler, I got it to return an iterator, so I avoided the extra step of collecting the iterator into a vector, giving me a significant speedup.
Here I use a mix of HashSets and Vectors to store my data. I'm not sure what the performance benefits of one over the other are in some situations, so I mostly picked which one to use out of convenience. One place where I thought a HashSet would be better is the visited parameter. Since it's main use is checking whether it contains something, I would have thought a HashSet would have been faster, but testing it out, using a Vector is noticeably faster. I don't know enough about how they work under the hood to have a good explanation for this, but am interested in finding out more about it.
This was an interesting one since it's the first one this year who's answer isn't a positive integer. My system for running things only handles u64s for outputs. However, parsing this output programmatically is more trouble than it's worth, so I simply return 0 for part 2, and print the code to stdout. Since the code is represented graphically, it is up to the user to parse it.
I had some difficulty with this one until I figured out the folds aren't always in the middle of a side, meaning some points will get folded over the edge of the paper and get dropped. Once I handled that, the rest was pretty simple.
For this one, I could feel that part 2 would ask me to go further than the naive solution would allow, but at first I couldn't think of a way to do it without storing the entire string. My reasoning was that since you not only need to know what characters are in the string, but also what order they are in, you would need to store the whole string no matter what you did. I went ahead and implemented the naive solution for part 1 and sure enough, part 2 asked to go further. Eventually I realized that rather than storing the counts of each letter (which wouldn't have any information about letter pairs), I could store the counts of each pair. Since each pair inserts a letter between them, it can't affect the adjacent pairs. As a final note, since each letter is part of two pairs, summing the pairs double counts the number of letters. The exception to this is the first and last letters, since they are only part of a single pair. Thankfully, the start and end characters stay the same throughout the process, so even though the representation of the string used in the problem doesn't cary any information about what characters are first and last, we can refer to the original string to find this out.
Day 15 was pretty painful for me. The start of it was easy because I could copy the infrastructure for dealing with a 2D grid of digits from day 9 (same as day 11). At first I assumed the path could go in all directions, but my implementation caused a stack overflow from recursing too deep. Since the example only goes down and to the right, I reduced my solution to only work with paths that go down and to the right. This worked for part 1 and the example for part 2. When it didn't work for my actual solution to part 2, I was left scratching my head. Moving back to omni-directional paths caused a stack overflow, but the solution had to use these paths. After coming up with a better approach, I went to bed to leave it for the next day.
The next day was just as hair-pulling as a mix of careless errors and algorithmic problems plagued my work. Eventually I fixed most of the issues aaaand it stack overflowed. The advantage of this new approach was that it didn't need to be done recursively, so rather than rely on the call stack, I kept my own stack and pushed/popped it manually. After fixing a minor mistake with how the algorithm handles the first point being processed, I had my answer.
Going back to it later in the day, I cleaned it up and optimized it by using a deque instead of a stack to have more control over what order points got ran in. If a point gets run for the first time, it's adjacent points get pushed to the front of the queue, otherwise the adjacent points get pushed to the back of the queue. I'm not sure why this speeds things up. I just know that I tested doing things that way and doing the reverse. Doing the reverse slowed it down 25x and doing it this way sped it up (not 25x sadly).
Today's reminds me of day 18 2020 with the expression evaluation. The previous one was able to be broken by exploiting the eval function in python. Today's problem effectively circumvented the problem by making actually parsing the input 90% of the problem. structure I used to represent the problem was based off my experience in trying to develop an actual programming language in Rust. Splitting the different operation types into a separate enum than the main PacketType enum cleans the code fairly significantly in my opinion.
Honestly this one was more about math than coding. I don't have much to say other than once I realized that fact, I could just find the min and max velocity in each direction, then test all possible velocities to see which ones worked.
This problem practically slaps you across the face and says "use RECURSION dum dum!" So anyway, I did not use recursion for this one. Dealing with recursive references and ownership in Rust felt painful when I initially tried doing it. Additionally, since information from children affects how parents behave, I would either have to be smart about handling parent references, or be smart about returning values from recursive functions. Both of these require being smart, so I chose neither. Instead, my representation of a SnailfishNumber is as a vector of tuples. The first value is the number itself, and the second value is the depth of the number. For example, the SnailfishNumber "[[1,2],3]" is represented by the vector [(1, 2), (2, 2), (3, 1)]. This made exploding pairs very easy, since finding the next number to the left/right is as easy as dec/incrementing the index. Adding is also easy. Just concatenate the two vectors together and increment all the depths.
I played around with using standard library traits for this one. I mainly used Add, Display, and FromStr (I derived the other traits I used rather than write them myself). The effect of the traits could have been done without using them, and instead using my own functions, but for the sake of experimentation, I used the traits. The first trait I wrote was FromStr. This allows me to use str.parse() to get a SnailfishNumber directly. The vector representation of the number lends itself well to this, since the order of numbers in the vector is by definition the same as the order in the string. Keeping track of the depth just entails counting the brackets. Writing the add function was simple as I already described the process of adding two numbers in this representation. However, I did run into a kink when implementing Add. There were various combinations of references and non-references to worry about. I ended up implementing Add for every combination of reference I used, but I don't think this is a good solution. It has unnecessary repeat code. The current code has a bit of a bad smell that I'm unsure how to fix. Despite this, Display was by far the hardest trait to write.
I finished part 1 and started part 2, but part 2 is very much easier using a recursive representation. I tried for a while to find a clever way to do it using my representation, but came up with nothing. At this point, I was unsure if it was even possible. Perhaps the way I was representing the numbers lost some information that was needed to do part 2. As a result, I decided to take a detour to see if this was the case. I wanted to prove that my representation was lossless. If I could turn it back into the original string it came from, essentially doing the reverse of what I did in FromStr, then I would know it was lossless. Doing this proved to be easier said than done. I found an important quantity for iterating through and displaying the number was what I called progress. It represents the fraction of the way through the number you are. Numbers of greater depth count for less progress, while a number at a depth of 1 would add 0.5 to the progress. In general, the contribution a number has to progress is 1/2^depth. This way, the progress is guaranteed to be 1 by the end of the number. However, to keep the progress as an integer (this will become important later), the progress variable I used is actually 16 times the progress described here. 16 comes from 2^4, where 4 is the maximum depth a number can have. This makes a number at a depth of four contribute 1 to progress and one at a depth of 1 contributes 8. The bits of progress cary important information about the structure of the number beyond just the depths. Information that is easy to get in a recursive representation of the number.
An important quantity to know to display a number is the depth of each comma. This tells us how many brackets to add to either side of the comma such as "]],[[". If we're half way through the number (progress = 8/16), then the comma must have a depth of 1, since that's the comma separating the upper pair. Likewise, if we're a quarter or 3 quarters of the way through (progress = 4/16 or 12/16), we're in the middle of a pair one layer deeper. Continuing this pattern, it becomes apparent that the depth of the comma is related to the position of the least significant bit which is set. Specifically, comma_depth = MAX_DEPTH - first_set_bit_index where "first" gets measured from least significant bits to most significant bits. Once I had my Display done, and knowing about the power of the progress quantity, I went back to part 2 and finding the magnitude of the number.
Another power of the progress bits was that they were essentially directions to the number if it were in a binary tree representation. The most significant bit (counting only the first 4 bits since the maximum depth is 4) says whether we're in the first or second half of the number. The second bit tells us which half of the half we're in. It feels somewhat obvious to explain now, after all, that's essentially what binary numbers are, but realizing it applied to the situation of the SnailfishNumbers was huge for me. For a number at depth d, the first d bits of progress say what sequence of lefts and rights it would take to get to it in a binary tree. This means that the contribution to the total magnitude is the number itself times 3^(num 0s)*2^(num 1s) since 0 represents left and 1 represents right. With that, part 2 was finished.
I think this problem is a great example of how I approach harder problems. I prefer to rely on mathematical properties of the problem itself rather than rely on programming knowledge. In this case, it was exploiting the mathematics of the progress rather than try to program my way around the tree representation. Thankfully, this most problems aren't hard enough for this to become particularly relevant, but sometimes even simple problems can have this effect happen to them if they rely on some programming tidbit I'm not to familiar with.
As of writing this (which is admittedly on the 22nd), day 19 has the lowest number of clears. Additionally, it was the only day so far which I did not complete on the day it was released. That's because it was hard. It required a lot of thinking and my ultimate solution has loops six layers deep. The second and third loops go through pairs of scanners. The fourth loop goes through all beacons in the first scanner and the fifth goes through the second scanner. The sixth goes through all 24 possible rotations. Then, with a given pair of scanners, pair of points, and rotation, it sees if the two align. It rotates all beacons in scanner 2 using the rotation matrix, then translates them so that the two selected beacons overlap. If at least 11 other beacons (12 including the beacons which are used for the alignment), then we say the two scanners align that way. Then, the second scanner gets merged into the first, and the new scanner replaces its two component scanners in the total pool of scanners. The process repeats itself (the first loop) until all scanners have been merged into a single mega-scanner.
To accomplish this, each scanner no only stores the positions of its beacons, but also stores the positions of each beacon relative to each other beacon, making it
I banged my head against this one for a while, but a little birdie point me at the fact that this is a cellular automata where 9 empty squares do not turn into an empty square. Once that became clear, my plan was to alternate between storing a positive and negative of the image. Going from a positive to a negative image is as easy as saving the inverse of what the rule says. Going from a negative to a positive on the other hand, not as simple. I needed to construct an inverse rule to apply to the negative image. That's where this little bit of nastiness comes from.
for i in 0..rule.len() {
inverse_rule.push(!rule[!i & 0b111111111]);
}Basically, to find the inverse rule, I need to invert the bits of the index (because it's a negative image), then invert the rule at that location (because to cancel the negation that comes from switching from negative to positive). the & 0b111111111 exists solely to only invert the first 9 bits.
By switching back and forth between a positive and negative image, the background is always 0, so we never have to worry about handling it.
Seeing the numbers in the example, I knew simply recursing through each universe would be insufficient. Fortunately, there is a finite number of states the game can exist in. The state of the game is determined by the positions of the two players and the scores of the two players. A HashMap mapping a state to the number of universes in that state can completely encapsulate the state of all universes. Also, I don't need to go through every single possibility of the 3 dice. Since all possible combinations of the three dice are dealt with, and the only thing that affects a universe is the total on the three dice, the outcomes of the three dice can be flattened into a single array mapping the total on the dice to the number of universes in which that total occurs. Therefore, the number of universes in a new state is equal to the number of universes in the old state times the frequency of player one's roll times the frequency of player two's roll (unless the game ended on player one's turn, in which we don't care about the roll of player two).
I struggled with this one for a while, trying to find a way to find the change in the lit light count based solely on the instructions before it, but came up short. Eventually the solution I settled on was to store a CubiodSet as a group of Cubiods. Adding a cubiod requires subtracting each of the existing cubiods from the new one. Subtracting a cubiod from another requires splitting the cubiod into several (up to 6) separate cubiods. Subtracting out a cubiod just means taking each of the stored cubiods and subtracting the negative space from them individually. This causes a lot of fragmentation, so there's also a defragmenting method that combines cubiods that are a) adjacent in one dimensions and b) the same in the other two dimensions. Combining these cubiods into a single cubiod reduces the amount of cubiods to split in the next operation. Defraging every time after adding a new cubiod results in less than half the cubiods existing in the final result, but because it's an expensive operation, it actually takes longer (7s vs 2s on my machine only running part 2). However, because I think it's cool, I've decided to keep it in the code. It would likely be faster to do some checks before adding a cubiod. For example, if the new cubiod is entirely contained in an existing cubiod, it can be ignored, or if an existing cubiod is contained entirely in the new one, the old cubiod can be discarded. Perhaps I will add these optimizations at a later date. Another important optimization would be to do part 1 the same way I do part 2 part 2 is faster. When not doing part 1, the program runs in under 10s, but while doing part 1 it takes almost a minute. I've decided, as I have in previous days, to commit my first solution to part 1 to be a more accurate reflection of what I did to solve the problem, but I may go back and improve the solution later.
In principal what I did today was nothing more than a dfs trying to find the solution with the minimum energy requirement. However, due to the awkward problem space, this ended up requiring a lot of maneuvering of around position structs. I don't think my solution is particularly clean, but it gets the job done. It's not a pure dfs, however. Because there's no reason for an amphipod to not move into its room when possible, The possible_next_states function will only return one next state if an amphipod can move into its room. This is an optimization to prevent the number of branches the dfs looks through from getting too large. Even with the greedy part, it is still very slow to run. Part 2 wasn't too bad to make. There were a few places where I had hard-coded the depth of a room to be 2, so I just changed those to accept an arbitrary depth (though not really. The array storing the rooms is only 4 deep. If I wanted to really allow it to be arbitrary, I would have to change it to a Vec). Once I made that change, part 2 just involved making the initial state differently, and running it with a depth of 4 instead of 2.
While making this, I learned the power of the todo!() macro. Normally, I would create a function signature and try to return some default value from it to prevent the compiler from complaining about the return value. With todo!(), I don't have to worry about that anymore. I can just create the function signature and slap a todo in it, then no more complaining for the compiler. Additionally, it means I can't forget to go back and write the function. The program panics if it reaches a todo, leading me directly to where I need to work next. This is both more convenient and less error prone than what I did previously.
The run function for today is rather sparse. It just returns the two answers as literals. That's because I found the answers on paper. The way I got the answers is a bit of a story. The tl;dr is that I manually decompiled the program given into Rust, then analyzed that program to find the answers.
The first thing I did was to create an ALU to run the "assembly" code given. I'm a bit sad that I didn't get to use it in the actual solution, but it wasn't that hard, so I'm not too terribly cut up about it. Writing it was about the same as all the other language interpreters written for AoC. Once I had the ALU made, I set it testing all the numbers from 99999999999999 to 11111111111111. Obviously that's a bit too many numbers to test, so I moved on to try something else. The first thing I did was to try to simplify the source assembly code. Getting rid of instructions that do nothing like div z 1 was a first step. I also started from the top and started removing superfluous instructions. The second through fifth instructions are mul x 0; add x z; mod x 26; div z 1, but since the registers are all initialized to 0, these do nothing, so I got rid of them. I slowly worked my way through, trying to reduce the number of instructions in order to make each iteration run faster. Going through, I started recognizing what was going on, and upon further inspection, learned that the entire program just runs the same thing 14 times; one for each digit of the input. There are a few differences between each iteration, but those are just doing the same arithmetic with different immediate values. This meant the program was a lot simpler than I had originally assumed.
Seeing this, I went ahead and decompiled the whole program into Rust. _simulate_code_raw is a one to one transcription of the assembly into Rust. From there, I made the code more clean and understandable in _simulate_code_readable. I could start to see the shape of something in base 26, but couldn't figure out what exactly was going on. The z register was clearly in base 26, with each digit being based on the digits of the input. But sometimes it would be divided by 26 and sometimes it wouldn't. I couldn't make heads or tails of it. Eventually, it got too late, so I resorted to brute force.
I knew the way I was doing it wouldn't cut it if I wanted to check enough numbers fast enough. I rewrote the function again as _simulate_code to try and optimize it as well as I could. Then I looked into parallelizing execution to check as many numbers as possible. My plan was to leave it running overnight. My first thought was to get it to run on my GPU, but decided that rabbit hole wasn't something to start exploring that late at night. I settled on using the rayon crate to parallelize the execution on the CPU. The api for rayon is simple to use: just convert the iterator into a parallel iterator and treat it the same as you would any other iterator. There was just one hiccup. to find the max workable value, you would want to start from the top and work downward. Rust ranges are always increasing. To get a decreasing range, you call .rev() to reverse the iterator. This doesn't return a whole new iterator, but instead returns a Rev struct. Rayon doesn't support turning a Rev into a parallel iterator. Instead, it has its own .rev() function to reverse an iterator after it's been parallelized. Unfortunately for me, this isn't supported for 64 bit integer iterators. As a result, I couldn't find a way to count down 64 bit numbers in parallel. I ended up starting my range at 91111111111111 to try and get closer to the max value (and as we'll see later, it was really fortunate I did this). I did not expect to find the max value this way, but I hoped I would find at least one working value. If I had one number that worked, that would help me reverse engineer the algorithm to find other working numbers. I set it running and went to bed.
The next morning, I had 15 numbers that passed the check, but it was still running. None of the numbers were the max. I made my fourth and final version of the algorithm: _simulate_code_dbg. This was just a copy of _simulate_code, but printed the value of z after each iteration. Because z is a base 26 number, I printed it in base 26 (using the letters of the alphabet as digits because 26). Running this function with some of the numbers I knew worked, the same pattern arose from each one. Here is an example output from testing the number 91131395919893.
91131395919893
J
JN
JNP
JNPD
JNP
JNPS
JNPSU
JNPS
JNPSK
JNPS
JNP
JN
J
A
It ends in 0 (A is the digit for 0 here), meaning the number passed the check. But the interesting part here is the length of z at each step. It goes up and down in increments of 1, as I thought it did previously, but the pattern is the same across all the working numbers. Looking into the significance of the pattern, I found that 3 things aligned! Whenever the length of z went down, the number added to x was negative, and z was divided by 26. Whenever the length of z went up, the number added to x was positive, and z was divided by 1. The condition in the loop if x != w must only be true when the length of z increases, and false when it decreases. In other words, when z gets shorter, x must equal w to prevent it from getting longer again. This means the value of the digit being read each time that happens is determined by the digit currently at the end of z. This groups digits into pairs. If the index of the first digit (d1) is i1 and the second (d2) is i2, then d2 - d1 = Y_ADDERS[i1] + X_ADDERS[i2]. Or, rearranging to find the second digit in terms of the first, d2 = d1 + Y_ADDERS[i1] + X_ADDERS[i2]. This uniquely determines the second digit of a pair based on the first. However, since the digits of the input are 1-9, but the digits of z are 1-26, not all numbers will be valid. Only pairs in which both numbers are in 1-9 will be valid numbers. Despite this, it still becomes very easy to find the max/min possible number by maximizing/minimizing the first digit in each pair and setting the second digit accordingly. By doing this on paper myself, I found the answers (hence the hard coded response in the actual code).
As a final note, I mentioned that it was a good thing I started my search at 91111111111111 rather than 11111111111111. That's because the minimum number that would've worked was 71131151917891, and my overnight search only got through 11 of the 14 digits, so there's no way it would have gotten a single working number. That would have made solving the problem a lot more difficult for me.
Whelp, it's done. All 25 days! This was an enjoyable AoC, and I'm glad I took the opportunity to learn a new language. This provided me with a very nice place to use my newly learned Rust knowledge. It is certainly better than reading up on Rust, then never using it.
The problem itself for today was fairly simple. My main comment was that I made a careless error in part 1 when checking the space ahead of the fish. Essentially, I didn't take into account the fact that the Eastward fish had already moved when checking whether the Southward fish could move. Other than that, fairly standard stuff. Part 2, on the other hand, took me a while. You can read about my process of doing part 2 in more detail here.