My approach to Advent of Code puzzles

Each year in December, I take part in the Advent of Code. It's a nifty coding advent calendar: each day from 1 December until Christmas, there is a new puzzle that can be solved through programming.

The puzzles all have more or less the same shape. You download some text input file. The puzzle will involve reading that input file and processing it in some way (it's strongly recommended that you write a program for this). At the end, the answer is some single word or number. To complete the puzzle, you type your answer into the Advent of Code website. Any program you write will only need to run on your computer, so you have complete freedom in terms of what programming language you use, how you prepare before hand, or even if you have manual steps like changing the input file to make it easier to work with.

There's also a story, where you're solving all of these puzzles to save Christmas! The first year I took part in was 2016, which told the story of recovering critical pieces of Santa's sleigh which were stolen by the Easter Bunny! Another year, we had to shrink down and go into Santa's broken printer, which he needs to print the naughty and nice list. This year told the story of going through the North Pole's elaborate weather machinery to ensure that it would snow on Christmas. It really leans into that fantasy where you use a skill you just learned to save the day.

I do this every year primarily because I enjoy it. A few friends of mine also participate every year, so how we each solved the day's challenge is a fun conversation topic. There are also benefits like practicing problem solving skills around data structures and algorithms. It's a bit different from what I get to do most days at work, and I enjoy getting to stretch that part of my brain. Not to mention that it's really useful to have those algorithm skills fresh when they do become necessary!

Since I've been doing this for a few years, I've settled into a pattern about how I approach these puzzles. Even though it's still programming, the nature of the problems means that the approach is quite different from how I would usually write software. In this article, I'm going to discuss what that approach is, the tools and libraries I use to support my process, and how that differs from writing production code.

Since I know more or less the shape of the problem, there's some work that I can do the night before.

All of the tools I might need should be installed. All the relevant Rust compiler toolchain stuff is running. My IDE (Emacs) is ready to write Rust. The appropriate Rust Analyzer plugin stuff is working.

Before the first challenge, I also create a new Cargo project for the year. It's one Cargo project, with an empty file in the src/bin directory for each day. So in preparation for day 1, src/bin/day_1.rs should exist and have a main function. If you haven't encountered having multiple binary targets in a Cargo project before, you can build and run extra executables in the src/bin directory with cargo run --bin day_1.

I can't do much more without knowing the problem.

The first thing I do is read and enjoy the story! I know that some people are racing for time, and for them it makes sense to skim over and skip the story. I'm usually only starting a few hours after the problem came out (the problems come out as the kids are waking up), so I may as well take my time and enjoy the story when I get to it.

For the problem part, it's important here to make sure that I understand the problem to solve. Make sure I understand what the input represents, the output that I need to find, and make sure that I can see how the examples get from input to output.

Pretty much all programs can be thought of in terms of input, processing, and output. For Advent of Code problems, that input usually starts life as a text file in some custom format. However, the processing step is almost always easier if that input is in a nice data structure.

The first step in my coding process is to figure out what the "nice data structures" to represent my input would be. In Rust terms, this means writing a few structs and enums. If there are numbers, they should usually be some number type. For example, if it's a positive integer, then it should be something like a u32. Relationships between different entities would usually be some combination of maps, sets, and vectors.

For example, for Day 4 last year, the input was a list of scratchcards, each with a set of winning numbers and a list of numbers that appear on the scratchcard.

Card 1: 41 48 83 86 17 | 83 86  6 31 17  9 48 53
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19

This is the set of structs that I wrote. The newtype pattern for the top level collection is mostly so that I can think in terms of writing a parser later that returns a Scratchcards, and so that I can associate functions with the top level Scratchcards type.

#[derive(Debug)]
struct Scratchcards(Vec<Scratchcard>);

#[derive(Debug)]
struct Scratchcard {
    winning: BTreeSet<u32>,
    owned: BTreeSet<u32>,
}

The next goal is to write the code which takes the puzzle input and parse it into those data structures we've designed. These days, I generally use a library called Nom to do so.

Nom is a "parser combinators library", which is a fancy way of saying that it's a library which provides a bunch of parsers. Some of those parsers recognise certain symbols, like a number.

Other parsers are "combinators", which take other parsers and combine them together. For example, the separated list parser takes two parsers: one for reading items we're expecting a list of, and one for reading the separator between items. separated_list1(space1, u32) is a parser which will read a list of unsigned 32 bit numbers, separated by whitespace. Since it's also a parser, I can pass it to other parser combinators until I eventually have a parser which reads my whole file.

Something important to remember is that this parser doesn't have to be clean, and it doesn't have to be perfect. If it reads the input file in front of me correctly, that's good enough. It never actually needs to parse any other file. That's one of the fun ways that Advent of Code problems feel different from my normal day to day programming.

This is what the parser looks like for the input above:

impl Scratchcards {
    fn parser(input: &str) -> IResult<&str, Self> {
        map(
            separated_list1(line_ending, Scratchcard::parser),
            Scratchcards,
        )(input)
    }
}

impl Scratchcard {
    fn parser(input: &str) -> IResult<&str, Self> {
        map(
            tuple((
                tag("Card"),
                space1,
                u32,
                tag(":"),
                space1,
                separated_list1(space1, u32),
                space1,
                tag("|"),
                space1,
                separated_list1(space1, u32),
            )),
            |(_, _, _, _, _, winning, _, _, _, owned)| Scratchcard {
                winning: winning.into_iter().collect(),
                owned: owned.into_iter().collect(),
            },
        )(input)
    }
}

If I were writing production code, then I absolutely should write unit tests for that parser. In real production code, I should also think carefully about all of the potential error cases, and how I could have nice actionable error messages. I'd probably also refactor that massive tuple where I'm ignoring most of the fields! However, this is Advent of Code, and it only ever needs to work on the one input I have in front of me. I find it more effective in this case to simply print the parsed input to the console and check it manually against my expectations from looking at my input.

fn main() {
    let input = fs::read_to_string("inputs/day_4.txt").unwrap();
    let scratchcards = Scratchcards::parser(&input).unwrap().1;
    dbg!(&scratchcards);
}

If it parses the input in front of me, it's good enough to move on to the next step.

The next step is to take the nicely parsed input, and write the code to transform it into the output. Every day is different, so I don't have a formula for this part, but I do have some general rules of thumb:

• I try the obvious or naive solution to the problem first, especially in part 1. Often, a simple solution will work in part 1, and then I can focus on a more complex solution after I know what twist part 2 will put on the problem.

• If I think some condition will probably always hold, I put an assertion into the code (assert!, assert_eq!, unreachable!, or even just panic!). If I'm wrong, the program will panic with a stack trace, and I can figure out why. This isn't production code, it's Advent of Code, and so it doesn't matter if my program crashes.

• Calling unwrap or expect on potential errors or optional data which will probably always be there is fine in this case too. It's just another assertion, which will crash the program with a stack trace if I'm wrong.

• If I'm feeling uncertain of a step, I print some meaningful debugging output and check it manually. It's often also useful to visualize the problem.

• It can help to search for algorithms or data structures that match the shape of the problem. It really helps to know that there are well known algorithms for finding things like the shortest path between two points. Talking to other people about how they solved a day's problem afterwards can be a great way for me to develop my knowledge of what algorithms are out there.

On the top level, my main function ends up looking more or less the same every day. Read the file, parse it, then call some functions on the parsed data struct to get the answer and log it out. The dbg! macro is great for this sort of thing, because it prints both the code and the result, so I can easily see which is the part 1 and part 2 answers.

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let input = fs::read_to_string("inputs/day_4.txt").unwrap();
    let scratchcards = Scratchcards::parser(&input).unwrap().1;
    // This is the part 1 answer
    dbg!(&scratchcards.points());
    // This is the part 2 answer
    dbg!(&scratchcards.scratchcard_explosion_sum());
}

After coming up with the answer, we're good right? Well, let's talk about some of the common cases where things go wrong.

A common pattern for Advent of Code puzzles is to have the first part be fairly straightforward to implement, and then second part is the same but with a bigger input. Maybe I'll need to count the number of squares that are inside an small area in part one. Since I usually start with a naive solution, my first solution goes over the area and counts the squares one by one. Then part two needs me to do the same thing for a very large area, too large to actually count the squares individually.

When I run into these problems, usually how it manifests is that my program will be technically correct, and work for the small example input, but when I use the big input it runs forever!

Let's look at some common solutions to this:

• Usually it makes sense to look at my input, and think about how many iterations my current solution needs to do. Maybe even do some simple calculations to try to figure out how many iterations I'd need. Once I've spotted where there are impossibly many iterations, it gives a deeper understanding of what part of my current solution isn't working.

• Is there some way to jump straight to the solution without doing any of those iterations? In some problems, there are mathematical tricks that I can use. In the "counting the number of squares in a big area" example, there are mathematical formulae to find the area of a polygon given its vertices. A commonly useful formula is figuring out the lowest common multiple of a few numbers. In my opinion, the point of Advent of Code is to learn things, so it isn't cheating to turn to DuckDuckGo and research standard algorithms for the situations you encounter.

• Often, a technique called memoization is the answer here. Basically, it's a fancy word for saying that I break the problem into smaller subproblems, and then cache the results of the subproblems as my program encounters them. The broader class of algorithms to be aware of here is called Dynamic programming.

• It can be useful to add some intermediate logging to see how long the program will actually take to run. If my solution would take 10 minutes to run, I can probably get to an immediate answer through microoptimizations (or spend 10 minutes making a cup of tea instead, this program only needs to run once). When I say microoptimizations, I mean optimizations that don't actually affect my overall algorithm but make the way I carry out my algorithm more efficient. Things like using integers for IDs instead of strings, cutting down on cloning large slices of dta, using bitsets if they're appropriate, or data structures that perform better with my solution.

It happens. Sometimes, I confidently enter an answer, only to be told that "sorry, the answer you gave is too high". So, how do I deal with this?

• First, I write down my wrong answer, and any other feedback the system gave me like if it was too high or too low. That will help me avoid submitting the same answer again, or submitting an answer that is even more wrong!

• Most problems have an example input and output. If I put the example input into my program, do I get the example output? This will let me find my bug with a much smaller input.

• I log a bunch of intermediate values, and check them manually to see if that's what I expected to see. This is much easier with the smaller example input.

• For more fiddly problems, here is where I might bring in a few unit tests to check that smaller parts of my solution work as they expect.

• As I'm tracing through, if I encounter assumptions that I've made, I add assertions to my code. Rather crash the program highlighting my bad assumption than proceed to give a wrong answer.

• I also read the problem again carefully. Sometimes at this point I realize that I misread part of the problem or how to handle an edge case.

Hopefully, after trying these things, I've found my mistake and get the right answer!

Hopefully at this point, I've found the correct answer and are enjoying those two yummy gold stars.

And all that is left is to wait for the next day, the next two challenges, and the next two gold stars.

I hope that my process has helped you to think through what your own process is, and maybe given you something to think about.

And I hope that you, like me, are looking forward to Advent of Code next year!