Given a square input of
# represent trees, find the number of trees in the path for a given
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.
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.
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
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
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|