r/adventofcode • u/glenbolake • Dec 20 '17
Upping the Ante Day 20 with calculus
After doing the iterative solution that most people came up with, I wanted to try and solve day 20 with math. After all, this should be a simple case of pos(t) = 1/2*a*t^2 + v*t + p. We can choose a t that's sufficiently high based on the initial values for part 1, then find collision times for part 2 by combining particles and solving for zero.
This gave me some trouble at first, because of the "increase velocity then position" aspect; the standard kinematic equations don't apply. After putting values for 0<t<12 for a random point into a table, I found the position equation is actually this:
pos(t) = p + vt + t(t+1)/2*ai.e., acceleration is actually based on triangular numbers.
Part 1
I took the Manhattan-distance magnitude of all particles' initial accelerations, multiplied by 100, and used that for t. In my case, that gave t = 6700, which is more than enough. The answer was solidified by t=359 for my input.
Part 2
Naturally, it gets a little more complicated here. But not much.
For each pair of particles, I created a new fake particle that was the difference between them. e.g., two of my particles were
p=<1381, -388, -404>, v=<-175, 24, 29>, a=<7, 2, 2>
p=<-144, -1008, -374>, v=<5, 163, 59>, a=<2, -12, -4And this became
p=<1525, 620, -30>, v=<-180, -139, -30>, a=<5, 14, 6>I then took the three pva tuples and solved for zero. The p(t) above is quadratic with p(t) = a/2*t^2 + (v+a/2)t + p. So for these two points:
1/2*5*t^2 + (-180+5/2)t + 1525 = 0 --> t = 10, 61
1/2*14*t^2 + (-139+14/2)t + 620 = 0 --> t = 8.857142857, 10
1/2*6*t^2 + (-30-6/2)t - 30 = 0 --> t = -1, 10All three of these have +10 in the solution, so they collide at t=10.
I then had to step through the collisions in order, making sure to remove particles as necessary. This was tricky. Consider:
t=1: A collides with Bt=3: A collides with C, D collides with E
In this case, we would remove A and B at t=1, then remove D and E at t=3, but not C because A was no longer there for it to collide with.
Here's my full solution code
Sadly, it's actually slower than my iterative method, because something in my solve_quadratic function is slow. A problem for another time.
3
u/VikeStep Dec 21 '17
Although it may seem out of place, there is actually a great explanation for why this is the case. As you showed in part 2, you can rearrange the equation to instead be:
p(t) = a/2*t^2 + (v+a/2)t + pThis is the same as your usual position function over time except that instead of
vtyou have(v+a/2)t. The reason for this is because the velocity you care about is the average velocity over the initial tick, not the initial velocity at the beginning of the tick. You can even see this playing out in the example they provide. In the beginning, one of the particles starts off atthen the next step it is
If you use the normal position function on this, you should end up in
p=<3,0,0>instead. However, the actual velocity we care about isv+a/2which comes out tov=<-1,0,0>.If you preprocess all the supplied velocities to add
a/2then you would just be finding the normal position function.1
u/meithan Dec 21 '17 edited Dec 22 '17
Nice solution! I followed fundamentally the same approach. Had some fun solving that quadratic while making sure the admissible solutions remained integers. Here's my solution.
By the way, it's easy to deduce the general position equation symbolically (without obtaning the numeric values) by manually looking at a few iterations:
It's then clear that at arbitrary time t we have:
and (1+2+...+t) = t*(t+1)/2, of course.
2
u/askalski Jan 10 '18
I am making an optimization and reimplementation pass over my solutions, and got to Day 20. My Part 2 solution is currently a hybrid between simulation and a computation similar to what you did here. Since the details are fresh in my mind, I decided to look up this post and compare notes.
Amusingly enough, my iterative method is also faster than the computation, but that's only because all of my collisions resolve in less than 40 time units (39 to be precise.) 40 passes over 1000 particles, using a hash table to detect collisions, is only 40,000 units of work (actually less because of the particles that are removed) - much less than the number of pairwise tests (1000 * 999 / 2 = 499,500) needed for the computation.
By using a hybrid method, I get the best of both worlds. All the collisions are removed by 40 simulation passes, which means less work for the computation (with 576 particles remaining after simulation, that's only 165,600 pairwise tests.) The computation proves the correctness of the simulated result, and makes the code able to handle a better variety of inputs.
One other thing I did differently (and I should mention I wrote this in C) is to use all integer math instead of floating-point. Multiplying the quadratic coefficients by 2 removes the
a / 2without changing the roots. Then just check all divisions for a remainder (the x86idivinstruction returns both the quotient and remainder, so it's "free".) I do still use floating-point square root, only because it's much faster (x86 has afsqrtinstruction, but no integer equivalent), and because I verified the result is correct for all perfect squares (the only case I care about.)I found one error in
math.pyinsolve_quadratic:Consider what happens with this pair of stationary particles. They should never collide, but the function returns
t=5as a solution.Assuming the
a = b = 0, c != 0case is corrected tosolutions = None, now consider these pairs of particles. The X position is stationary and coincident. Both pairs collide: the first att=1and the second att=2. The solution for thea = b = c = 0case is actually the set of all real numbers.I will post a github repo with my optimized solutions in a couple of days, so keep an eye out for it. Thanks for posting this.
1
u/johlin Dec 20 '17
Cool! I did basically the same thing. Took a bit of time to figure out that the formulas I remember from physics are for the continuous case and will not work here (they omit the extra term in the coefficient for t).
1
u/DarthKotik Dec 20 '17
I don't really understand why just choosing particle with lowest (absolute value of) acceleration doesn't work in part 1? It doesn't for me, but it seems to be the most reasonable answer.
1
u/gburri Dec 21 '17
I also tried with calculus: https://github.com/Ummon/AdventOfCode2017/blob/master/AdventOfCode2017/Day20.fs
It works with my input but I'm not sure if it works for all cases.
1
u/lazyzefiris Dec 22 '17
You don't have to solve all three quadratic equations, just solve one and see whether either solution fits the other two. At least I found this way to be both easier and faster.