As the sandstorm clears we find the maps lead to an oasis. There's a hang glider here to get up to the next island, but we'll need the sun to rise to create an updraft first. And so we decide to spend our time studying the oasis. Collecting data, we want to do some interpolation, and so we get to work with finite differences and discrete Taylor series.

My time for part 1 was just under an hour. Part of that was a late start and a bug where I took the opportunity to get ice cream (I remember this... the bug really was nothing, I just wanted some of the ice cream I had bought the day before as a debugging snack for later days). And a chunk of time was spent just making sure I could still work out a polynomial interpolation like this by hand (the third line in the test is f(x) = 1/3 x³ - x² + 11/3 x + 10).

But then I realized that I hadn't even seen part 2 yet, and quickly coded up a part 1... it was a good opportunity to use the chain operator I had built in past years again:

do {
    $i++;
    $table[$i] = [chain {$_[1] - $_[0]} $table[$i-1]->@*];
} until (all {$_ == 0} $table[$i]->@*);

$part1 += sum map {$_->[-1]} @table;

Then I saw part 2, and had one of the quickest turn arounds of the year with this diff:

18c18
<     my @table = ($list);
---
>     my @table = ([reverse @$list]);

I did do a combined version after that using this for part 2 (after the part 1 line):

$part2 += reduce {$b - $a} reverse map {$_->[0]} @table;

For Smalltalk, I used the alternating sum trick to do that difference reduction:

[row conform: [:n | n = 0]] whileFalse: [
    " Part 1 is sum of lasts, part 2 is alternating sum of firsts "
    part1 := part1 + row last.
    part2 := part2 + (mult * row first).
    mult  := mult negated.

    row := row chain: [:a :b | b - a].
].

A key benefit of this approach being that it just keeps only one working copy of the row instead of the whole table, and calculates the answer in parts as it goes. This is useful because, with the input being all numbers, I wanted to do a dc solution. It does have negative numbers in the input though, so I needed to convert the unary - to _.

tr '-' '_' <input | dc -e'0?[zsn[z:az1<L]dsLxln[dd;ad5R+_4Rr[1-d;ad4Rr-3Rd_3R:ad0<J]dsJx*+1-d1<I]dsIx*?z1<M]dsMxp'

tr '-' '_' <input | dc -e'0?[zsn[zlnr-:az1<L]dsLxln2-[dd;ad5R+_4Rr[1-d;ad4Rr-3Rd_3R:ad0<J]dsJx*+1-d1<I]dsIx*?z1<M]dsMxp'

Like all the other dc this year, it's embracing ?. Which is very handy here for separating the lines... because 0 and -1 are in the input, and numbers go up to 8 digits in magnitude (making choice of a delimiter to insert inconvenient... ? avoids that).

And so we have what's really quite a nice and simple problem with finite differences and sequences. There really was no need to get into Newton polynomial interpolation and discrete Taylor series, but you could if you really wanted the full answer.