Advent of Code 2021 Day 01

Source code for this solution can be found in the associated GitHub repository.

Part 1 #

The first challenge requires finding out how many times the values in a list increase from the number before it. For example, with the following sample input we can see that the values increase 7 times:

199 (N/A - no previous measurement)
200 (increased)
208 (increased)
210 (increased)
200 (decreased)
207 (increased)
240 (increased)
269 (increased)
260 (decreased)
263 (increased)

Let’s use this sample data to create a program in src/bin/day01a.rs that will solve the challenge! Let’s handle the cases where there are only zero or 1 measurements; we’ll return a 0.

fn calculate_increase(_measurements: Vec<usize>) -> usize {
    0
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn zero_measurements_has_no_increase() {
        let measurements = Vec::new();

        let increase = calculate_increase(measurements);

        assert_eq!(0, increase);
    }

    #[test]
    fn one_measurement_has_no_increase() {
        let measurements = vec![199];

        let increase = calculate_increase(measurements);

        assert_eq!(0, increase);
    }
}

Great! Now let’s handle the following 3 cases, each with 2 measurements:

• an increase from 1st to 2nd measurement.
• no increase from 1st to 2nd measurement.
• a decrease from 1st to 2nd measurement.

Since all 3 cases will pass with the same implementation, we’ll write all 3 tests in one go:

#[test]
fn increase_from_measurement_1_to_2_is_an_increase() {
    let measurements = vec![199, 200];

    let increase = calculate_increase(measurements);

    assert_eq!(1, increase);
}

#[test]
fn no_change_from_measurement_1_to_2_is_not_an_increase() {
    let measurements = vec![199, 199];

    let increase = calculate_increase(measurements);

    assert_eq!(0, increase);
}

#[test]
fn decrease_from_measurement_1_to_2_is_not_an_increase() {
    let measurements = vec![201, 200];

    let increase = calculate_increase(measurements);

    assert_eq!(0, increase);
}

To get these tests to pass, we need to amend the calculate_increase function. We’ll iterate over the range of the measurements starting from the second entry. This allows us to compare against the previous entry; the guard clause ensures we don’t try to access non-existant elements.

fn calculate_increase(measurements: Vec<usize>) -> usize {
    let mut increase = 0;

    if measurements.len() >= 2 {
        for i in 1..measurements.len() {
            if measurements[i] > measurements[i - 1] {
                increase += 1;
            }
        }
    }

    increase
}

With this in place, we should be able to check our implementation against the sample measurements:

#[test]
fn given_list_of_sample_data_calculates_increase_of_7() {
    let measurements = vec![199, 200, 208, 210, 200, 207, 240, 269, 260, 263];

    let increase = calculate_increase(measurements);

    assert_eq!(7, increase);
}

The final step is to load the real measurement data from file and compute the actual increase. We’ll save the measurements in ${projectRoot}/data/day01a.txt and to avoid dealing with path issues we’ll include_str!. Let’s see what the implementation looks like:

fn main() {
    let raw_measurements = include_str!("../../data/day01a.txt");

    let measurements = raw_measurements
        .trim()
        .split('\n')
        .filter_map(|m| str::parse::<usize>(m).ok())
        .collect();

    let increase = calculate_increase(measurements);

    println!("{}", increase);
}

let measurements = raw_measurements
    .trim()
    .split('\n')
    .map(str::parse::<usize>)
    .filter(|m| m.is_ok())
    .map(|m| m.unwrap())
    .collect();

Sometimes collect requires us to specify the type to be collected into. This is needed if the compiler cannot infer the type, which in our case it can.

With this in place, we can run the tool:

cargo run --bin day01a
1154

⭐️, now let’s look at the second part of the task.

Part 2 #

In this part of the challenge, we need to compare a sliding window of 3 measurements over the same list of measurements. Given the previous sample data, our sliding window data would yield the following sums, with 5 increases:

A: 607 (N/A - no previous sum)
B: 618 (increased)
C: 618 (no change)
D: 617 (decreased)
E: 647 (increased)
F: 716 (increased)
G: 769 (increased)
H: 792 (increased)

I’d like to reuse as much of the previous code as possible. The first thing we’ll do is extract the calculate_increase function and tests into a day01.rs library. We need to remember to make the function pub and export it from lib.rs. With these changes in place, we’re almost ready to start updating our implementation. However, I want to make two more changes that will prevent our existing tests and implementation from breaking. The first is to add a calculate_increase_windowed function and delegate to it from calculate_increase:

pub fn calculate_increase_windowed(measurements: Vec<usize>, _window_size: usize) -> usize {
    let mut increase = 0;

    if measurements.len() >= 2 {
        for i in 1..measurements.len() {
            if measurements[i] > measurements[i - 1] {
                increase += 1;
            }
        }
    }

    increase
}

pub fn calculate_increase(measurements: Vec<usize>) -> usize {
    calculate_increase_windowed(measurements, 1)
}

Next, we’ll make some changes to the logic in our calculate_increase_windowed function to use the windows method on a slice. We can set the window size to 1 and keep the functionality exactly the same as when we finished Part 1]:

pub fn calculate_increase_windowed(measurements: Vec<usize>, window_size: usize) -> usize {
    let mut increase = 0;
    let mut last_measurement = None;

    for m in measurements[..].windows(window_size) {
        let window_sum = m.iter().sum::<usize>();
        if let Some(last_sum) = last_measurement {
            if window_sum > last_sum {
                increase += 1;
            }
        }
        last_measurement = Some(window_sum);
    }

    increase
}

As can be seen, our implementation has changed a little bit. We now keep track of the last_measurement and iterate over a window in a slice of measurements. The windows method only exists on slices, not a vec. We use one of Rust’s many functional tools to calculate the sum of window. Then we compare the window_sum with the last_sum and increment the increase when the conditions are right. Using the Option is a convenient way to keep track of whether we’re comparing against the first sum or a subsequent value. All our tests should still be passing and the day01a binary should still result in the correct increase. However, we’ve now made the necesary changes to make our update to use a window of 3 an easy change. Let’s write a test and get to it!

#[test]
fn given_list_of_sample_data_with_window_of_3_calculates_increase_of_5() {
    let measurements = vec![199, 200, 208, 210, 200, 207, 240, 269, 260, 263];

    let increase = calculate_increase_windowed(measurements, 3);

    assert_eq!(5, increase);
}

And if we run the test… straight to green! That’s right. Our refactoring was into an implementation that works for the second task straight away. We could have been a bit more deliberate and waitied to introduce the calculate_increase_windowed function. However, I don’t think there’s anything wrong with introducing that earlier.

All that remains is to add src/bin/day01b.rs and call our new function. Apart from that change, it’s the same as day01a.rs.

use aoc_2021::day01::calculate_increase_windowed;

fn main() {
    let raw_measurements = include_str!("../../data/day01a.txt");

    let measurements = raw_measurements
        .trim()
        .split('\n')
        .filter_map(|m| str::parse::<usize>(m).ok())
        .collect();

    let increase = calculate_increase_windowed(measurements, 3);

    println!("{}", increase);
}

Which we can run:

cargo run --bin day01b
1127

So, great success, let’s reward ourselves with another ⭐️.