Advent of Code 2024: Day 02

Code for solutions available on GitHub.

Red-Nosed Reports

The puzzle for today is pretty simple. The input is a list of sequences of numbers, like this:

7 6 4 2 1
1 2 7 8 9
9 7 6 2 1
1 3 2 4 5
8 6 4 4 1
1 3 6 7 9

The task for part 1 is to determine how many of these lines are safe. Being safe is defined as:

• The sequence is monotonically increasing or decreasing.
• The difference between each pair of numbers is at least 1 and at most 3.

If the input is parsed into a Vec<Vec<u64>>, it’s pretty simple to figure out if a sequence is safe. Thanks to the wonderful .windows method on slices, which iterates over contiguous sub-slices in an overlapping manner:

[1, 2, 3, 4].windows(2)
    -> [1, 2], [2, 3], [3, 4]

So iterating over the outer Vec, filtering the inner Vecs (taking advantage of the fact that &Vec<T> is essentially &[T], a slice) that are safe, and counting how many we have left, we get our answer. The filtering function I decided to write like this:

fn is_safe(levels: &[u64]) -> bool {
    let safe_differences = levels
        .windows(2)
        .all(|w| (1..=3).contains(&w[0].abs_diff(w[1])));
    let increasing = levels.windows(2).all(|w| w[0] < w[1]);
    let decreasing = levels.windows(2).all(|w| w[0] > w[1]);

    safe_differences && (increasing || decreasing)
}

Which can then be used to get the answer like this:

sequences.into_iter().filter(|s| is_safe(s)).count()

Very simple.

Part 2

For part 2, there’s a twist, as always. This time a sequence can be safe if it fulfills the above criteria or if it can be made to fulfill the criteria by removing one single element. One example given is that the sequence

1 3 2 4 5

can be made safe by removing the 3.

There are simple and more complex ways you might go about this. I chose the simple way of just trying to remove one element at a time if the original sequence was not safe. This ends up being O(n^2) in time, but the inputs are so small and I had A Day at work today so I didn’t feel like engineering something more clever. As such I won’t reproduce the code here since it’s just more of the same. Instead I want to move on to something I learned while coding it up!

Range slicing quirk

In Rust, you can slice a… well… slice by a range. That is, get a sub-slice of a by indexing it like a[i..j] where i is the starting index (inclusive) and j the ending index (exclusive). The end index can be at most a.len(), otherwise the slicing panics. If both indices are equal, you get an empty slice back. But a small detail, mentioned in the docs, is that a.len() is a valid starting index for slicing with a range like this.

This is because the implementation of this only checks that the ending index is not less than the starting index, and that the ending index is less than or equal to the length of the slice. Less than or equal, since it is an exclusive index. The consequence of this is that range slicing is not quite the same as indexing, even though they use the same square bracket syntax¹.

Here’s a simple code summary of the difference between the two:

let arr = [1, 2, 3];
println!("{:?}", &arr[arr.len()..]); // OK. Prints "[]".
println!("{:?}", arr[arr.len()]); // Panic! Out of bounds!

So I learned something new today. :)