expLog

Advent of Code

Advent of Code is an excellent annual collection of programming puzzles. It's quickly become my favorite part of the holiday season as a celebration of programming: carefully crafted puzzles, amazing solutions spanning astonishing technical stacks, beautiful visualizations – with a sense of humor and joy around it all.

The reason I recommend AoC strongly is because it's simply so much fun: there's a surreal and light-hearted Santa-themed story wound around each year's story, an amazing – and inspiring – community on Reddit; and the puzzles are generally aimed towards teaching something new. I'd strongly recommend it even if you don't generally enjoy programming competitions like Code Jam or Hacker Cup.

The format

Very briefly: a new puzzle unlocks every night at midnight, Eastern time from 1st to 25th December. Each puzzle has 2 parts, with the 2nd part generally being a more complex variation on the theme.

Inputs vary and can be large; occasionally involve ASCII art or other sentences that need to be parsed. Solutions, on the other hand, tend to be single numbers or strings that can pasted in: there's no submission of code required, so you can solve problems however you want. And people do. In mind-bending, esoteric, eccentric and delightfully twisty ways.

"Good" solutions should be able to compute the answer in 15 seconds on old hardware; interpreted languages like Python are perfectly suited to Advent of Code.

Submissions are rate limited to at most 1 per minute: otherwise one lateral solution to problems would be to simply brute force the server with multiple possible solutions.

Scores are tracked for people who manage to be the first hundred to submit their solutions; the first 1000 explicitly get a rank back on submission. The rest of us gaze in awe at their short and sweet solutions.

Advice for participants

This is as much for me in 2021 as for anyone who's somewhat unfamiliar with it; there are a couple of things I would recommend to have the most fun with the contest:

Play to learn

As satisfying as leaderboard positions can be, it's much more satisfying to truly learn from Advent of Code: depending on the year and the puzzle, I've improved my knowledge of – and fluency with – graph search algorithms, number theory, learning to choose the right data structure, and – yes – trying to program quickly and failing.

The 2-part format also encourages trading off good design and quickly hammering out something; a well thought through first answer often means a faster second answer – but it effectively trades off your rank in the first problem with your rank in the second.

Learn twice as much

Pairing Advent with a new technology that you want to adopt can also be excellent: the programs are perfectly sized to explore a language – or editor – or other tool that you would like to adopt and are an excellent mechanism to explore a wide breadth of that particular tool.

For 2018, I tried to improve my Rust but ended up significantly improving my command of C instead. For 2019, I used every single Jupyter Notebook interface I could get my hands on to understand all the amazing software out there (EIN: Emacs IPython Notebooks) ended up being the solution I enjoyed the most.

Finally, this year was a deep dive back into Rust that went fairly well – I also used this as an opportunity to try out different Rust editors: including VSCode, IntelliJ, and unsurprisingly finding my way back to Emacs – albeit with a much more pleasant configuration than the one I started with.

Compare your solutions after

Every day has a corresponding megathread in the Reddit community where people post their solutions and discuss their approaches. I inevitably find that I learn something every time I browse through the solutions – whether it's in the algorithmic approach, how to structure my solution, or some features or libraries that I simply wasn't aware of.

This is generally my favorite part of the contest – I can see how other programmers approach exactly the same problem, and learn from them. Given that I've also spent a significant amount of time thinking through the problem first I can also appreciate their solutions that much better. This is particularly valuable when exploring solutions from excellent programmers like Peter Norvig.

Write about it!

There are so many new tricks and techniques you might come across during the competition that it's hard to remember them all, let alone apply them when you next see a similar problem.

Writing about them – perhaps as notes in your code repo, tweets, blog posts, perhaps even a Substack if you're with the zeitgeist and an extrovert, or a Zettelkasten if you're an introvert – goes a very long way. I (somewhat annoyingly for any followers) tweeted my way through 2020, and regret not keeping a better record for earlier years.

Spend a lot of time on Reddit

The r/adventofcode community is pretty amazing: there's a solid collection of posts ranging from discussions on different approaches to problem solving to the best memes and everything in between.

Participating there to learn and have fun is a pretty good use of your time.

AoC++

Eric Wastl clearly crafts the problems with a lot of thought and care: which is evident in how clearly the problems are defined, with useful edge cases, and each round is beta tested be we get our grubby hands on it. There's also a significant amount of effort in making sure we don't DDOS the website.

There's a little more detail around what goes into the sausage in this video and the FAQ, and I can't even imagine the amount of work that goes into making good puzzles.

AoC++ is basically a way to get a shiny gold badge next to your name on the Advent of Code website, and also a way to support AoC with a little bit of money. I'd strongly recommend donating if you can afford to – just to have a higher chance that AoC sticks around forever (until the heat death of the universe – or thereabouts).

Important!?!! Name your files with 01, 02, 03, …

It's all fun and games till December 10th rolls around and now I * twitch * every time I see the contents of the folder.

ordering.png

Figure 1: Sigh

Resources

Blitzen

One part of Advent of Code that I dislike is having to manually save the input files, and then pass them into my solution program somehow. I ended up writing a CLI to speed me up and stop filling up my Downloads folder with input1.txt, input2.txt and so on an so forth.

Eric provides an excellent and easy to use API to fetch inputs, and submit solutions: so I wrote a small program that would fetch the input and write to stdout – which I could then pipe into my solution.

Somewhat less useful – but more cool – is the ability to submit solutions through the CLI; it can read from stdin and write to stdout. Any responses from the server are parsed into markdown and displayed in the terminal – this is particularly useful when the answer's incorrect, and the message from the server includes a hint ("Your solution is too low", or "Someone else has this exact solution").

I'd intended to make this a trivially small binary given the little work it does, but adding support for Markdown parsing blew it up to several Megabytes – which is something I'll revisit in time for the next AoC to roll around.

Excellent solutions

As I said earlier, there are some excellent programmers working through Advent of Code – occasionally focusing on readable code instead of aiming at the leader board, and it's a pleasure to look at their solutions.

The opportunity to see what others do on the same problem with similar constraints is extremely rare for me: so I really enjoy comparing my solutions with others' and learning from them.

  • Peter Norvig's Pytudes: A single, elegantly structured notebook that solves all the problems in one go. There're some very interesting generic functions that apply through all solutions for parsing and folding the outputs into solutions.
  • Sophiebits's solutions: Sophie is constantly on the leaderboard, and I'm generally floored by the terseness of her solutions. It takes me some time to figure out how those few lines of code worked.
  • Awesome Advent of Code: a massive collection of tools, templates and solutions.
  • Axel Lind's rust solutions: I found these really useful to be able to see significantly more idiomatic Rust than what I'd been writing.
  • There are also a tremendous number of people live-streaming or recording videos as they go: including Uncle Bob, Joel Grus, and several Twitch streamers – I've skimmed a few videos, but I normally don't have the patience to watch so I don't have strong recommendations.

Vignettes from AoC 2020 (Spoilers!)

The unfiltered version of this section is a Twitter thread on my account where I'd annoy my followers and record my victories and failures along the way.

Using AoC as means to polish up my command of Rust seemed like an excellent opportunity. Sadly, that also meant giving up any hope of making it to the top 100 this time around (I achieved it once in 2019!), but that's a trade I was willing to make.

What I learned from the problems

This is a collection of things I learned about from this round of AoC: your personal list will probably be very different.

A refresher in modular arithmetic, Chinese Remainder Theorem, etc.

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.

The Van Eck Sequence

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.

vaneck.jpeg

An exercise in parsing

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:

Linked lists inside an array

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.

Hexagonal grids and indexing

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.

What I learned about Rust

For the first couple of weeks I was basically trying to write Python in Rust: not really relying on the typing system, keeping all the "business" logic in my head and simply manipulating plain data structures.

After spending far too much time debugging my solution to Day 20 I decided to start leveraging the compiler instead and actually defining types and structs and enums.

dbg!

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.

rem_euclid, saturating_sub and friends

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.

Building familiarity with the Regex crate

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.

The magic of Itertools

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.

Wielding iterators with more skill

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.

Destructuring vectors (slice & sub-slice patterns, to be precise)

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
}

Profiling Rust

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:

Sorry, your browser does not support SVG.

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

Sorry, your browser does not support SVG.

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:

Sorry, your browser does not support SVG.

Organizing my solutions

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"

...

IDEs for Rust

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.

Some other tools I picked up along the way

Cheap screen recordings

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

Partial screen recordings: Peek

Peek was really useful in capturing a rough sea full of sea monsters: I suspect I'll be using it a lot more frequently at and away from work to capture snippets from my screen.

The UI was a little surprising, but extremely intuitive once I understood what was happening; using it with a tiled window manager takes a little bit more effort because it isn't initially obvious that you're supposed to move the window onto the part of the screen that you're recording.

monsters.gif

Figure 6: My blinking Day 20 solution

Thank you!

AoC wouldn't exist without Eric Wastl and his team: Tim Giannetti, Ben Lucek, JP Burke, Aneurysm9, Andrew Skalski and Danielle Lucek – thank you all so much!

At the same time, it wouldn't be half as much fun without the crazy solutions and visualizations by everyone participating in r/adventofcode – thank you all so much as well!

All the ridiculous solutions in Excel, on Gameboys, and extremely obscure languages; the extremely elegant and the extremely minimal but fast solutions; the professional animations visualizing the problems, the cartoons; and last but not least – the memes! – make it so much better than any other competition I've seen.

memes.png

Until next year!

Comments?

Discuss this post on Reddit, message me on Twitter or email.

view source