Wait For It

Part 1

I have to admit, my initial solution for this puzzle was a bit on the complicated side. I was trying too hard to think of a clever solution. Maybe it’ll come to me if I… wait for it.¹

For now, let’s do the simplest thing I can think of. Let’s just count the number of different button-holding times that beat the record distance.

If the time spent holding the button is $b$, and the total race time is $t$, then the distance the boat will move is $b \times (t - b)$ — the boat’s accumulated speed, times the amount of time remaining for the rest of the race. Let’s write a function that will sum up the cases for which the formula’s result is greater than the record distance.

def num_race_wins(time: int, distance: int) -> int:
    return sum(b * (time - b) > distance for b in range(time))

Armed with this function, we can solve Part 1 very easily. zip runs through the times and distances in parallel (keeping the time and record distance of each race together), and we just need to pass them to our function and wrap it in math.prod!

from math import prod

class Solution(StrSplitSolution):
    def part_1(self) -> int:
        times, distances = [
            list(map(int, line.split()[1:]))
            for line in self.input
        ]
        return prod(
            num_race_wins(time, distance)
            for time, distance in zip(times, distances)
        )

Part 2

Can I stick with brute-forcing this time? Yes; I just need to str.join the input numbers to get single time/distance numbers.

...

class Solution(StrSplitSolution):
    ...

    def part_2(self) -> int:
        time, distance = [
            int("".join(line.split()[1:]))
            for line in self.input
        ]
        return num_race_wins(time, distance)

Is it quick enough? Also yes; both parts run in ~2.34 seconds on my machine.

Will I stick with brute-forcing? No; I feel like I was onto something with my initial solution. And if I implement my idea well, it should spit out an answer immediately, and I won’t have to…wait for it.²

If we take our formula from before ($b \times (t - b) > d$) and rewrite it so we’re comparing with 0, we get $0 > b^2 - tb + d$. It looks like a quadratic equation, but not quite: it’s a quadratic inequality.

I noticed this when I wrote my initial solution, but directly calculating the number of integer solutions to this inequality is harder than it sounds. (Or at least, I couldn’t figure it out day-of.)

Looking at a plot of this quadratic inequality, we can see that we’ll find integer solutions if $b$ is greater than the left root and less than the right root.³ All we have to do is find those roots.

If we apply Po-Shen Loh’s quadratic method here,⁴ the halfway point $h$ between the roots will be $\frac{t}{2}$, and the left/right offset $o$ will be $\sqrt{h^2 - d}$. We will calculate the lower bound of the solution as $L = \lfloor h - o \rfloor$, and the upper bound of the solution as $U = \lceil h + o \rceil$ (using math.floor and math.ceil to guarantee that they’re outside of the range). Finally, $U - L - 1$ will be the number of integers in this range.

This allows us to implement the num_race_wins function like so:

from math import ceil, floor, prod, sqrt

def num_race_wins(time: int, distance: int) -> int:
    # NOTE The distance the boat travels is b * (t - b), where b is the
    # time spent holding the button, and t is the total race time; we
    # want the amount of b values where this distance is greater than
    # the record. To do this, I use some carefully handled algebra.
    halfway = time / 2
    offset = sqrt(halfway * halfway - distance)
    lower_root = floor(halfway - offset)
    upper_root = ceil(halfway + offset)
    # NOTE This is the length of the range, excluding the two endpoints.
    return upper_root - lower_root - 1

A bit more algebra, but a much lower time complexity. Now both parts of my solution run in ~3 microseconds on my machine — almost six orders of magnitude faster than before!