Owen Gage

Advent of Code 2025

I've been attempting Advent of Code for several years now with varying success. This article is a short retrospective on this year's.

Growing helper library

A year or so ago I decided to start building up a helper library to solve challenges. I wanted to make sure these:

Dense 2D grids

Working on a dense two-dimensional grid is very common, but the space this grid sits on can change. The edges may wrap around like a torus, they may act as actual boundaries, or they may form a cube or have other complex wrapping.

I handle this by making my DenseField<T> type be agnostic to this boundary issue. It holds a Vec<T> of the cells of the grid, but then provides different methods for accessing that grid with different topologies.

For example I have a simple get(x,y) function for a bounded grid, and wrapping_get(x,y) that will automatically wrap around the coordinates treating the surface like a torus.

Accessing the 'neighbours' of a cell is common as well, so I provide many methods for accessing different numbers of neighbours for different topologies:

Here is the first for example:

pub fn neighbours8_bounded(&self, p: IPoint) -> impl Iterator<Item = (&T, Point<isize>)> {
    let Point { x, y } = p;
    let p = |x, y| (self.try_get(pt(x, y)), Point::new(x, y));
    [
        p(x - 1, y - 1),
        p(x, y - 1),
        p(x + 1, y - 1),
        p(x - 1, y),
        p(x + 1, y),
        p(x - 1, y + 1),
        p(x, y + 1),
        p(x + 1, y + 1),
    ]
    .into_iter()
    .filter_map(|(nei, p)| nei.map(|nei| (nei, p)))
}

This takes care of a lot of common mistakes when solving problems, such as

Here is an example from 2025 day 7 of it's usage:

#[derive(Clone, Copy, PartialEq, PartialOrd, Eq, Ord)]
enum Cell {
    Empty,
    Start,
    Splitter,
    Beam(usize),
}

impl From<u8> for Cell {
    fn from(v: u8) -> Self {
        match v {
            b'.' => Cell::Empty,
            b'^' => Cell::Splitter,
            b'S' => Cell::Start,
            b'|' => Cell::Beam(1),
            _ => panic!(),
        }
    }
}

fn main() {
    let input = lines(fetch_input(2025, 7));
    let field = DenseField::<Cell>::from_lines(input);
    let start = field.find(&Cell::Start).unwrap();
    // ...
}

The parsing of input using the From trait makes getting set up to actually solve the problem quick, and quickly moves us to meaningful structures rather than ascii characters.

DenseField has a lot of methods, but it's easy to pick the correct one for the given problem, and saves on a lot of the tedious code to find and filter out neighbouring cells. These methods have plenty of assertions in as well that help catch issues with my solutions.

There are a few extra helpers, like an iterator for all points on a grid with control over row/column first, parsing a grid from text, and rotating a grid. I add more as required.

Quite a few problems exist that are on a 'sparse' grid, and often a potentially infinite one. I have no general structure for this and typically use a standard container of IPoint objects which simply combine the isize x and y coordinates.

Parsing

Parsing input is a required part of every problem. Advent of Code is unique in that you can fully expect your input to be well formed. This means you can judiciously use things like panic!() and .unwrap() without consequences. The parsing helpers I have reflect this. Production code would obviously have to actually handle this. Don't judge me!

Probably my most useful helper is my string extension trait:

pub trait StrExt {
    fn strip_brackets(&self, left: char, right: char) -> Option<Self>
    where
        Self: Sized;

    fn split_parse<T: FromStr>(&self, pat: &str) -> impl Iterator<Item = T>
    where
        T::Err: Debug;

    fn split_once_parse<T: FromStr>(&self, pat: &str) -> (T, T)
    where
        T::Err: Debug;

    fn split_parse_n<const N: usize, T: FromStr>(&self, pat: &str) -> [T; N]
    where
        T::Err: Debug;
}

These methods embody the panicing idea, with implementations over spiced with unwrapping. But a single call can take a string and return a fixed or dynamic number of parsed objects. For example here is split_parse_n being used to parse 3D coordinates:

let coords = input
    .into_iter()
    .map(|s| {
        let [x, y, z] = s.as_str().split_parse_n::<3, isize>(",");
        Vec3 { x, y, z }
    })
    .collect_vec();

These helpers along with the typical ones for automatically fetching input files with the API make getting started much easier.

New addition: Disjoint set

One problem this year was 'optimally' solved with a data structure called a Disjoint Set which I had not come across before. Very briefly it stores a collection of items, where each item belongs to exactly one set. It does this by forming a tree for each set, with the root element acting as the identity for that set.

Doing traditionally non-mutating operations on this object actually mutate the trees to make them more shallow, improving operations like merging and finding the sets an element belong to.

This probably won't come in useful often, but was so generic it seemed pointless to hide it inside the code for a single day. In the end it wasn't that much faster (~20%) than a naive Vec<HashSet<T>> implementation. That would likely change with the scale/flavour of the problem however.

Day 10

This day was the biggest challenge for me. I only solved it by finding an algorithm explained on the sub-reddit. This happens most years--I'm not a computer scientist by training.

That said, I'm always keen to learn some more mathematics or computer science. It turns out this day is quickly solved with SMT solvers. I found the text book Decision Procedures that supposedly teaches this topic, and so I have a self-bought Christmas present on the way.

Book cover for Decision Procedures, an algorithmic point of view, second edition

Hopefully I can go back and implement a minimal SMT solver for this day, and maybe make it generic enough for future problems.

Quick Rust thoughts