Advent of Code 2024: Day 01

Another year, another Advent of Code. Same deal as last year. Code here. Diving straight into it.

Historian Hysteria

The lore for this year is that we’re looking for the Chief Historian. Today we’re checking his office but he’s not there. What is there, though, is a bunch of notes about historically significant locations, each marked with an ID. The other historians split into two groups and each gathered a list of all these historical places and IDs. The two resulting lists of numbers are then held up side by side.

3   4
4   3
2   5
1   3
3   9
3   3

This is the example input given. Part 1 theorizes that these two lists are similar, but only off by a small amount. So we should compare them by finding out the distance between the smallest IDs in each list, the second smallest, etc. Then we can sum up all the distances and see just how different each list is. I won’t bother with documenting parsing the input. For the sake of this, just assume that we have two sorted lists a and b of numbers (Vec<u64> (yes, I’m doing this in Rust again)). Then this is the entire solution to part 1:

a.into_iter()
    .zip(b)
    .map(|(x, y)| x.abs_diff(y))
    .sum()

Part 2

The difference between the lists is pretty large, so it seems like they are very different. But a lot of numbers appear in both lists. This time we need to calculate a similarity score between the two lists. The score is defined by for every number in the left list, multiply its value by the number of times it occurs in the right list, then sum up the result. A naïve solution would look something like this:

a.into_iter().fold(0, |acc, x| {
    acc + b
        .iter()
        .skip_while(|y| x != **y)
        .take_while(|y| x != **y)
        .count() as u32
        * x as u32
})

And it works. Takes between 500-800 microseconds (including input parsing) on my machine, depending on cache warmup and such. But it’s doing a lot of unnecessary work. Iterating through b, skipping elements, taking elements, etc. A key insight is that if we could group each list into sub-lists only containing equal elements, we can use the length of the sub-lists to multiply together with their value if both are non-empty. That’s a lot of words, so an example is in order. Taking the example given above, imagine that a and b were instead this:

let a = [[1], [2], [3, 3, 3], [4]];
let b = [[3, 3, 3], [4], [5], [9]];

(This is not valid Rust, just an example).

Now, calculating the similarity for each of, for example, the number 3 is a single operation. You multiply 3 by the length of its sub-list in b, and the length of its sub-length in a, since that’s how many times you would do it naïvely in the first version of this solution. We can achieve exactly this with the use of Vec::chunk_by!

let a = a.chunk_by(std::cmp::PartialEq::eq);
let b = a.chunk_by(std::cmp::PartialEq::eq);

Now a and b are iterators which returns sub-lists where all elements have the same value. Since a and b were initially sorted, the sub-lists will contain all such elements.

The rest of the code is a bit longer than the naïve solution, but it runs in about 100 microseconds on my machine, a factor of 5-8 faster! And also roughly the same speed as the solution to part 1!

let a = a.chunk_by(std::cmp::PartialEq::eq);
let mut b = a.chunk_by(std::cmp::PartialEq::eq).peekable();

let mut similarity: u64 = 0;
for chunk in a {
    let elem = chunk[0];

    while b.peek().is_some_and(|c| c[0] < elem) {
        b.next();
    }

    if b.peek().is_some_and(|c| c[0] == elem) {
        let other = b.next().unwrap();
        let n = other.len() as u64;
        let m = chunk.len() as u64;
        similarity += elem * n * m;
    }
}

b has to be a peekable iterator, so .peekable() is called on it. Then each chunk in the left list (a) can be compared to chunks in the right list (b). Since they are sorted, we skip all sub-lists whose values are less than the current left sub-list we’re looking at¹, and then check if the next sub-list has the same elements as the current left sub-list². If that is the case, we do the simple multiplication and add on to the similarity score. Otherwise we just move on to the next sub-list and repeat.

Full code listing for today.

Update, a couple of hours later

I switched my parsing from manual to using the nom crate. This halved the runtime of both parts down to around 50 microseconds from 100.