Advent of Code 2023: Day 09

Code for solutions available on GitHub.

Another post under the influence of covid. Like day 8, I’ll be brief.

Mirage Maintenance

This is a pretty simple one. The input is a list of time sequences:

0 3 6 9 12 15
1 3 6 10 15 21
10 13 16 21 30 45

And our job is to predict the next number for each sequence and sum up the values of all predictions. A prediction is made by repeatedly taking a discrete derivative of the sequence until reaching a constant state, predicting the next value of that, then bubbling up. See the actual problem description for a really good explanation of the problem. I feel like I can’t reword in in a better way than the problem was already put.

Basically, If we have a sequence of all zeroes, the next value will be zero. If this is not the case, we create a new sequence from the pairwise difference of numbers in the sequence, predict the next value of that, and the next value of the current sequence is the last value plus the predicted value of the sequence of differences. Here’s the function that does just that (with help from the itertools crate):

fn predict_value(values: Vec<i32>) -> i32 {
    if values.iter().all(|x| *x == 0) {
        return 0;
    }

    let lower_sequence = values
        .iter()
        .tuple_windows()
        .map(|(a, b)| b - a)
        .collect_vec();
    let last = values.last().unwrap();
    predict_value(lower_sequence) + last
}

That’s it. That’s the puzzle.

Part 2

Part 2 asks to predict a value backwards in time, i.e. what was the value before the first? Just reverse each sequence and call the same function.