Day 1: Sonar Sweep
Advent of Code (AoC) 2021, starts with the Sonar Sweep. You can read the problem statement on their website.
Day 1 problems are usually simple, and it is really all about how fast can you solve it.
In case you have never done AoC, it lasts for 25 days. Each day a new challenge is released. Each challenge has two parts, and you complete each one by providing an answer, usually a number. Your code doesn't really matter, only the answer.
For part one, all we have to do is parse the input into integers, and measure the rate of change from top to bottom. Once we have the rates of change, we count how many of these are positive.
Consider this input:
199 200 201 200
From top to bottom, the rates of change are
1, 1, -1. The first entry of the input has nothing to be compared with. For an input of size
n-1 rate of change.
At this point, one might rush and try to iterate over the input like so:
While this works well for part one, in part two, one has to consider rates of change between windows, of size 3. At this moment, if you want to finish fast, you ought to realize, that part one is just the same, but with windows of size 1.
In Rust there's a method to sum a list of integers, conveniently called,
sum. Let's tweak the previous code to work with windows of size 1.
index - 1 + 1, and
- (1 - 1), should really bother you, but that's the key part, these two depend on the window size,
n. Let's change that to 3.
And you are done! What's the time on the clock?!
Iterators have a very neat method called
scan, to which you provide an initial state, and a closure. The neat part is that
scan keeps an internal state, while yielding elements into a new
There's a few things going on here, let's walk backwards, like a crab. The
count method, well, lets us know how many elements are left after we run the
filter method. The
filter method, in this case, it's simply keeping true values generated from
scan. It doesn't do any calculations of its own.
As said before,
scan yields a new iterator, while keeping internal state. The elements on the new iterator are the result of comparing two elements. As the
scan moves over the
rows, each element is compared with,
rows[*state], where state starts at zero, and is increased by one every time.
Finally, we run the
scan only over a
rows iterator that starts from the second element.
Here comes the great insight.
While trying to solve the problem as fast as possible, we missed out on a fact. The difference of two windows, of any size, it's equal to the difference of the non-common terms. That is the first element of the first window, and the last element of the second window.
D + C + B - (C + B + A) = D - A
So, to solve part two:
We just need to start the same process from the fourth element on the
rows vector, index 3.
What's wrong with for-loops?
Absolutely nothing, the above just helps us to explore the available APIs on iterators, while also increasing our confidence in using Rust closures as first class citizens.
The for-loop that helped us at 6 am, could've been:
At the end of the day, these things boil down to experience, cleverness, language proficiency, and why not, how excited were you about solving AoC once again!