Advent of Code 2020 in Rust day 3: nested iterators

Given a square input of . and # where # represent trees, find the number of trees in the path for a given (x,y) slope.

process_slope(input, (3, 1))

The input comes in as such:

..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#

Once again we can take advantage of iterators to solve both part 1 and part 2. .lines() gives us an iterator over each row. The slope (our tuple) gives us the step values for the x and y. We start at 0 and each step moves down to the step * y row, so we can take advantage of step_by(y) to step through the rows.

fn process_slope(input: &str, (x, y): (usize, usize)) -> usize {
    input
        .lines()
        .step_by(y)
        .enumerate()
        .filter_map(|(step, row)| match row.chars().cycle().nth(step * x) {
            Some('.') => None,
            s => s,
        })
        .count()
}

Then, because we don't have the "x index" yet for the current step, we can enumerate to yield the step number and use that with the x step value to get the x index for the current step.

As we're iterating over the enumerated rows, we can iterate over each row individually as well to extend the row as far as we need to, since the slope may take us farther "right" than the grid we were given. To do this we can set up a .cycle() which will allow us to repeat the row we were given over and over as many times as we need to. This allows us to pick off the nth index of the iterator from that cycle.

Performance

We're running at about 165 microseconds with this code, which I'm fairly happy with considering the maintainability of it.

There is one optimization that Rust doesn't do for us though. The current implementation takes advantage of the fact that &str's Clone implementation won't allocate on each iteration, but we still call .next() on the iterator step * x times. This is due to iterators potentially having side effects which makes it hard to optimize.

The alternate approach is that since we know we'll cycle and that we know we don't need any of the intermediate values, to use remainder. In Rust the remainder operator is % and it lets us take the cycle out of the row.chars() iterator, skipping directly to the nth.

fn process_slope(input: &str, (x, y): (usize, usize)) -> usize {
    input
        .lines()
        .step_by(y)
        .enumerate()
        .filter_map(|(step, row)| match row.chars().nth((step * x) % row.len()) {
            Some('.') => None,
            s => s,
        })
        .count()
}

This brings us all the way down to 21 us, so clearly worth doing if we cared about microsecond level optimizations or if this was in a hot loop.

| example | lower bound | best guess | upper bound | | ------------- | ----------- | ---------- | ----------- | | process_slope | 164.55 us | 165.29 us | 166.04 us | | remainder | 20.916 us | 21.39 us | 21.189 us |