Crate advent2021[−][src]
Modules
Day 1:
This solution uses a sliding window of 2 values for the first part. In the
second part we expand the window to 4 values as
[a, b, c].sum() - [b, c, d].sum() == a - d
, so we only need to consider
the first and last values to determine if the three value windows increase
or decrease.
Day 2:
The main part of the effort for this solution is reading the input into a
correct structure. From there following the computations are straightforward.
In the second part, I leveraged the fact that one of the two parts of the
Direction is zero to avoid branching logic, making the code take half as
long as the branching version of the fold
.
Day 3: I’m not entirely happy with this solution because it feel very cumbersome. The first part is messy because it is faster to count all bytes at the same time. For the second part, partitioning seems the most straightforward approach, but I have a lot of code duplication.
Day 4:
I encoded the board into row and column indices for each possible ball.
I took a huge performance penalty for using method(self)
instead of
method(&self)
at first.
Day 5:
This solution process highlighted two things. First, branching logic can
be expensive. My original solution to part 1 was 3x slower than the
solution to part 2, but the only difference was checking if dx
or dy
was zero. Second, this difference reduced greatly when I switched to a
narrower data type, using i/u16
instead of i/u32
and using a u8
for
my grid
s representing the vents.
Day 6:
This was a reasonably straightforward problem. The key is to keep track of
number of fish of each age instead of modeling each fish separately.
Of note, manually rotating seems to be faster than rotate_left(1)
in this
particular problem. Also of note, there is no need to actually rotate all of
the fish if you rotate the meaning of each index.
Day 7: The triangle number formula helps tidy up the code here. I am nearly certain that the answer for part 2 has to occur near the average, but I don’t have a full proof of this hunch. Sorting is the bottleneck, but using an unstable sort helps somewhat.
Day 8: For this puzzle I decided to parse all input into digits first. Pushing all of the work into the input parsing made the two questions trivial. To parse the final 4 digits, only the 1 and 4 of the initial digits are required. You don’t need to identify all 10 digits.
Day 9: Using the overset grid to homogonize operations helped efficiency today. Without this overset, special logic would be needed to handle the edges and corners of the smoke map. For the second part, I used a flow fill algorithm changing the values so the recursion worked correctly.
Day 10: I used the typical algorith for brace matches. The slowest part of this approch is the parsing of each line, with the dynamic creation of the vector of opening braces.
Day 11: This solution relies upon knowledge of the grid size for performance. Without this knowledge, the grids need to be stored in Vecs instead of arrays. I used a recursive update around each point that triggered a flash. Most of the speedup came from homogonizing loops and reducing branching logic.
Load: This module has the code for loading input from file to a string buffer
Output:
This module collects some of my println!
boilerplate between the days.