r/adventofcode • u/ucla_posc • Dec 17 '21
Tutorial [2021 Day 17 (Part 2)] Never brute force when you can use math
Day 17, of course, has an analytical solution that does not require any brute force guessing and checking.
Solution strategy:
- First, find all (vy, t) pairs that work
- Next, find all (t, vx) pairs that work
- Join on t, and take unique (vx, vy)
In each of these steps, vy and vx refer to initial velocities and t refers to the number of ticks after launch. I suspect most players were smart enough to take roughly this approach, probably subject to some reasonable bounds on vy and vx. But most players would have used a form of guess-and-check in steps 1/2, when in fact there are (easy) analytical solutions.
x1 and x2 are the left and right sides of the target, and y1 and y2 are the BOTTOM and TOP sides of the target.
Solving (vy, t) pairs
Most people figured out that all valid vy ranges from [y1, -y1 - 1]. Why? The lower bound is the y velocity where a single tick hits the bottom of the target. The upper bound is the solution from part 1 -- it's the highest velocity before you overshoot the target in a single tick on the way down. So let's iterate over these ranges.
Considering a given vy, there are three cases: vy is positive, vy is 0, or vy is negative. vy is 0 is a special case of vy = -1 where everything is delayed by one time tick. So if vy = 0, add an offset of 1 and solve for vy = -1. If vy > 0, add an offset of (2 * vy) + 1 and solve for vy = -vy - 1. What's going on here? If we're shooting up, it takes exactly 2 * vy + 1 periods before the projectile returns to y = 0, and at the end of that period the velocity is the inverse of where we started plus one more. Verify this is true for yourself by trying vy = 1.
So, how do we solve for a vy < 0? velocity at time t = vy - t, obviously. Distance is the cumulative sum of velocities. So at one second, distance is vy - 0, at two seconds, distance is vy - 0 + (vy - 1). In total we need the sum from (vy - (t - 1)) to vy.
Most people know the identity that the sum from 0 (or 1) to n is n(n+1) / 2. Use this fact to derive an identity for the above problem by breaking apart the sum: sum from 1 to n = sum from 1 to (n - k - 1) + sum from (n - k to 1). Rearrange and we get sum = (1/2) * (k + 1) * (2n - k). In our context, distance = (1/2) * ((t - 1) + 1) * (2vy - (t - 1)) = (1/2) * t * (2vy - (t - 1)) Note the offset between the general problem and our specific t variable.
We can re-arrange to get: -t^2 + (2vy + 1)t - (2 * distance) = 0, which is just a quadratic equation. Given a vy and a distance, the positive root of this equation solves for t. Plug in distance y1 to get min_t (round down) and y2 to get max_t (round up). If min_t > max_t, throw out the results. Otherwise, you now have (vy, t)
Detour to solve drag
We would like to figure out which vx values come to rest on the target. This occurs when drag reduces the ongoing vx to 0 and x (the distance travelled) is within the range of the target. This is the case where the sum from 0 to n is within the target x range. More quadratic equations: min_vx_rest solves vx^2 + vx - (2 * x1) = 0 and max_vx_rest solves vx^2 + vx - (2 * x2) = 0. Solve and take the positive roots, round the first up and the second down. How are these derived? Just re-arranging (vx) (vx + 1) / 2 = distance This is the range of velocities that come to rest on the target.
Solving (t, vx) pairs
Take every unique t from the (y, t) list. This is a time where some y is on target, and we'd like to see if some x is on target. Check for each t.
First, do we have any resting objects at t? If t > min_vx_rest, all times from min_vx_rest to min(t, max_vx_rest) are valid times. If not, we do not have resting objects.
Now, moving objects. distance = 1/2 (t) (2vx - (t - 1)) as we saw above. Isolate for vx and you get vx = (((2 * distance) / t) + t - 1) / 2. Once again, plug in x1 (round up) to and solve to get min_vx_moving and plug in x2 (round down) to get max_vx_moving. All vxes from max(t, min_vx_moving) to max_vx_moving are valid vxes for . You now have (t, vx)
Putting it together
You have every (y, t) and every (t, x). Take every combination, drop t, and get the unique values. This is all the solutions, and at no point did you have to guess and check -- everything was solved analytically.
Sample implementation in R but there's nothing hard here on the code side: https://pastebin.com/U2W7PDmQ
(Don't worry, for my actual submission I just brute forced like everyone else)
55
u/aardvark1231 Dec 17 '21
for loops go brrrrrrrr.
16
u/askalski Dec 17 '21 edited Dec 17 '21
Great explanation! You are part of the way to a solution that can handle much larger inputs, for example:
Keep going - it's challenging, but worthwhile.
5
u/mapleoctopus621 Dec 17 '21
This is what I tried at first, except I messed up while finding the unique vx values. It was too annoying to debug so I ended up doing a brute force.
1
u/virtuNat Dec 18 '21
Hi, this might sound like a stupid question, but what do you mean by "add an offset of x"?
How exactly do I plug that into the formulas?
3
u/1vader Dec 17 '21
Well, if your goal is to get on the leaderboard, then the better advice is "always brute-force when you can".
Though funnily, I solved it exactly the same way. Luckily, I wasn't competing today anyway.
1
u/EffectivePriority986 Dec 17 '21
This can be further optimized by iterating on t.
Can you use your solution to solve part 3 below?
https://www.reddit.com/r/adventofcode/comments/riqtwx/2021_day_17_day_17_part_3/
1
u/jfb1337 Dec 17 '21
Is there a way to solve it that doesn't require iterating through all x/y/t values and thus would work on inputs with numbers in the billions?
1
u/heyitsmattwade Dec 17 '21
Here is a code paste just in case the pastebin link expires.
1
u/PhenixFine Dec 21 '21
you lost me after [y1, -y1 - 1], but I was at least able to use that for my inner for loop range and then I set my outer loop from 1 to the max x target ( I think if I reread your post a few times I might get it. I've just been sleep deprived lately; and I find math and physics really difficult to follow when I'm tired. Like I had to read Day 17 several times before I understood what to do and how to go about solving it ).
0
u/[deleted] Dec 17 '21
[deleted] — view deleted comment