AoC 2021 - Day 1

# 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.

## 6 am

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` there's `n-1` rate of change.

At this point, one might rush and try to iterate over the input like so:

``````let inputs = aoc::get_input(2021, 1);

let rows = inputs
.trim()
.split("\n")
.map(parse_num::<u32>)
.collect::<Vec<_>>();

for index in 1..rows.len() {
answer += if rows[index] > rows[index - 1] { 1 } else { 0 };
}``````

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.

``````for index in 1..rows.len() - (1 - 1) {
let current: u32 = rows[index..index + 1].iter().sum();
let prev: u32 = rows[index - 1..(index - 1 + 1)].iter().sum();

if current > prev {
}
}``````

The `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.

``````let n = 3;
for index in 1..rows.len() - (n - 1) {
let current: u32 = rows[index..index + n].iter().sum();
let prev: u32 = rows[index - 1..(index - 1 + n)].iter().sum();

if current > prev {
}
}``````

And you are done! What's the time on the clock?!

## 6:30 am

In Rust, `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 `Iterator`.

Ah, what?

``````let compare = |state: &mut usize, curr: &u32| {
let result = *curr > rows[*state];
// mutating the internal state
*state += 1;
// yield to the new iterator
Some(result)
};

let part_one = rows[1..]
.iter()
.scan(0usize, compare)
.filter(|x| *x)
.count();``````

## Really, what??

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:

``````let part_two = rows[3..]
.iter()
.scan(0usize, compare)
.filter(|x| *x)
.count();``````

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:

``````let mut n = 1;

// part one
for index in n..rows.len() {
answer += if rows[index] > rows[index - n] { 1 } else { 0 };
}

// reset variables
n = 3;

// part two
for index in n..rows.len() {
answer += if rows[index] > rows[index - n] { 1 } else { 0 };
}