Advent of Code

Day 13 had a problem that could be solved cleverly – by manually looking for a solution with a constantly increasing loop size, or by finding a value \(x\) that satisfied a series of equations of the form: \(x \equiv b \mod m\)

I spent quite a bit of time revising all I'd learned with Khan Academy. (Prof. A. T. – my number theory professor from college – would be very disappointed at how little I remember; but that class was 11 years ago.)

I rolled my own function to get a modular inverse and then successively reduced the equations by combining 2 constraints into 1 repeatedly till I got a single modular congruence, which I solved to get the least positive integer that worked..

I enjoyed this problem a lot, and was feeling particularly proud. Then I saw Sophiebits's ~20 line solution and couldn't believe that it worked. Figuring out how this solution worked was fairly gratifying in itself:

• Calculating the solution for the Chinese remainder theorem by applying the direct construction of the existence proof, and getting the value much more simply.

• Calculating the modular inverse in Python using Fermat's little theorem, where \(a^{p - 1} \equiv 1 \mod p\) if \(a\) is not divisible by \(p\); or \(a^{p-2}\) is the modular inverse of \(a\) mod \(p\).

  Of course, since version 3.8 python also directly supports taking the inverse by passing in a negative value pow(a, -1, m) as the exponent instead.

After brute forcing my solution for day 15 and assuming I'd messed up somewhere, Reddit pointed me to an excellent video by Numberphile on the Van Eck Sequence which was fascinating.

I'd become fairly arrogant with my abilities writing parsers after writing a few trivial procfile and s expression parsers. I completely missed out on the fact that operator precedence is a thing parsers have to account for and Day 18 drove that home.

Obviously, with my superior (/s) parsing skills I wasn't going to look up anything. I wrote some code to break the input into tokens manually, and then simply evaluate left to right eagerly for part 1.

For part 2, I ended up creating trees and then re-rooting them while parsing according to manually determined operator precedence rules. I also added support for eagerly evaluating parts that were known to be complete, which was surprisingly trivial.

Given this was a tree based implementation in Rust you can imagine that I had a lot of fun dealing with borrows as well. I suspect this was my favorite day from AoC 2020.

Reading other solutions after the fact was amazing: u/fizbin collected a lot of approaches in their Reddit post. My favorites include:

• How fortran did operator precedence, described in Wikipedia
• eval-ing the string in Python after some shenanigans to override operator behavior.

The ideal solution for day 23 involved a linked list: that made the required operations significantly cheaper. Given I've been using Rust, one of the last things I want to do is write a pointer based linked list – for this particular problem I could do it by using a long Vector where the position in the vector identified the value, and the actually value stored at that point pointed to the next element in the list.

Faking pointers using indexes into an array works out surprisingly smoothly in Rust.

This was fairly satisfying to figure out, particularly because my initial solution took 3 hours and the one with the correct data structure took <1s.

Figuring out how to translate hexagonal movement into absolute coordinates was a lot of fun: the key insight to making this all work was realizing that I could represent a single point with several hexagonal paths – and a single set of (x, y) coordinates. Avoiding complex irrational numbers meant I could translate things fairly simply into an offset of 2 along the East-west direction, and 1 up and 1 east for the others.

Red Blob Games has an excellent article on hexagonal grids that I'd read several years ago, but I must admit I never really internalized it till I worked things out myself this time around.

This one was embarrassing to find out: I couldn't believe I'd been doing println!("{}", val) for so many years when dbg! was an option. I do wish there was a way to ask for more compact output.

I came across this while looking through Axel Lind's solutions: primitive integers have an astonishing collection of useful functions baked in. My original solution to emulate this for an arbitrary integer was to hackily do ((val % mod) + mod) % mod instead to get a positive remainder.

There's a lot more in the primitive documentation, including several bit manipulation functions like reverse_bits, which is something else I'd implemented manually this year.

BurntSushi's regex crate is fairly famous and really fast: though I must admit to being a little disappointed that a regex implementation doesn't ship in the std library for Rust.

I ended up including a snippet using lazy_static! and Regex so that I wouldn't have to constantly look up documentation.

use lazy_static::lazy_static;
use regex::Regex;

fn parse(line: &str) -> Result<&str, Box<dyn Error>> {
    lazy_static! {
	static ref RE: Regex = Regex::new(r#"(?P<cap>.*)"#).unwrap();
    }
    let captures = RE.captures(line)?;
    let result = captures.name("cap")?.as_str();
    Ok(result)
}

Looking at Sophiebits's Python solutions, I also realized I almost never try to use a match that matches multiple times and that's something I should try more of in the future.

Itertools almost feels like cheating with all the helpful functions it provides; I imagine I'm back in Python when applying it liberally.

My favorite functions include

• cartesian product which is very useful for generating all possible neighbors for a given grid point. Instead of looping from -1..=1 twice, I can do a cartesian_product and walk over all the cells in a 3 by 3 grid. There's also the iproduct! macro for this particular use case: iproduct!(-1..=1, -1..=1).
• collect tuple is a nice convenience method to collect values into a tuple instead of a Vector.

It's been extraordinarily tempting to convert all my for loops to iterators and code-golf my solutions away to nothingness; but if I'm perfectly honest abusing iterators often makes the code more unreadable and harder to work with.

That said, some functions I found really useful include:

• .cloned() and copied(): Converts an Iter over &T to one over T.
• std::iter::once with chain(): this is particularly useful to append an extra delimiter to make sure the last row in the input is handled appropriately.
• filter_map: Good for simplifying code and making it easier to clean up a collection of Result-s and Option-s.

Finding out that this was possible helped simplify some of my solutions significantly.

This is partially well documented under Slice Patterns (which sadly don't show up when searching for "Rust Vector Patterns"). I believe the latest stable state of the world is captured in a blog post on Sub slice patterns instead (and the corresponding stabilization pull request).

A contrived example of the syntax:

fn test(nums: &[i64]) -> i64 {
    let (start, end) = match nums {
	[x0, _xs @ .., xn] => (x0, xn),
	[x] => (x, x),
	[] => unreachable!(),
    };

    start * end
}

I tried to profile my solution to Day 15: I was a little surprised to learn that benchmarks needed nightly support, and ultimately ended up settling on using Inferno to generate Flamegraphs instead.

The changes I needed to make included adding debug symbols for releases,

[profile.release]
debug = true

and then simply following instructions:

perf record --call-graph dwarf ./target/release/day15 profile
perf script | inferno-collapse-perf > stacks.folded
cat stacks.folded | inferno-flamegraph > profile3.svg

In this case I kind of knew what I was going to find: I was abusing a HashMap and not using the Entry API, so it was doing multiple lookups.

This showed up clearly in the first profile where most of my time is spent in looking up keys:

Replacing it with an entry API halved the time from 7s to 3s:

And finally I decided to trade off memory for speed and brought it down to 1s by simply using a Vec in the final solution:

Looking through other people's Rust solutions I've seen several different mechanisms for organizing repos: some people have a Cargo project per day, per part, and some of us (including me) decided to use Cargo's bin support: Cargo Targets#binaries.

This allows me to simply drop in a new file at src/bin/ every day with a corresponding [[bin]] entry in Cargo.toml.

[[bin]]
name = "day1"

[[bin]]
name = "day2"

[[bin]]
name = "day3"

...

I tried out Emacs, VSCode, and IntelliJ IDEA while solving the problems. IntelliJ was the smoothest option out of the box, particularly with default-on support for inline types and argument labels.

A little bit of tweaking allowed me to get the same functionality in Emacs with support for everything else I'm already comfortable with thanks to lsp-mode, lsp-rust-analyzer-server-display-inlay-hints and lsp-rust-analyzer-display-parameter-hints: I'll share my Rust based configuration separately.

My personal laptop is a 2012 Macbook Air running Arch Linux, so it's not particularly powerful: running OBS to record my screen at a readable resolution started causing my keystrokes to lag.

As an alternative to be able to actually look at how I perform under time constraints, I set up a few simple scripts to take a screenshot every few seconds and then stitched them together into a sped up video instead. This was surprisingly satisfying and still let me get an idea of what I was doing and how long I took to do it.

Recording my screen was as simple as running an infinite loop:

sleep 300; while true; do; maim -o "$(date)"; sleep 10; done;

ffmpeg made it nice and trivial to stitch everything together into a fast video:

ffmpeg -framerate 2 -pattern_type glob -i "*.png" -c:v libx264 -pix_fmt yuv420p video.mp4