Crate mbryant_aoc2021

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

benchmarks

Benchmark results and information about the systems I benchmarked on.

day1

The intro day - not much interesting here.

day2

More interesting parsing than day1, but not too different or difficult.

day3

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.

day4

It’s bingo time. The real problems start!

day5

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.

day6

A part2-gotcha day if you don’t realize the counts are all that matter.

day7

Use some math that’s unjustified but feels approximately correct to find fast answers.

day8

A fun logic problem, with parsing being the most complicated piece.

day9

An obvious BFS day that is more efficiently solved with a linear pass and a modified union-find.

day10

Not the standard interview question with paren matching, surprisingly.

day11

day11::flash each octopus, recursing into the neighboring octopuses whenever one flashes.

day12

Depth-first search using a graph implemented as a bit-based adjacency matrix.

day13

Trivial code to fold each coordinate repeatedly.

day14

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.

day15

Use Djikstra’s to traverse the grid, as there isn’t a good heuristic for A*.

day16

Use a custom read N bits primitive to implement a simple recursive parser.

day17

Leans on triangle numbers to reduce the need to brute-force.

day18

Represent snailfish numbers as a list of (value, depth), simplifying day18::reduce_number at the cost of complexity in day18::magnitude.

day19

Horribly annoying matrix code with a problem that seems a lot harder than it actually is.

day20

Conway’s Game of Life, with a minor twist.

day21

A memoized recursive solution using a 4-d lookup table.

day22

Track the set of boxes that are enabled, splitting them as necessary when they overlap.

day23

Fairly tedious code to generate the different state transitions that are possible and then search between those for an optimal solution.

day24

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.

day25

Another slight twist on Conway’s game of life.