# Day 9: Mirage Maintenance

by @SethTisue

## Puzzle description

https://adventofcode.com/2023/day/9

## Background

This method of predicting the next number in a sequence is an example of using "finite differences". The elves are asking us to construct a "difference table". It is a special case of the more general method of "Lagrange interpolation". The method of differences also gave its name to Charles Babbage's famous mechanical "difference engine".

Even if this mathematical background is unfamiliar to you, the method is still straightforward to implement.

### Core logic

The algorithm can naturally be expressed in functional style using recursion. See the alternate solutions linked below for some other possible approaches.

The heart of our solution to both parts is this recursive method:

`def extrapolate(xs: Seq[Int]): Int =`

if xs.forall(_ == xs.head)

then xs.head

else

xs.last + extrapolate(

xs.tail.lazyZip(xs)

.map(_ - _)

.toSeq)

If we are not at the base case, we construct the next row
of the difference table using `map`

, extrapolate the next
difference, and then add that difference to the number at
the end of the current row.

At the base case, I've introduced a small optimization. The puzzle suggests stopping once we hit a row of all zeros:

` if xs.forall(_ == 0)`

then 0

else ...

But we can actually stop a step sooner, once we arrive at a row of all
the same value, even if that value is nonzero. (If we continued, the
*next* row would be all zeros.)

The use of
`lazyZip`

instead of regular `zip`

is also a small optimization that avoids
constructing an intermediate collection.

Note that doing `xs.tail.lazyZip(xs)`

instead of the more obvious
`xs.lazyZip(xs.tail)`

means we don't need to reverse the arguments
before subtracting, allowing use of the `_ - _`

shorthand.

Note also that both `zip`

and `lazyZip`

discard any extra values,
so it doesn't matter that one of the sequences being zipped is one
shorter.

It would be only slightly more awkward to instead use `sliding(2)`

to
iterate over successive pairs, as follows:

`xs.sliding(2).map:`

case Seq(x1, x2) =>

x2 - x1

Instead of recursion, one could also express the algorithm using an
iterator (with `Iterator.unfold`

, as suggested by Stewart Stewart, or
`Iterator.iterate`

), or tail recursion with an accumulator, or an
imperative loop.

### Parsing

Parsing today's input presents no special challenges:

`def parse(input: String): Seq[Seq[Int]] =`

input.linesIterator

.map(_.split(' ').map(_.toInt).toSeq)

.toSeq

### Part 1

Now we have all the pieces we need to solve part 1:

`def part1(input: String): Int =`

parse(input)

.map(extrapolate)

.sum

### Part 2

The simplest way to solve part 2 is simply to insert
`.map(_.reverse)`

, so that we're extrapolating to the left rather than
to the right:

`def part2(input: String): Int =`

parse(input)

.map(_.reverse) // only this line is new

.map(extrapolate)

.sum

It's also possible to solve it without reversing the input, as seen in some of the community solutions linked below. The problem text suggests "Adding the new values on the left side of each sequence from bottom to top", and this suggestion can be turned into code.

## Solutions from the community

- Solution of Jan Boerman.
- Solution by Guillaume Vandecasteele
- Solution by jnclt
- Solution by Thanh Le
- Solution by Spamegg
- Solution by Niels Prins
- Solution by Jamie Thompson
- Solution by Rui Alves
- Solution by Yann Moisan
- Solution by g.berezin
- Solution by Marconi Lanna
- Solution by Joel Edwards
- Solution by Paweł Cembaluk

Share your solution to the Scala community by editing this page. You can even write the whole article! See here for the expected format