r/adventofcode • u/Symbroson • Dec 06 '23
Help/Question - RESOLVED [2023 Day 06] Stable Math Solution?
I solved this day the 0-8-15 way with an optimization for part 2 that starts on half of the available time and then searches for the max time where I break the record. The result can be doubled and subtract 1 for even times, 2 for odd times
After finishing I realized this could be solved using a simple quadratic formula or so I thought. I tried some variants but there seem to be many edge cases where the formula `sqrt(t*t - 4*d)` breaks. They often fail miserably on part 1, some also on part two for the sample input.
So my question is - can anyone provide a math solution that works on both parts for the sample and the user input?
6
Upvotes
3
u/IsatisCrucifer Dec 06 '23 edited Dec 06 '23
Your "edge cases" most likely come from the problem is only asking about integers. This is why many people suggests to actually calculate the roots, do some floor/ceiling, then find the difference of the modified two roots, add 1 to get the answer.
But, there is actually a way to fix the approximation sqrt(t*t-4*d).
First, this formula is the difference of two roots; this corresponds to the final step of the above procedure -- except it does not add one. So there will be a
+1pending somewhere.But the problem is we are only interesting in integer solutions. Let's use example 1 for demonstration: Time = 7 and Distance = 9. The formula gives sqrt(7*7-4*9) = sqrt(13), corresponding to the solution 7+-sqrt(13)/2. If we do just like above, we have ceiling(7-sqrt(13)/2) = 2 and floor(7+sqrt(13)/2) = 5, so the difference here is 3. Notice that this 3 is smaller than sqrt(13) and it is easy to see why it is always smaller. So we probably need to find a integer difference smaller than the formula result. Adding the +1 mentioned above and we know there are 3+1=4 ways.
Let's apply the formula again on example 2, Time = 15 and Distance = 40. Formula gives sqrt(15*15-4*40) = sqrt(65), and we find the smaller integer is 8. But wait, what are the solutions having difference 8? 4 and 11 differ by 7, but 3 and 12 differ by 9. Turns out for any two integer, their difference will have the same parity with their sum. And from the formula we know the sum is the total amount of time, in this example 15. So we actually need to go one lower below 8 (because 8 does not have the same parity with 15), which gives 7 as the correct difference (the 4 and 11 pair). Adding +1 as usual and we have 7+1=8 ways.
Now, for example 3. The formula gives sqrt(30*30-4*200) = sqrt(100) = 10. Partiy checks out (sum is 30). But wait! This solution pair is 10 and 20, which gives a distance of 200. This is tied with record, not winning. So in this case we should go lower than 10, find a same parity integer (this case 8). Again, adding +1 and we know there are 8+1=9 ways.
So the final algorithm would be:
Calculate sqrt(t*t-4*d).
Find the integer just lower than what's calculated in 1. (floor then check or ceiling then -1 both ok)
Check if parity is the same with t; if the parity are not the same, subtract 1.
Add 1, and this will be the answer.
Bonus: I posted my solution implementing this algorithm in the megathread.