Advent of Code 2023: Day 06

Code for solutions available on GitHub.

Wait For It

This day was really easy. I actually initally solved it in about 15 minutes in the morning. At work. In Excel.

The input looks as follows:

Time:      7  15   30
Distance:  9  40  200

This represents 3 races of toy boats, where the time row is the total units of time the race lasts, and the distance row represents the record distance in the race.

The way the toy boats move is that they have a button on top that for every unit of time it is held down, they gain 1 unit of speed which is unleashed when the button is released. Think remote control car being held in the air while being accelerated then dropped and taking off immediately. There’s a tradeoff here between how long to hold the button to gain maximum speed and releasing the button as soon as possible to have more time to travel a greater distance.

The challenge is to find all possible integer values for units of time to hold down the button that result in beating the record distance.

Let’s do this mathematically.

• The total time T of a race is the button hold time t plus the race time, t_race
• D is the record distance for the race
• v is the velocity of the boat, and is equal to t
• The distance function d(t) = v * t_race = t * (T - t)

We want to beat the previous record, meaning that we want d(t) - D > 0. So finding the roots of the following equation:

t * (T - t) - D = 0
-t^2 + Tt - D = 0

will give the exact values for t (button hold time) that will result in beating the record. However, since the button can only be held for integer units of time, we need to round the lower root of t to the next integer, and the upper root to the previous integer. So t2 - t1 + 1 should be the answer (where t1 and t2 are the appropriately rounded roots). However, If the quadratic has integer roots, the rounding doesn’t do anything, and holding the button for exactly the same amount of time will result in tying the record, not beating it. So we need a corretion term subtracting 1 for each root that has a zero fractional part. The full solution is thus

t2 - t1 + 1 - correction_term

I’m not even going to bother with documenting the Rust code. It’s pretty uninteresting. It’s here if you need it.

Update: 2023-12-07

I realized I didn’t cover part 2 at all. But it’s really simple. Instead of the input being a bunch of races, it’s really only one race, and you should ignore all spaces between numbers. The solution is the same. The only complication is that if you chose u32 as the base type for the solution, this will overflow.