Advent of Code 2023, Day 9
❄️ Back to Advent of Code 2023 solutions homepage ❄️
# Imports
from aoc23.utils import read_input
import math
import numpy as np
input_9 = read_input(9)
Part 1
In the first part of today’s puzzle, we are given a collection of sequences with the property that when differenced a finite number of times using the difference operator $Df(n) = f(n+1)-f(n)$, a constant sequence is obtained. Sequences with this property are exactly the sequences which are generated by polynomial functions, with the degree of the polynomial given by the number of difference operators applied to reach the constant sequence.
In order to find the next value in the sequence, keep track of each of the differenced sequences, until the constant sequence is reached; then, add up the final element of each differenced sequence to give the next value:
sequences = [
[int(x) for x in line.split()]
for line in input_9
]
def next_element(sequence):
diffs = []
while any(sequence):
diffs.append(sequence)
sequence = np.diff(sequence)
return sum([diff[-1] for diff in diffs])
assert next_element([1, 2, 3, 4, 5]) == 6
assert next_element([0, 1, 4, 9]) == 16
assert next_element([1 + x + 3*x**2 + 4*x**3 for x in [1, 2, 3, 4, 5, 6]]) == 1 + 7 + 3*7**2 + 4*7**3
We are asked to find the sum of the next values for all of the sequences:
sum([next_element(sequence) for sequence in sequences])
2038472161
And so the answer to part 1 is: 2038472161.
Part 2
For the second part, we must find the preceding value for each sequence, rather than the next value, by following the same rules as before and extrapolating backwards instead of forwards. This was possible the easiest part 2 extension I’ve come across:
sum([next_element(sequence[::-1]) for sequence in sequences])
1091
This works because if $f(x)$ is a polynomial of degree $n$, then so is $g_a(x):=f(a-x)$, and so subsequent values of $g_a$ can also be computed using the same differencing rule. Considering our initial sequence of 21 values $(f(1),f(2),…,f(21))$, we see that the preceding value given is by $f(0)=g_{22}(22)$. In other words, the next value of the sequence $(g(1),…,g(21))=(f(21), f(20), … f(1))$ i.e. the reversed sequence.
So the answer to part 2 is: 1091.
Further reading:
- Vandemonde matrix - casting the polynomial interpolation as a linear algebra problem, solved by inverting the Vandemonde matrix. More widely applicable, to cases where the input points aren’t easily spaced.
- Lagrange polynomials and Newton polynomials - two sets of polynomial basis functions, which put the Vandemonde in unit matrix/lower triangular form respectively.
Comments