My apologies for missing last week — the April 2024 total solar eclipse will pass directly over us (just like it did in 2017), and my band has a big concert planned for the weekend before it happens. We’ve been doing a lot of prep and rehearsals — if you’re in southern Illinois that weekend, we’d love to see you there!
In today’s challenge, you get to do a "real" world simulation of a boat race.
You have a boat which runs a timed race. However, this boat has an unusual mode of travel — you hold a button down to charge the boat. Every millisecond you hold the button down makes the boat go faster — hold it down for one millisecond, the boat travels one millimeter/millisecond. Hold it down for two milliseconds, the boat will travel at two millimeters/millisecond.
However, this is a timed race, so are only so many milliseconds to finish the race. Every millisecond used to charge the boat is a millisecond the boat isn’t moving. For example, if a race lasts five milliseconds, then any of the following can happen:
| Hold button | Boat speed | Time left | Total Distance |
|---|---|---|---|
| 0 ms | 0 mm/ms | 5 ms | 0 mm |
| 1 ms | 1 mm/ms | 4 ms | 4 mm |
| 2 ms | 2 mm/ms | 3 ms | 6 mm |
| 3ms | 3 mm/ms | 2 ms | 6 mm |
| 4ms | 4 mm/ms | 1 ms | 4 mm |
| 5 ms | 5 mm/ms | 0 ms | 0 mm |
So the best you can do here is hold the button for 2 or 3 ms and cover a total of 6 mm.
There is also a course record involved. For the example above, lets say the course record is 3 mm. You can beat that in any of four ways: hold the button for 1, 2, 3, or 4 ms.
Your puzzle input consists of the time limits for a set of races, and the course records for each of those races. It’s up to you to figure out how many ways you can beat those records. Multiply all those together to get your answer.
Approach
Remember back in January when I said:
In previous years, I’ve used Java and Python, and two puzzles I solved using an Excel spreadsheet.
Well, this was one of those times. I don’t use Excel anymore, but Libre Calc did the trick, using the table structure shown above:
- The first column tracks the time to hold the button down. This also doubles as the speed of the boat.
- I calculate the total distance in the last column using the total time for the race.
- I use a formula to count all the cells in the last column which are above the course record.
That gave me the answer for each race, which I multiplied together to get the right answer.
Part 2
Of course, part 2 couldn’t be as simple as just expanding the spreadsheet, could it?
The complication states that the numbers you were given in part 1 were kerned improperly. The numbers don’t apply to multiple races, but just one. So if your input listed two races of 5 and 11 milliseconds, with records of 4 and 17 millimeters, that is now interpreted as one race of 511 milliseconds, with a record of 417 millimeters. You still have to figure out how many ways you can beat that single record.
In part 1, none of my races were more than 100 ms, and the records topped out at around 1000 mm — easy numbers for a spreadsheet to handle. For part 2 though, I was dealing with a 55 million ms race with a record of 246 trillion mm. A spreadsheet just wasn’t going to cut it this time.
Look Closer
However, I did notice something in the sample data, and maybe you did as well — the total time for each race is symmetrical. That is, your boat travels the same distance when you hold the button for 2ms as you do for 3ms. You also get the same distance at 1ms and 4ms.
This tells me that I don’t need to count every possible race — I just need to know how many milliseconds to hold the button until I find the first one which results in a distance that breaks the current record. I can then calculate the last race which also breaks the record, and subtract those two numbers to get the total.
Figuring out the first part was a bit of a trick using a spreadsheet.
I started by incrementing the hold time by 100,000 until I found a time which beat the record. I then applied the idea from the Reimann sum algoritm, whittling the span down by 10,000, then 1,000, 100, and 10, until I found the right number. From there, it was some simple math to get my final answer, which was in the 40 millions or so.
Alternate Method
Of course, there is another, better, way using data in the chart above. Trigger warning: there will be math involved, specifically, high school algebra.
And full disclosure — I didn’t come up with this until well after the contest was over.
The math based method relies on some analysis based on the numbers shown in the chart above.
Let’s define some variables first:
- Let’s call the time the button is held down $s$ — this is the number we want to find.
- Next, let’s call the total time of the race $T$, and the record time $R$. We’ll capitalize those numbers because they are constant values, and we know them from the problem input.
Now for the analysis part:
- The time the boat has to move is the total time of the race minus the time the button was held down, or $T-s$.
- The speed of the boat is, as before, the time the button was held down, or $s$.
- Therefore, the total distance covered is the time the boat moves multiplied by it’s speed. This is expressed as $s(T-s)$.
We want the distance to be greater than the record time of $R$. So, let’s setup an inequality:
$$s(T-s) > R$$
After some algebraic manipulation, you are left with the following inequality:
$$s^2 -Ts + R < 0$$
Here’s where the high school algebra comes in.
Since this is a polynomial of degree 2, you can apply the quadratic formula to find possible values of $s$:
$$s = \frac{-b\pm\sqrt{b^2-4ac}}{2a}$$
Plugging in $a=1$, $b=-T$, and $c=R$, we get:
$$s=\frac{T\pm\sqrt{T^2-4R}}{2}$$
This will result in two values for $s$, both of which are greater than 0. We’ll call them $s_{low}$ and $s_{high}$.
How do we know $s_{low}$ and $s_{high}$ are both greater than zero? It’s in the problem description. Recall that $s$ represents the number of milliseconds you hold the button down, as well as the boat’s speed. You can’t hold the button down for a negative number of milliseconds, and you can’t travel with negative speed. Therefore, both values of $s$ must always be 0 or larger.
The image below shows how this works — the polynomial showing the total time for the race is in red, while the record time as a constant is in blue. The points where they intersect are the two numbers we are looking for.
The values $s_{low}$ and $s_{high}$ represent times which will result in the record distance $R$. However, we need times which will give distances greater than $R$ — remember, we set this up as an inequality. We also need these values to be integers — there is no way to hold the button down for a fractional number of milliseconds.
So we need to find the next integer larger than $s_{low}$ and the next integer lower than $s_{high}$ — both of these times will give us distances greater than $R$. If we take $\lceil{s_{low}}\rceil$ and $\lfloor{s_{high}}\rfloor$, we’ll get two usize values, both of which represent distances that beat $R$. By subtracting them from each other and adding one, we’ll know how many values of $s$ will beat $R$, which is what we need to solve part 2.
And in fact, this technique works for both the sample data and the real data. We can even use this technique to solve part 1 as well — just multiply all the answers together.
Summary
Sometimes there are problems for which a non-coding answer seems like the best shot. However, after some analysis, other better solutions can always be found, even well after the fact. This was one of those times for me, as the straight algebra solution didn’t come to me until well after the simulation solution. In fact, it’s making want to go back to my other spreadsheet solutions to see if there is a better way.