r/adventofcode • u/musifter • 12d ago
Other [2023 Day 24] In Review (Never Tell Me The Odds)
And so the expected shoe drops... the snow-making process has a problem, and it's forming hail that we need to break up. Conveniently the hailstones are being blown by magical winds, and so our physics is just linear. And so we have a problem that can be thought of as physics and/or linear algebra.
The input for this one is 300 hailstones. The consist of a 3D position and a 3D velocity vector. The positions in the input are eye watering numbers in the trillions to hundreds of trillions (the range for mine is ~42.6 bits to just short of 49). The numbers on the velocity side are on (-1000, 1000) (the largest magnitude in mine is 958)... with 0 excluded.
Part 1 wants us to ignore the Z axis, and considering the projection onto the XY-plane, find the number of intersections that occur within a bounding box, in the future (t > 0).
There's a number of ways to do this, and given expected arrival of the 3rd dimension, I went with Cramer's Rule and turning the hailstones into linear equations of ax + by = c (ie Ax = c as a matrix). To do that, I just considered y = mx + b. Where m is slope, which it rise-over-run which is vy/vx (with no fear of 0).
y = mx + b
y = (vy/vx) * x + b
vx * y = vy * x + c (the intercept gets modified, and so I change the name to c).
-vy * x + vx * y = c (c can be calculated from the input line values)
With that form, the intersection is just a determinant / determinant:
my $det = $b2 * $a1 - $b1 * $a2;
return (undef) if ($det == 0);
return( [($b2 * $c1 - $b1 * $c2) / $det, ($c2 * $a1 - $c1 * $a2) / $det] );
So I just run through all the pairs (double nested triangle) and verify an intersection and that the time values are positive. I actually calculate them, but you could just worry about the sign if you want to avoid the division:
my $t1 = ($res->[X] - $stones[$i][X]) / $stones[$i][VX];
my $t2 = ($res->[X] - $stones[$j][X]) / $stones[$j][VX];
$part1++ if ($t1 > 0 and $t2 > 0);
For part 2, the 3rd dimension is in play, and we're tasked with finding a spot to stand and a velocity to throw a rock, so that it hits all the stones. Again, this isn't really a physics simulation, as the rock doesn't get effected by these collisions... it's just a line.
And my thoughts immediate on this go to that classic axiom of puzzling, that since this is a puzzle it is designed to have a solution. And that assumption can be used. Imagining I had two stones flying in front of me (and we've picked things aren't parallel and could cause problems), I could line up a shot that hits them both and the time between them would tell me how far back to stand. As they move, that line changes. But if I add a third rock to hit, that should fix the line (because puzzle). Two points make a line, three make the pattern. And so I should only need three points (but the others can be used to verify).
And so I started looking at equations. And this was my basic idea:
X <--S Stone and the rock hit at X at time t. The vector Vs - Vr, points
/ back to the place the rock came from, and would travel from S to R
^ L in the same time t.
|
R
I know some people visualized this in physics terms... imagine you're the rock and convert all the stone vectors into that frame of reference. It's really the same, I just came at it a bit different, because I was thinking algebra.
Next up was looking at getting a system to solve the variables. And there were more variables than I wanted to deal with, and so I cheesed it a bit. I called the rock vector (i,j,k) for a reason, and that was because I assumed that the velocity vector would be on the same scale as the stones (in fact, the largest magnitude on the rock for my solution is 286), and so I could brute for over i and j and make them constants... and k could be solved after. Here's the comment from the code:
# If we subtract the velocity vector of the rock (i,j,k) from each stone's
# velocity, at their time t (the time the stone is hit), they all add to the same point:
#
# x1 + t1(vx1 - i) = x2 + t2(vx2 - i)
#
# Reworking that:
#
# t1(vx1 - i) - t2(vx2 - i) = x2 - x1
#
# Which is a line of form ax + by = c, where the times are x and y... providing
# we make i a constant (which we're doing by brute forcing to try values for it).
And so, I used the function for line crossing from part 1, with X and Y coordinates of two stones, with brute forcing i and j (to consider them constants), to get potential times for impact on those stones. Then I check that that was a collision, and the times are positive and different and integers (because AoC answers... no need to bring in the possibility of rationals making integers until necessary).
With that, I then take the 1st stone and do the same with a 3rd. If I get a valid collision and the collision time for stone 1 is the same again (and leading to the same spot as the collision with stone 2 made it point to), I assume we've lined up our shot.
Next up is calculating k:
# Calculate k (the z part of the rock vector)
#
# t1(vz1 - k) - t2(vz2 - k) = z2 - z1
#
# k(t2 - t1) = z2 + t2(vz2) - (z1 + t1(vz1))
#
# k = (z2 + t2(vz2) - (z1 + t1(vz1))) / (t2 - t1)
Which is really just working out the obvious, it's the difference in the collision positions of two stones divided by their delta-time.
Then I just followed the the vector from the first stone back to the rock start:
my $x = $stones[0][X] + $time12->[0] * ($stones[0][VX] - $i);
my $y = $stones[0][Y] + $time12->[0] * ($stones[0][VY] - $j);
my $z = $stones[0][Z] + $time12->[0] * ($stones[0][VZ] - $k);
With (x,y,z) and (i,j,k) I can now validate all the stones if I want more confidence. But this worked and got my answer, so I didn't do more.
Like a lot of these last few days, I was happy with just having a solution that solved the problem at hand. I did spend a few hours thinking on this one, before ultimately just simplifying things to just get an answer (so I was getting tired). I can at least say that I did make good use out of the solution to part 1 for my part 2.
3
u/e_blake 11d ago
This one has a weird quirk where the example is column aligned (two consecutive spaces on a couple of lines, since velocity "1" is a shorter string than "-1"), but the actual input is not (never more than one space between tokens). Which might bite you if you are not careful when writing a custom parser for speed but still want to handle both the example and actual inputs.
2
u/e_blake 11d ago
Eww - I just noticed that my input was lucky (no parallel lines when considering only x and y velocities), but my daughter's input DID have two lines both with dx=16 and dy=-87 (parallel in part 1). Another one of Eric's unintended accidental differences in difficulty; code that assumes no parallel lines is not universal.
2
u/terje_wiig_mathisen 12d ago
Part1 was very similar to yours, u/musifter
For part2 I did not think of using Einstein, doing everything in the rock-relative coordinate system (but I wished I had!), instead I calculated the centroid of all the current positions, guessing that the hail stones were more or less randomly spread out, then I did a form of recursive descent looking for solutions where x & y would match up, then verify against z:
Loaded 300 hail stones
min: (66252602357374,32171878227714,2680557427552)
max:(562238344970567,549163897737994,554003079517479)
dmin: (-303,-919,-710) dmax:(288,906,949)
Centroid: (2.917843e+14,2.720833e+14,3.004516e+14), cent 3.95e11: (2.909469e+14,2.781623e+14,3.008861e+14)
vx=11,vy=-330 -> d2=0.00000e+00
Start at (291669802654110,103597826800230,251542427650413) with speed = (-11,330,91)
2
u/terje_wiig_mathisen 11d ago
PS. 2023 was by far my worst year timing-wise, with this one and two other puzzles taking more than 24 hours, and that meant that I didn't get my 50th star on the 25th, it had to wait for day24 to be finished first.
OTOH, doing these final days while in the middle of a vacation in the family ski cabin in the mountains of Telemark, with a one year old grandson in attendance, meant I had to prioritize my time.
I also knew at this point that as long as I finished it at all, I would win the Cognite corporate leaderboard. :-)
2
u/e_blake 11d ago edited 11d ago
This one was a bear for me; I did not solve part 1 until the 27th, and I admit having to read some of the reddit threads for ideas on part 2, which I did not solve until early January.
My initial m4 solution to part 1 was a combination of finding the right geometric equations to solve, and finding a way to avoid needing to implement bigint division (I already had my own bigint routines for addition, multiplication, and less-than relationships, but not for division). I settled on treating each line N of input (x, y, z, dx, dy, dz) as a line equation that can be rewritten into a point-slope line aN*x + bN*y + cN = 0, with aN = dyN, bN = -dxN, and cN = xN*dyN - yN*dxN. From there, and with a quick google search refresher on the intersection of two coplanar lines, I knew that two lines with coefficients (a1, b1, c1) and (a2, b2, c2) have an intersection at X = (b1*c2-b2*c1) / (a1*b2-a2*b1) and Y= (a2*c1-a1*c2)/(a1*b2-a2*b1). After adjusting the denominator to be positive, I was able to avoid the division by merely checking, for each pair of points, whether denominator*lo_bound <= X_numerator <= denominator*hi_bound && denominator*lo_bound <= Y_numerator <= denominator*hi_bound && (dxN<0 ? (X_numerator <= denominator\*x*N*) : (X_numerator >= denominator*xN)). Which is both precise (no division needed!) and slow (over two minutes runtime) thanks to the overhead in running more than 2 million bigint multiplies.
My part 2 solution was much faster, once I figured out an approach with help from reddit. Using the first five entries was enough to create a delta between the first row and each of the next four rows; resulting in a 4-row augmented matrix for four unknown variables (the delta between lines got rid of the unknown time):
[ dy2-dy1 -dx2+dx1 -y2+y1 x2-x1 | (x2*dy2 - y2*dx2 - x1*dy1 + y1*dx1) ]
[ dy3-dy1 -dx3+dx1 -y3+y1 x3-x1 | (x3*dy3 - y3*dx3 - x1*dy1 + y1*dx1) ]
[ dy4-dy1 -dx4+dx1 -y4+y1 x4-x1 | (x4*dy4 - y4*dx4 - x1*dy1 + y1*dx1) ]
[ dy5-dy1 -dx5+dx1 -y5+y1 x5-x1 | (x5*dy5 - y5*dx5 - x1*dy1 + y1*dx1) ]
and I got my star by solving that augmented matrix by Gauss-Jordan elimination with the help of a spreadsheet, before breaking down and finally implementing that algorithm in m4. So I did have to implement bigint division, but I specifically modified the algorithm to only do divisions at points where I knew the answer would be integral and not rational - which meant I only did 7 total divisions, but the first one of those divisions was HUGE:
m4trace: -2- div64(29405009862978224473000896693463756594620768, -257938683008580916429832427135646987672112)
resulting in the integer -114. Solving for just four variables (x, dx, y, dy) and then plugging it back into the original line, gave me z (and dz, although I didn't need that), with part 2 in just 130ms.
From there, I was annoyed that my part 1 solution took minutes compared to my part 2 under a second, so I explored ways to reduce the effort. I still do O(n2) pairwise comparisons, but figured out a MUCH faster approach. I scaled down each x and y input by 1 billion then shifted the window from [200000,400000] to [-100000,100000], then checked 5 intersections per line: where is x,y at time 0, where is x when y is -100000, where is x when y is 100000, where is y when x is -100000, where is y when x is 100000. Of those 5 locations, I know whether the line intersects the box of interest in the future at all (some lines don't), and if so, 2 of the 5 serve as decent approximations for endpoints of the line segment for the time where it is in range. The approximations are off (because I truncated by a billion), but by no more than 1% (since the maximum velocity 1000 applied over the size of the window 200000 is less than the 1000000000 that I truncated by), and, at least for my input, randomly dispersed enough that it did not matter. With two endpoints (4 values) per line segment, it is then possible to determine if two line segments intersect by using the signs of the four cross products of each group of 3 of those four points to see how many clockwise vs. counterclockwise orientations exist (so I'm not actually computing WHERE the lines intersect, only whether they MUST intersect; no division required!), a trick I discovered here - and which has the additional benefit of not overflowing 32-bit math! Without any bigint calls in part 1, my answer now pops out in 1.5s.
I also tested with these unofficial files where I proved how fragile my fast solution is: I get the correct answer for 3 of the 10 inputs, off by as many as 6 on 4 of the others (the rounding errors in the segment points that were close enough to parallel and/or close enough to the same quanta of the bounding box end up flipping the sign on some of the cross product computations), and trip an assertion failure that I couldn't even solve the problem on 3 of those inputs (any cross-product of 0 which declares two fudged line segments to appear collinear messes up my assumptions); whereas the much slower bigint version can get the correct answer every time. But hey, since I only have to get my own stars, and a runtime of 1.5s is no longer the long pole in my 2023 execution profile, I've never made the time to go back and clean that up to be more generic, perhaps by tracking the fractional remainder alongside the original truncated point to preserve accuracy.
But while I was working on making my solution fast, I did stumble across two algorithms, Bentley-Ottmann and Balaban, that claim they can outperform O(n2) for part 1. I have not coded it up, so I cannot state for certain whether the complexity of bookkeeping it introduces will matter, but it is on my wishlist for future attempts. In particular, Balaban claims to be O(n log n + k) time and O(n) space - once you compute the endpoints for all segments being tested (which is what I already do in my part 1 rewrite), and sort them (the n log n factor), you can do a scan-line approach where the set k of intersections in the bounding box is handled one line swap at a time. The algorithm's efficiency depends on the size of the output, not just the size of the input, and for my given input, k is about 59% of n2, so it may still be slower.
2
u/e_blake 11d ago
Bentley-Ottmann was indeed slower: https://github.com/maneatingape/advent-of-code-rust/pull/112/changes
4
u/TheZigerionScammer 11d ago
My solution exploited the fact that I knew AOC would only want to work with integer numbers (which you mentioned, but ironically was a principle that was violated in Part 1 of this problem) and I noticed that if two hailstones had the same velocity in one direction then the distance between them would be constant and the velocity of the rock would have to be a factor of that distance to hit both hailstones, plus or minus the velocity of the hailstones of course. I set up my program to search for any pairs of hailstones with a shared directional velocity and found the factors for each pair, and the common factor of all the pairs had to be the velocity for that direction. (I expected to have a certain number of velocities I could brute force through but this worked better than I expected and simply gave me all three velocities right away.) After that it was some minor algebra to get the initial position of the rock.
After I submitted my solution and write up I had a lot of people tell me that my solution helped them solve it too, which felt really good. I don't know much about linear algebra and I wasn't going to download a z3 solver or anything like that and I know a lot of other people were in the same boat.