<- Blog
2021/01/125 minute read

applying dynamic programming to advent of code 2020 day 9

Unlike last year, I was able to complete all of the Advent of Code challenges before the year was out. I started out using C, but switched to python for the last 8 days as I was spending too much time on the problems. I am happy with how this worked out, I learned even more about C and myself as well as gained a deeper appreciation for scripting languages like Python. While I enjoyed this year's event as a whole, and there was one problem that I enjoyed much more than the others: Day 9 Part 2.

While preparing for job interviews in the fall, I spent a fair bit of time on leetcode sharpening my algorithms skills. This was an invaluable tool, and I found that I was able to use many of the problems to better my understanding of dynamic programming. This was a concept that I did not fully grasp from my algorithms courses and had always irritated me. It is often thrown in as a footnote when discussing ways to optimize algorithms. I was first exposed to it when reading the seam carving paper, and found myself incredibly confused. It was only through applying the paradigm to simpler problems that things started to make sense.

The input for Day 9's puzzle is a list of long integers. Part 1 tasks us with finding a "weak" or "invalid" number that does not follow our set of rules. Part 2 asks us to then find a contiguous set of at least two numbers that sum to the answer from part 1. This problem is perfectly suited to a dynamic programming approach.

The clue as to why this is true is that we are looking for a sequence or subset of a list with a certain property. This is a common scenario where dynamic programming applies, just like searching for common subsequences or palindromes. This is because a sequence can be built bottom up from single elements to larger and larger sequences. This bottom up building is the core of dynamic programming. We can now frame the problem as such.

Given a list of integers 'nums' of length n, let d[i][j] denote the sum
  nums[i] + nums[i+1] + ... + nums[j-1] + nums[j]

We can now start to build this matrix. We use the following 2D loop:

    int i, j;
    int done = 0;
    for (j = 2; j < n; j++) {
        for (i = 0; i < j-1; i++) {
            d[i][j] = d[i][j-1] + nums[j];
            if ((done = d[i][j] == weakness)) break;
        }
        if (done) break;
    }

We start with j=2 and i=0, iterating j until n. Each iteration of j, we iterate i from 0 to j-1. These weird bounds enforce the requirements that the sequence be at least 2 elements long. This loop builds d above the diagonal, accumulating all partial sums from i to j for all i and j. In effect, we are fixing the endpoint of the sequence at j, and then updating all of the sequences starting with all i from 0 to j-1 with the value at j. This tries subsequences of every valid length starting from every valid i. If we ever go to update the sum of a sequence and find our target value, we break early. It is clear that the complexity of this loop is O(n^2) runtime and O(n^2) space. This is an improvement over the naive O(n^3) solution which has to iterate to compute the partial sum at each valid (i,j).

After this, we have to find the min and max values on this range and return their sum. I chose the naive approach:

    long long min = LONG_MAX;
    long long max = LONG_MIN;

    for (int x = i; x <= j; x++) {
        min = MIN(min, nums[x]);
        max = MAX(max, nums[x]);
    }

    return min+max;

This has a runtime complexity of O(n), since the worst case is n if the solution sequence is the whole input list. This does not impact the asymptotic runtime of the total loop, but may be optimized further. It is possible to keep track of these values in a matrix just like the sums. We could introduce two more matrices min and max, where min[i][j] denotes the min on the sequence from i to j. This would provide a substantial real time speedup, given that min and max can be updated quickly (likely without branching).

Overall, this was a fairly straight forward problem, but it is easy to introduce a O(n^3) complexity. This is a very elegant application of dynamic programming, and I am proud that I was able to see and implement this on my first try. Learning new ways of viewing and framing problems can help better illuminate more efficient and elegant solutions to complex problems.

The full source code of my solution can be found on my github.

A big thank you to Eric Wastl for fun and interesting problems every year. Please check out Advent of Code to learn more and give previous year's problems a spin, which I am doing using 2015 to learn Rust.

back to blog posts