Advent of Code 2024

Rust!

Daily Themes and Stars

** programming basics: parsing input, loops, sorting...this is day 1?
** corner cases, refactoring, premature optimization, tests, $O(8) = O(1)$
** regular expressions, reading the instructions (example 2 is not the same as example 1)
** 2D arrays, bounds, regex doesn't work, graph traversal
** sorting with custom comparators
** object-oriented programming, order of operations, cycles, grids, why is this so slow?
** recursion, operator precedence, digit string concatenation, why is this so fast?
** vectors, procedural programming, grids, distinct values (sets; deduplication)
** disk fragmentation, arrays (trickier-than-it-looks, annoying procedural programs, puzzle could probably be solved faster than actually doing it...)
** searching (I used BFS), grids, path-finding
** dynamic programming, recursion, automata
** more grids, divide-and-conquer was not the solution, graph searches
** linear algebra (Ax=b), greedy algorithms, integer division loses information
** corner case (well, "center case" since the middle doesn't count), constants, modulus operator, even more grids, find the Christmas tree
** still more grids, refactoring, procedural programming/mutable state, so many cases, order of operations, queues
** A*, pathfinding, complex arithmetic
** assembly, backpropagation, too big for Goal Seek
** pathfinding, bisection
** tries, dynamic programming/memoization
** cost analysis (this problem is smaller than it looks), abstraction, even more index trickiness
** robotics, indirection, nested loops, dynamic programming/memoization, hard problems
** arithmetic, complicated instructions, subsequences, pseudo-random number generators (PRNG), MapReduce
** maximal clique problem, matrix-based solution, coping with NP-hard problems
** logic gates
** combinations

Lessons Learned

VSCode helps so much when it shows the inferred types. This feature is called inlay hints.
On the other hand, RustRover's Copilot-like predictions would take some getting used to. I found myself accepting predictions that looked right, but later turned out to have subtle mistakes that were tricky to debug. I know lots of people feel more productive iwth Copilot, but for now I need to learn the language for myself.
Consider using into_iter when it's OK to consume the iterator or decorate closure parameters with & to make them a little more comfortable.
Use &[T] instead of Vec<T> as function arguments.
count() might not do what you expect. Did you mean len()? You might need to collect the iterator into a collection.
filter_map() makes clever use of optionals to combine filter and map. It composes nicely with match.
Rust regex doesn't support lookahead (?=). Might have been useful for day 4.
Vec<Vec<char>> sorta works for 2D strings, but it isn't as clean as you'd like.
Rust apparently has no try/catch. There isn't a great way to backtrack from array accesses with yolo bound checks. I think you could avoid the panic with get, but this didn't work with my Vec<Vec<_>>. A hashmap might have been much easier than nested vectors.
is_sorted_by and sort_by expect different comparison functions. is_sorted_by operates on booleans, sort_by uses Ordering.
Day 6 was difficult for me. I came up with an interesting solution (inspired by a Reddit comment) based on TTLs instead of keeping the path explored. It was a case where compute is faster than memory.
My Day 6 solution is among my slowest programs. I wonder if a grid would have been better than the hashmap.
Someone else on Reddit helped me with an extra test case.
ilog on integers is much faster than casting to and from float types for logarithms.
https://stackoverflow.com/questions/40006219/why-is-it-discouraged-to-accept-a-reference-string-vec-or-box-as-a-function
https://stackoverflow.com/questions/30633177/implement-fmtdisplay-for-vect
Expect compiler errors or runtime crashes on integer overflow. One should prefer addition to subtraction when comparising distance. z.B, to check if a: u8 is one less than b: u8, use a + 1 == b instead of b - a == 1.
Day 11 was a tricky dymanic programming problem. Two tricks: you don't need to worry about the stone order (despite the phrasing of the prompt), and you only need to count occurrences of the numbered stones. I had my head wrapped around a jagged recursive triangle, but you don't need that. This is more like the iterative Fibonacci approach with while i < k { (a, b) = (a + b, b); i += 1 }. You actually can use trees, but you need to count down to a basis of depth=1. See [2024 Day 11][Python] MEGA TUTORIAL. See also [2024 Day 11] Every sequence converges to 3947 points (with proof) for an interesting study of attractors in this problem.
include_str! can bring in the contents of a file. My tests show that the performance is about the same as std::fs::read_to_string, but it's nice to ship a binary with no dependent files.
In day 9 I had some trouble with the borrow checker. Passing a reference to a mutable struct into a function might not work. Consider the object-oriented approach.
Be careful with the Copy and Clone traits with the members of a mutable array. You might accidentally copy a value without realizing it, then be surprised that your writes aren't working. A workaround is to just reference the array members directly.
Vector comparison (v1 < v2) might not quite do what you expect in nalgebra.
I might have to check out ndarray.
These procedural days (days 6, 8, 9, 12, 15) are difficult. Maybe Rust makes it worse, maybe I'm just not good at them.
The swaps I did in day 15 probably made this harder than it needed to be. I had made an early design decision to model the game as a grid (2D array) with contents, rather than a collection of game objects with coordinates. Had I opted for the objects, I could have simply incremented their x/y positions as a group instead of this order-dependent swap nightmare.
flat_map combines map and flatten.
The @ operator binds matched values of a pattern to values.
Rust's std::collections does not have a red-black tree, but it does provide a BTree.
I was surprised that BTreeSet produced slightly faster runtimes than HashSet in day 18.
Day 21 is very difficult. I resorted to modeling the button presses manually using JSON. Serde makes it easy to deserialize a JSON string into a string. I was surprised that it correctly read JSON string elements into the char type for my application.
I tried unsuccessfully to reduce day 24 to A*, much like the 8-piece puzzle problem. I still think this method could have worked, but ${222 \choose 2}^4$ is a very large search space. I solved day 24 by rendering the logic gates with GraphViz, learning how an adder works, and spot-the-difference troubleshooting.

References

Libraries

grid for 2D vectors that don't need to be full matrices.
nalgebra for matrices.
socket2 for future networking projects requiring raw sockets.
Ratatui for terminal user interfaces (TUI).
clap for command-line argument parsing.
hyper and axum for making web applications.
Handlebars, Tera, Maud, and Askama for HTML templating.
SQLx for accessing databases.
Serde for serializing and deserializing JSON and many other data formats.
nom for parsing.
Bevy for games.
pathfinding for graphs.
Rayon for parallelism.

wjholden/Advent-of-Code-2024

Advent of Code 2024

Daily Themes and Stars

Lessons Learned

References

Libraries