Crate mbryant_aoc2021
source · [−]Expand description
This crate contains reasonably efficient solutions for all Advent of Code 2021 puzzles. See AOC 2021 for more information, including puzzle prompts.
If you haven’t used Rust before, these are generated docs from the
codebase. They should cover my thoughts on the problem and solutions, provide an overview, and
allow easily browsing through the code via the [src] buttons on the right side of the screen.
This is the first time I’ve thought of displaying more than code via Rust docs like this, so
I’m curious for feedback.
Initial Goal
Execute all puzzles before the JVM can start up (~800ms).
Note: This was solidly achieved, as all puzzles run in <100ms on each benchmarked system.
On my desktop, they run faster than python can cold-start (measured via time python3 -c "exit()")!
Code layout
Each day’s code is in a different module (linked at the bottom of this page), with three
mandatory functions: generator, part1, and part2. generator is passed the input text,
parses and computes a useful intermediate representation from it, and a reference to that value
is passed to part1 and part2.
This allows us to focus on each part individually, as well as track the cost of parsing the
input. However, it means we often end up doing duplicated work between part1 and part2.
Solutions are intended to be general, but may require constants to be changed. For example, if the input is a fixed-size grid, data structures will likely use a constant set to that fixed size, since this enables storing data with less required pointer traversing.
Due to the anemic (by modern standards) cache on my desktop machine, I frequently optimize for memory efficiency rather than amount of work done by the CPU. This may not pay off as well on a system with a faster memory hierarchy.
Benchmarking
Solutions have been benchmarked on a few different systems, but the main development was done
on an Intel i7-6700K. System information and results can be found
under the benchmarks module.
For the full code, including framework and benchmarking code, see the Gitlab repo.
Modules
Benchmark results and information about the systems I benchmarked on.
The intro day - not much interesting here.
Inputs can obviously be stored as integers, rather than lists. The biggest challenge today was to keep the ordering consistent between day3::generator and day3::part1/day3::part2.
It’s bingo time. The real problems start!
Calculate the number of segment intersections by drawing each segment on a grid and seeing how many overlaps occurred. This feels gross compared to using math, but the implementation worked out to be both cleaner and run faster.
A part2-gotcha day if you don’t realize the counts are all that matter.
Use some math that’s unjustified but feels approximately correct to find fast answers.
A fun logic problem, with parsing being the most complicated piece.
An obvious BFS day that is more efficiently solved with a linear pass and a modified union-find.
Not the standard interview question with paren matching, surprisingly.
day11::flash each octopus, recursing into the neighboring octopuses whenever one flashes.
Depth-first search using a graph implemented as a bit-based adjacency matrix.
Trivial code to fold each coordinate repeatedly.
We map each pair of elements to its count, then update the counts according to the replacement rules, allowing us to compute each step in O(rules) time.
Use Djikstra’s to traverse the grid, as there isn’t a good heuristic for A*.
Use a custom read N bits primitive to implement a simple recursive parser.
Leans on triangle numbers to reduce the need to brute-force.
Represent snailfish numbers as a list of (value, depth), simplifying day18::reduce_number at the cost of complexity in day18::magnitude.
Horribly annoying matrix code with a problem that seems a lot harder than it actually is.
Conway’s Game of Life, with a minor twist.
A memoized recursive solution using a 4-d lookup table.
Track the set of boxes that are enabled, splitting them as necessary when they overlap.
Fairly tedious code to generate the different state transitions that are possible and then search between those for an optimal solution.
The instruction stream is day24::MODEL_DIGITS similar sequences (each differing by the arguments
to three instructions) implementing rudimentary push/pop with some simple operations on the
inputs.
Another slight twist on Conway’s game of life.