Ho Ho Ho!

Every year, Eric Wastl hosts Advent of Code. Advent of Code is a programming puzzle-solving event, with a puzzle every day starting from the first of December to Christmas. I have been a yearly participant since 2020, and you can find a lot of my past solutions to the daily puzzles on my GitHub! While my participation usually gets thwarted by my onslaught of finals - I try to do the daily puzzle as long as I can every year. Last year, there was a puzzle that nicely coincided with one of my classes in terms of content. Day 9 (which you can read up on to get the extra flavor that Eric adds) involved a sequence of numbers that we had to analyze and extrapolate to generate a new number in the sequence. While programming the logic was not too difficult - there was an underlying principle that connected back to my Numerical Methods class. To show the connection, let’s first take a more in-depth look at the puzzle itself.

Pulling Apart the Puzzle

The puzzle gave you a sequence of numbers, such as:

1, 3, 6, 10, 15, 21

Your mission was to find the next number in this sequence. The puzzle instructed you to find this number by looking at the differences between each number, and looking at the differences between each difference, and so on until the difference was 0. A visual representation of this would be:

1    3    6    10    15    21
  2    3    4     5     6
    1    1     1     1
      0     0     0

The initial differences between the first terms are the second line, the differences between those numbers are the third, and the last line shows zeroes due to the third line being full of the same number. Doing this allows us to work backwards, as we simply just have to add up the last term of each line (0 + 1 + 6 + 21 = 28) to find the next term in our sequence. This process is not too difficult to program, and as such many people (me included) wrote their code around this concept. However, there is a sneaky Numerical Method’s concept infecting this problem. The key has to do with his principle: the sequence of differences will always end with a sequence of zeroes. This principle allows us to make the bridge to polynomial interpolation.

Polynomial Interpolation Acclimation

The term Polynomial Interpolation sounds a bit scary, so let’s break it down into its individual components.

A polynomial is simply a set of terms containing a variable and a coefficient that are being added, subtracted, multiplied, or divided by each other. In more simple terms, its math things that look like \(3x^2 + 2x - 5\). We are all introduced to polynomials in our first algebra class, so they should be familiar.

Interpolation is a little bit more complicated. Essentially, it is the process of taking discrete data (a set of numbers) and attempting to estimate new data points based on the past data points. Much of the time, this involves trying to fit a function around the data points. For polynomial interpolation, we attempt to find a polynomial that will output the numbers we see in our data - that way we can use the polynomial to estimate new data points. A good visual example can be seen below.

From here, we can start to see how we can use this method to determine the next number in our sequence. However, how can we be sure our sequence of numbers follow a polynomial pattern? Eric Wastl’s suggested method for solving the puzzle revealed a crucial detail: the last sequence of differences always was zeroes. For people who have taken calculus, you might recognize breaking down the differences between outputs (and their differences, and so on) as essentially taking the derivative. One of the many properties of polynomials is that if we continuously take the derivative of it, we will eventually end up with zero. Wastl guaranteed the sequence would always end up with zeroes, thus affirming it follows a polynomial pattern.

Polynomial interpolation was a concept I learned in my numerical methods class. After solving the problem using basic programming, I recognized this pattern and used my knowledge from the class to solve it using interpolation. Being able to use my newfound knowledge to solve fun puzzles was a great confidence booster. If you’re interested in turning continuous patterns and data into discrete estimations, consider taking a numerical methods class!

Now that we understand polynomial interpolation and why we can use it for this problem, let’s use the concept to generate a polynomial for our example sequence. There is many ways to do so (all with different benefits/drawbacks), but I will use Lagrange Interpolation (a type of polynomial interpolation) as it’s one of the easier methods to explain.

Lagrange Interpolation Jubilation

Here is the mathematical definition of Lagrange interpolation:

\[L(x) = \sum_{i=1}^{n} y_i \cdot l_i(x)\] \[l_i(x) = \frac{x - x_0}{x_i - x_0} \cdot... \cdot\frac{x - x_{i-1}}{x_i - x_{i-1}}\cdot\frac{x - x_{i+1}}{x_i - x_{i+1}}\cdot...\cdot\frac{x - x_n}{x_i - x_n}\]

This seems extremely complicated, but hopefully with some explanation you can get a better understanding of it. The first thing to note is that the function assumes we have \(n\) pieces of data (\(n\) numbers). When the function \(l_i(x)\) mentions \(x_0, x_1,\) or \(x_i\), it is referring to how we index our sequence. We consider the numbers in our sequence the output (\(y_i\)) and we label each number sequentially, usually starting at zero or one. This label is our input (\(x_i\)). For instance, for our example sequence of 1, 3, 6, 10, 15, 21, we want an input of zero (\(x_0\)) to output 1 \((y_0)\), and input of 1 \((x_1)\) to output 3 \((y_1)\), and so on.

Now let’s break down the logic behind this interpolation. Remember, when we input \(L(0)\) into our function, we want the first term in our sequence to pop out. Let’s analyze how the \(l_i(x)\) function allows this. Notice that if we input \(x_i\) into the function, that the terms will all cancel out. This results in the function simplifying to one, which is multiplied by \(y_i\) in our \(L(x)\) function. Along with this, whenever we input any other term in the sequence (\(x_k, k\not = i\)), the fraction that uses \(x_k\) results in a zero in the numerator, making the entire function zero. These two facts combined guarantee that \(L(x_i) = y_i\).

Let’s see this in action with a small sequence of 1,4,8. Our polynomial function ends up being:

\[L(x) = (1)\frac{x-1}{0-1}\cdot\frac{x-2}{0-2} + (4)\frac{x-0}{1-0}\cdot\frac{x-2}{1-2} + (8)\frac{x-0}{2-0}\cdot\frac{x-1}{2-1}\]

Here we can see the cancelling in action. Plug in the numbers 0,1,2 and see what happens! We can then use this function to plug in 3 and get an estimated output. This can be used in the Advent of Code puzzle to get the next number in the sequence.

If you are more programming-oriented, I have also included a C function below that mimics our lagrange function - hopefully it will help your understanding!

// Assume nums is an array of integers, and n is the length
// This function outputs the L(x) output, given an input x
int lagrange(int * nums, int n, int x) {
    float total = 0;
    for (int i = 0; i < n; i++) {
        float subtotal = *(nums + i); // Get output number (y)
        for (int j = 0; j < n; j++) {
            if (j == i) continue;
            subtotal *= ((float) (x - j)) / (i - j);
        }
        total += subtotal;
    }
    return (int) total;
}

Conclusion Extrusion

Learning computer science concepts in class is one thing - but being able to apply them when you least expect it is even more rewarding.

If you are interested in this puzzle, check out the rest of Advent of Code! Some amazing puzzles are crafted every year by Wastl.