Kind of a rest day

Overall, the puzzles have been relatively tricky for a first week, I feel like. Thankfully, today was chill.

Nvim stuff

Not strictly Nvim, but LSP: I was a snippet hater, and I was wrong. rust-analyzer has snippets that let you write for example some_long_expression.ok, and it'll transform into Ok(some_long_expression). Same with some, ref (prepends a &) and refm (prepends a &mut). They're so good.

The task itself

Code

As I mentioned, a chill one. The entire problem pretty much boils down to finding the amount of numbers that are above a line for a given parabola. So this time, we have math!

For any given race, we have one variable (speed) and two constants (time, distance). From that we can calculate the distance we travel for any given speed:

f (s p e e d) = s p e e d * (t i m e - s p e e d)

In order to win the race, this number has to be larger than our distance constant.

f (s p e e d) > d i s t a n c e

If we rearrange this, we get a quadratic inequality:

s p e e d * (t i m e - s p e e d) > d i s t a n c e

- s p e e d^{2} + t i m e * s p e e d - d i s t a n c e > 0

We can use the, and I'm sorry to say this, quadratic formula to find the interval in which this is larger than 0.

\begin{array}{r} a = - 1, b = t i m e, c = - d i s t a n c e \\ x 1 = \frac{- b^{2} + \sqrt{b^{2} - 4 a c}}{2 a} \\ x 2 = \frac{- b^{2} - \sqrt{b^{2} - 4 a c}}{2 a} \end{array}

In the interval (x1, x2), the inequality holds, giving us our solution.^[1] We just need to count the whole numbers in that interval.

type Race = (usize, usize);

fn ways_to_beat((time, distance): Race) -> usize {
    let a = -1.0;
    let b = time as f64;
    let c = -(distance as f64);

    let x1 = (-b + (b.powi(2) - 4.0 * a * c).sqrt()) / (2.0 * a);
    let x2 = (-b - (b.powi(2) - 4.0 * a * c).sqrt()) / (2.0 * a);

    let (x1, x2) = (x1.ceil() as usize, x2.floor() as usize);
    1 + x2 - x1
}

And that's already the core of the puzzle. Doesn't matter that part 2 asks you to do this for a large number, it's just as fast!

Now, I wish that was my first impulse... instead, I started out writing a binary search starting at speed = time / 2. It was only while writing comments and this post that I realized that, wait, this is just school math!

Floating point precision

I originally forgot to mention this, but when I first wrote the solution, I did the calculations with f32/single-precision floating point numbers. This didn't work, my final result was off by 2 (an astounding 0.00000654% error).

Switching to f64 fixed it. It's kinda funny that you can run into floating point resolution issues like that.

We know for certain that x1 < x2, because a = -1, so all the signs get flipped. ↩︎