Advent of Code 2023: Building Intuition With Quadratic Equations

Friday, December 8th, 2023

Introduction

Ah, it's the most wonderful time of the year. The days are short, it's cold and wet, it doesn't snow anymore, and the kids refuse to go outside.

Wait, all that stuff sucks.

But you know what doesn't suck about this time of the year? That's right - Advent of Code.

I always have a good time working my way through Eric Wastl's puzzles. The level of craft that goes into each year's Advent of Code is truly impressive, and it's also a chance to write Elixir, which is always fun. In 2020, I completed all 25 puzzles, and it felt like a huge accomplishment. In the intervening years, I've never quite managed to get through all of the puzzles, but still, every now and then, even if it's not even Christmas, I find myself getting pulled into these puzzles for a while. I always enjoy the experience, and I always learn something.

I've got a pretty cool repo where I've collected all my solutions - and I've built up some cool tools to make working on them easier over the years. I've got code for fetching the puzzle inputs and descriptions automatically, a small library of functions that I wrote one too many times, and even a whole module which I use for the "2D grid" class of puzzles.

Another thing you can find in that repo is my notes about each puzzle. In many cases these just read something like "oh my god that one was a pain in the ass", but here and there, I've ended up writing a deep dive on some particular thing I encountered. Every once in a while I go back and reference those notes. It's always sort of fun to reconstruct what I was thinking as I wrote some gnarled tumor of a function, and occasionally, it's even useful.

Two days ago, I worked through this year's Day 6 Puzzle. I didn't have too much trouble with it, but when I got to the second part of the puzzle, my code took around 15 seconds to finish processing. As a rule, I'd be fine with a 15 second runtime - I've got other solutions in the repo that take a lot longer than that - but I had a feeling, based on my initial brute force implementation, that there was some fairly simple math trick I was missing.

As I started exploring the problems and writing notes, the notes started to get a life of their own, and by the time I was done figuring out my next solution, I felt like I had the bones of a pretty good blog post on my hands. It also felt like a good excuse to figure out how to get my blog to display LaTeX. (Incidentally, this is a lot like how one of my other posts came into being).

Two disclaimers:

• This post contains spoilers for Day 6 of Advent of Code 2023. If you don't want to be spoiled, read something else.
• If you're good at math, this might feel a little basic. I'm really not a math guy (and if you doubt this after the post, please remember that LaTeX is making me look at least 10x smarter than I actually am). I don't think I've thought about quadratic equations or the quadratic formula since college - and even then, I think it was sort of assumed as basic knowledge - so probably the last time I really engaged with any of this was in high school. For me, though, this was a really valuable exercise in re-establishing some intuition on this subject.

So, without further preamble, let's do some math.

My Initial Notes

alright, this one looks amenable to brute force, or at least part 1 does.

yup, part 1 easy to brute force.

part 2 is obviously less amenable to brute force, but it only has to run 35,696,887 iterations to simulate the race, and then the Enum.filter is also linear time against all 35 million. It finishes in about 15 seconds though. Good enough for now.

Ok - so I was sittin' on the toilet, and thinking about this problem. It's obviously some sort of math problem. There is a formula for figuring out the distance traveled for each amount of time holding down the button. So there must be a way to figure out what that equation looks like, and then solve for the constraint.

So I think it's something like this. d is the distance traveled, and t is the amount of time holding down the button. then there's a constant, we'll call it C, which represents the total time we have for the race.

$$d = t * (C - t)$$

Ah-ha - it's just a quadratic equation / parabola. And that makes sense - there's going to be 0 points at t=0 and t=C (because in either of those cases the boat doesn't move). Every point between those points has some positive value for the movement of the boat. In the middle of the parabola (its vertex) is the maximum possible distance. And for every value of of t to the right of the vertex, we start losing distance.

So god, i don't remember how to do this. I guess I need to figure out.... for the range of t=0..C, all the values of d that are greater than the "distance record". and doing that will involve finding the roots of the parabola / equation, but might also need some sort of shift to account for the limit.

OK - yes, that's right. Googling around a bit, this is starting to come back to me.

Slowly Remembering Quadratic Equations

OK so. A quadratic equation describing a parabola looks like \(y = ax^2 + bx + c\).

And we can use the quadratic formula to get the roots of the equation - which are the points where the graph of the parabola crosses the x axis, i.e., the points where \(y = 0\). To do this we write the equation with \(y\) set to zero, like this: \(ax^2 + bx + c = 0\). Then we can just plug the coefficients into the quadratic formula and solve:

$$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$

And this gives us the places where \(y = 0\).

But for our application, we're interested in something slightly different. We need to know the range of values of \(t\) (the amount of time we hold the button) which results in a value greater than the distance record. we'll call that value \(d\).

Now, for the sake of building intuition, lets think about the code and how it relates to our equation.

We calculate the distance that a boat travels with this block of code. time_holding_button comes in from the "loop" (not really a loop, we `Enum.map` over the range of possible ts for a given race.)

• ms_per_s is the speed at which the boat travels, and it's equal to the number of seconds we hold down the button. (It's acutally milliseconds, per the puzzle text, but not important here).
• remaining_seconds is the amount of time left for the boat to travel. Remember that for each race we have a set amount of `race_time` in which the race occurs. So the remaining number of seconds is the total `race_time` minus how long we held the button.
• Then, distance is just how fast we're going per second multiplied by the remaining time in the race.

So, above, I expressed this equation as: \(d = t * (R - t)\), but let's see it with our var names for clarity:

$$distance = time\_holding\_button * (race\_time - time\_holding\_button)$$

Call distance \(d\) and time_holding_button \(t\), and the constant race_time \(C\), and we get that original equation:

$$d = t(C - t)$$

So if we want to plot this on an \(x\),\(y\) plane, then our \(y\) value will be the distance the boat travels, and the input \(x\) is how long we hold the button. This gives us the same equation, but with x and y:

$$y = x(C - x)$$

And if we manipulate that equation, we get the familiar form of a quadratic equation. lets change the \(C\) to \(B\) for the sake of not being confused with the constant in the normal \(ax^2 + bx + c\) form:

$$ y = -x^2 + Bx $$

From this equation we can determine a few things, and the most important of those is that the parabola is going to open downward. Again, this makes sense - our two roots are at \(x = 0\), and \(x = C\) and those are the two points which represent not holding the button at all or holding it through the entire race_time. The \(y\) values to the left or right of those roots don't make any sense - those to the left would represent holding the button for a negative amount of time (a negative \(x\)), and those to the right would represent holding the button longer than the race (at which point the values are technically wrong, because they're no longer defined by our function at that point). Our function is really limited to the domain of \(t\) which would be valid in our race.

Building More Intuition Around Our Equation

Ok, so that establishes some intuition for what our function describes and the parts of the domain we're interested in. But let's try to prime our intuition even more before we get back to numbers. Text is nice, but you know what they say - so we really need to be able to see the graph of the function to get a sense of what's going on here.

This is a plot of our function. Remember that our \(B\) coefficient is enormous - it's the range of time available in the race, and from parsing the puzzle input we can find out that it's 35,696,887.

$$y = -x^{2\ }+35696887x$$

Because the constant in our problem is humongous, and because this equation involves an exponent, we end up with a really tall and narrow graph, even if we "zoom out" to a pretty crazy degree. I messed with the axes on this graph to make it a little easier to see the whole thing in one image - but note that we're working with some seriously huge numbers here, and also notice that the scale on the y axis is several orders of magnitude greater than the scale of the x-axis.

We can see that this plot matches up with some of the intuition we developed above. For \(x < 0\), the \(y\) value (distance traveled by the boat) is negative. And for \(x > 35,696,887\), \(y\) is also negative.

Because this quadratic equation doesn't have a \(c\) constant, it's fairly easy to see the roots are 0 and 35,696,887 just with some simple manipulation of the equation - we don't even need the quadratic formula to do this. For both of these equations, we don't even need to plug the constant in to be able to see the roots.

\(x=0\) is the trivial case, even someone as bad at math as me can see this equality checks out.

$$ \begin{aligned} 0 &= 0^2 + b * 0 \\0 &= 0 + 0 \end{aligned}$$

If we set x to our big constant (\(x=35,696,887\)) it's a little harder, but not by much.

$$ \begin{aligned} 0 &= 35,696,887^2 - (35,696,887 * 35,696,887) \\0&= 35,696,887^2 - 35,696,887^2 \end{aligned}$$

While working through this problem, I noticed something. For any quadratic that we can express like \(y=x^2-bx\), or equivalently \(y=-x^2+bx\), the roots will always be 0 and \(b\). After playing with it a while, it's apparently a requirement that \(a = 1\) or \(a = -1\) and that the sign of \(b\) is flipped from \(a\).

To see more generically that \(x=0\) and \(x = b\) are the solutions for \(0 = -x^2 + bx\), we can use the quadratic formula. Since equations in this form don't have a constant \(c\), we plug in \(c=0\), which simplifies the quadratic formula a bit. We're interested in solving the equation in terms of \(b\), so we also need to plug in our constant for \(a\) - in this case, \(a=-1\).

$$ \begin{aligned} a &= -1\\ c &= 0\\ \end{aligned} $$

$$ \begin{aligned} \\x &= \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \\x &= \frac{-b \pm \sqrt{b^2 - 4(-1)(0)}}{2*(-1)} \\x &= \frac{-b \pm \sqrt{b^2}}{-2} \\x &= \frac{-b \pm b}{-2} \\ \\x_1 &= \frac{-b + b}{-2} \\x_1 &= \frac{0}{-2} \\x_1 &= 0 \\ \\x_2 &= \frac{-b - b}{-2} \\x_2 &= \frac{-2b}{-2} \\x_2 &= b \end{aligned} $$

Just to double check my intuition, let's do the same thing to find the roots for the form \(0 = x^2 - bx\). Because the quadratic equation wants a positive \(b\), we need to account for the fact that \(b\) is negative in this form. We can just flip the signs on all the bs through the equation, but to make it more obvious what's going on, we'll express \(-b\) as \(b = (-1)*b\). This is kind of unnecessary as the two negative signs cancel quickly, but it helped my intuition to see things worked out at this level of detail.

$$ \begin{aligned} a &= 1 \\b &= -1 * b \\c &= 0 \end{aligned} $$

$$ \begin{aligned} \\x &= \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \\x &= \frac{-(-1 * b) \pm \sqrt{(-1 * b)^2 - 4(-1)(0)}}{2a} \\x &= \frac{(-1)(-1 * b) \pm \sqrt{(-1 * b)(-1 * b) - 0}}{2a} \\x &= \frac{(1 * b) \pm \sqrt{(-1 * b)(-1 * b)}}{2a} \\x &= \frac{b \pm \sqrt{(-b)(-b)}}{2a} \\x &= \frac{b \pm \sqrt{b^2}}{2*(1)} \\x &= \frac{b \pm b}{2} \\x &= \frac{b \pm b}{2} \\ \\x_1 &= \frac{b + b}{2} \\x_1 &= \frac{2b}{2} \\x_1 &= b \\ \\x_2 &= \frac{b - b}{2} \\x_2 &= \frac{0}{2} \\x_2 &= 0 \end{aligned} $$

Ok. So we've basically dissected this little quadratic equation, and we know quite a lot about how it works now. But we're not quite to the answer we're looking for yet, because remember - we aren't really that interested in the roots of the equation. Instead, what we need to figure out is the answer to this question: What is the range of values in the domain for which \(y > target\_distance\) - the distance which we have to beat to win the race.

Finding a New Set of Roots

So, what we really need to do is to find the roots of the equation not at \(y=0\), but at the line \(y = target\_distance\). Just like our total time available for the race (which we've been calling \(B\)), we get the target distance from our puzzle input, and it's a _really_ big number: 213,116,810,861,248 (that's 213 quadrillion).

Plotting our quadratic (\(y = -x^2 + 35,696,887x\)), and this horizontal line (\(y = 213,116,810,861,248\)) gives us this graph:

So now, we just need to find the places where the parabola crosses our new line - that is, the places on the graph where \(y = target\_distance\). Any values for x which are between these new roots will beat the current record distance defined by the problem. And conveniently, we have the quadratic formula, which we can use to find the roots of any parabola. But remember - in order to use the quadratic formula, we need our quadratic equation to be in this form to get the right values for \(a\), \(b\), and \(c\):

$$ 0 = ax^2 + bx + c$$

Luckily, what we have is pretty easy to manipulate into that form:

$$ \begin{aligned} \\213,116,810,861,248 &= -x^2 + 35,696,887x \\ 0 &= -x^2 + 35,696,887x - 213,116,810,861,248 \end{aligned}$$

Plotting this new equation, on the same graph as our previous equations, gives us this picture. To make it easier to see the significance of the relationship betwene our two parabolas, I added two vertical lines to the plot. This makes it easy to see that our new parabola's roots on the \(x\) axis are the same as the roots of the previous parabola on the line \(y = 213,116,810,861,248\).

Now that we have our new equation expressed in the \(0 = ax^2 + bx + c\) form, all that's left is to plug those values into the quadratic equation, and solve it. This gives us the roots for the parabola, and any values of \(x\) between these numbers will result in our boat winning the race. The numbers here get huge - but the math is straightforward.

$$\begin{aligned} 0 &= -x^2 + 35,696,887x - 213,116,810,861,248 \\ a &= -1 \\ b&=35,696,887 \\ c &= -213,116,810,861,248\end{aligned}$$

$$ \begin{aligned} x &= \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \\x &= \frac{-35,696,887 \pm \sqrt{35,696,887^2 - 4*(-1)*(-213,116,810,861,248)}}{2(-1)} \\x &= \frac{-35,696,887 \pm \sqrt{1,274,267,741,490,769 - 852,467,243,444,992}}{-2} \\x &= \frac{-35,696,887 \pm \sqrt{421,800,498,045,777}}{-2} \\x &= \frac{-35,696,887 \pm 20537782.20854864}{-2} \\ \\ x_1 &= \frac{-35,696,887 + 20,537,782.20854864}{-2} \\ x_1 &= \frac{-15159104.791451361}{-2} \\ x_1 &= 7579552.3957256805 \\ \\ x_2 &= \frac{-35,696,887 - 20,537,782.20854864}{-2} \\ x_2 &= \frac{-56,234,669.208548635}{-2} \\ x_2 &= 28117334.604 \end{aligned} $$

Alright, so now we have our roots. All the integers between \(x_1\) and \(x_2\) are valid solutions to the puzzle (i.e. an amount of time to hold down the button that results in a race-winning distance). We just need to count the total number of integers between our two values. That is, we want the whole range of integers that are >= x1, and <= x2 - or: \(\{ n \in \mathbb{Z} \mid x_1 < n < x_2 \}\).

Counting the Winning Values

Counting the number of integers in this range is easy, intuitively - but implementing it mathematically is slightly counterintuitive. Intuitively, you look at the numbers, you pick the next integer after the lower root, the highest integer before the higher root, then subtract these two numbers and add 1. So the formula goes something like:

$$ \begin{aligned} solution = \lfloor x_2 \rfloor\ - \lceil x_1 \rceil + 1 \end{aligned} $$

The problem with implementing this in code is that it fails if you end up with an integer root, because the floor or ceil of an integer is just that integer - that is:

$$ \left\lfloor n \right\rfloor = \left\lceil n \right\rceil = n, \quad \text{if } n \in \mathbb{Z} $$

It turns out the better way to implement this in code is to take the floor of the lower root and add 1, and to take the ceil of the higher root and subtract 1. Then we can get the solution like so:

$$ \begin{aligned} solution = (\lceil x_2 \rceil - 1) - (\lfloor x_1 \rfloor + 1) + 1 \end{aligned} $$

It's worth noting that this formula only works for quadratics of the form \(-x^2 +bx\). If the sign of \(b\) is negative, we'll have negative roots, and so we'd have to shuffle the floors and ceils around. But that's ok, since we know all our equations will be in that form for this puzzle.

Plugging our roots into this formula gives:

$$ \begin{aligned} \\ x_1 &= 7579552.3957256805 \\ x_2 &= 28117334.604 \end{aligned} $$

$$ \\ \begin{aligned} \\solution &= (\lceil 28117334.604 \rceil - 1) - (\lfloor 7579552.3957256805 \rfloor + 1) + 1 \\solution &= (28,117,335 - 1) - (7,579,552 + 1) + 1 \\solution &= (28,117,334) - (7,579,553) + 1 \\solution &= (28,117,334) - (7,579,553) + 1 \end{aligned} $$

This matches the solution we got from our initial brute force algorithm, so we're done!

Coding it Up

Now all we need to do is translate this process into our Elixir code. The resulting function is pretty simple:

Running our test suite with this new implementation provides a huge speedup to our code. The brute-force version of the algorithm took around 15 seconds for the huge part 2 numbers, where as this one finishes almost instantly.

Analyzing the Code's Runtime

It's interesting to think a little bit about the time complexity of the two algorithms. Let's take a look at the initial brute force solution.

simulate_race takes the race_time and distance_record as parameters, then it maps over the range of 1..(race_time - 1), manually calculating the distance achieved by the boat for each possible time_holding_button. It adds a third value to the tuple, distance > distance_record. If this is true, then the input was a win, if not, the input didn't beat the record.

At this point, all we need to do is count the number of winning inputs in our set of possibilities:

The only difference between the part_2_brute_force and part_1_brute_force functions is that in Part 1, we interpreted our data as describing more than one race, so we need to run our simulation of each possible input for each of those races.

So, if we think about our algorithm for simulating inputs to each race, we can realize that it does a constant amount of work for each number in its range. That means the runtime complexity of the function is \(O(n)\). There's an "outer loop" in the case of Part 1, since we need to run our \(O(n)\) algorithm once for each race in the input - but since there's only 4, this doesn't really make much difference.

In the case of Part 2, we only need to do a few math operations for any given race. This means the algorithm has a constant runtime - \(O(1)\).

In either case, the math operations aren't very expensive. A computer can obviously perform a handful of multiplications almost instantaneously. But once you have to do it a few hundred quadrillion times, those "almosts" start to add up.

As a general rule, I'd be more than happy with a 15 second runtime for one of these problems, but it's still cool to understand that with a little math, it can be basically instaneous.

Benchmarking the Code

When I run into one of these problems that has some kind of increase in time complexity, I often enjoy writing a benchmark for it. The library I use for this in Elixir is Benchee, which has some nice features and is overall pleasantly easy to use.

Here's the simple test case I wrote with Benchee:

And here's the output of running the benchmarking suite:

##### With input small case from sample #####
Name                   ips        average  deviation         median         99th %
math version        5.83 M      171.47 ns ±13983.47%         145 ns         216 ns
brute force         2.23 M      447.79 ns  ±6449.45%         331 ns         667 ns

Comparison:
math version        5.83 M
brute force         2.23 M - 2.61x slower +276.32 ns

##### With input bigger case from sample #####
Name                   ips        average  deviation         median         99th %
math version        5.55 M       0.180 μs ±13066.58%       0.146 μs        0.22 μs
brute force         0.98 M        1.02 μs  ±2048.99%        0.86 μs        1.29 μs

Comparison:
math version        5.55 M
brute force         0.98 M - 5.67x slower +0.84 μs

##### With input bump it up more #####
Name                   ips        average  deviation         median         99th %
math version        6.41 M     0.00016 ms ±16668.17%     0.00012 ms     0.00019 ms
brute force      0.00091 M        1.09 ms    ±12.62%        1.07 ms        1.54 ms

Comparison:
math version        6.41 M
brute force      0.00091 M - 7013.29x slower +1.09 ms

##### With input part 2 input #####
Name                   ips        average  deviation         median         99th %
math version        6.02 M      0.00000 s ±12560.12%      0.00000 s      0.00000 s
brute force      0.00000 M         8.47 s     ±0.00%         8.47 s         8.47 s

Comparison:
math version        6.02 M
brute force      0.00000 M - 50996397.84x slower +8.47 s

##### With input even bigger input #####
Name                   ips        average  deviation         median         99th %
math version        5.70 M    0.00000 min ±13078.74%    0.00000 min    0.00000 min
brute force      0.00000 M       7.66 min     ±0.00%       7.66 min       7.66 min

Comparison:
math version        5.70 M
brute force      0.00000 M - 2619587031.25x slower +7.66 min

So, first observation is even for a tiny input that's only running a handful of iterations, the math version finishes in half the time. The next two inputs line up approximately with the \(O(n)\) runtime, increasing about an order of magnitude for each order of magnitude in the input. As we get into higher numbers, the slowdown starts to get more pronouced - I think this is probably due to the cost of inserting a value into a map in Elixir, which iirc is \(O(log n)\). As our n increases, we start to pay more and more for that insertion.

Closing Thoughts

Alright, wow. This ended up being probably my longest post on this site. And I wound up putting probably an extra 6 hours of work into Day 6 if you count the time I spent writing this.

But that's OK - because one of the best things about having this blog is being able to go back and reference my own posts. For you, anonymous reader, all this quadratic equation stuff may be crazy familiar - but for me, I hadn't really thought about it for a decade. I feel a lot sharper on the math behind this topic, and the next time I encounter a quadratic equation, I'll be stoked to have this reference.

Well, that's all I've got for now. See ya next time.