## Source: Day 9: Mirage Maintenance

Full solution for today (spoilers!)

## Part 1

Given a list of terms, repeatedly calculate the differences of terms until these differences are 0. So:

`0 3 6 9 12 15 3 3 3 3 3 0 0 0 0`

Calculate the sum of next terms for each sequence (18 for this one).

There’s nothing particularly interesting about the types and parsing here:

```
#[derive(Debug)]
pub struct Equation {
pub terms: Vec<i64>,
}
fn equation(s: &str) -> IResult<&str, Equation> {
let (s, terms) = separated_list1(space1, complete::i64)(s)?;
Ok((s, Equation { terms }))
}
pub fn equations(s: &str) -> IResult<&str, Vec<Equation>> {
separated_list1(newline, equation)(s)
}
```

Honestly, I could have just kept `Vec`

all through.

What’s a bit more interesting is a method to build the `stack`

for an `Equation`

:

```
impl Equation {
// Generate a 'stack' of vecs, starting from the original terms
// Each subsequent vec is the vec of differences in terms (and thus 1 element shorter)
// Stop when that list is all 0s
pub fn stack(&self) -> Vec<Vec<i64>> {
let mut stack = vec![];
stack.push(self.terms.clone());
loop {
let bottom = stack.last().unwrap();
if bottom.iter().all(|t| *t == 0) {
return stack;
}
stack.push(
bottom
.iter()
.zip(bottom.iter().skip(1))
.map(|(a, b)| *b - *a)
.collect(),
);
}
}
}
```

I enjoy the `zip(...)`

of `iter()`

and `iter().skip(1)`

.

With that, we just need to fill in the next numbers from ‘bottom up’:

```
fn main() -> Result<()> {
let stdin = io::stdin();
let input = io::read_to_string(stdin.lock())?;
let (s, equations) = parse::equations(&input).unwrap();
assert_eq!(s.trim(), "");
let result = equations
.iter()
.map(|equation| {
// Build a stack of differences until we get to 0
let mut stack = equation.stack();
// From the bottom up, add the last value to the differences beneath it
for i in (0..stack.len() - 1).rev() {
let next = stack[i].last().unwrap() + stack[i + 1].last().unwrap();
stack[i].push(next);
}
// The new last value of the top line (the original list)
*stack[0].last().unwrap()
})
.sum::<i64>();
println!("{result}");
Ok(())
}
```

And there we have it.

## Part 2

Instead of summing the next terms for each equation, sum what would be the term before the current list.

Almost, exactly the same code, we just have two differences:

```
fn main() -> Result<()> {
let stdin = io::stdin();
let input = io::read_to_string(stdin.lock())?;
let (s, equations) = parse::equations(&input).unwrap();
assert_eq!(s.trim(), "");
let result = equations
.iter()
.map(|equation| {
// Build the stacks as in part 1, but reverse them all (so we can generate a new 'first' element)
// Alternatively, use a VecDeque
let mut stack = equation.stack();
stack.iter_mut().for_each(|v| v.reverse());
// Same (from the bottom up), but this time we're subtracting
for i in (0..stack.len() - 1).rev() {
let next = stack[i].last().unwrap() - stack[i + 1].last().unwrap();
stack[i].push(next);
}
// The new last value is the value 'before' the original list
*stack[0].last().unwrap()
})
.sum::<i64>();
println!("{result}");
Ok(())
}
```

Specifically, we `for_each(|v| v.reverse())`

and subtract instead of add.

That’s really all there is to it!

## Performance

Nothing much to say here:

```
$ just time 9 1
hyperfine --warmup 3 'just run 9 1'
Benchmark 1: just run 9 1
Time (mean ± σ): 80.1 ms ± 3.3 ms [User: 30.6 ms, System: 11.3 ms]
Range (min … max): 77.2 ms … 89.4 ms 32 runs
$ just time 9 2
hyperfine --warmup 3 'just run 9 2'
Benchmark 1: just run 9 2
Time (mean ± σ): 79.6 ms ± 3.9 ms [User: 30.3 ms, System: 11.1 ms]
Range (min … max): 77.2 ms … 95.5 ms 32 runs
```

Within a margin of error of each other, which is to be expected. The first `reverse`

may have added some time, but it only depends on the length of input, not what the number of terms is.

If we had *far* larger input, I might try to optimize this (I expect there are direct equations for these), but other than that… we’re already sub 100ms and it’s been a long day–so away we go!