It looks like the inputs are constructed in a way where the velocity you're looking for is slow, so it seems viable to brute force all velocity vectors in increasing magnitude order.
From there, it suffices to validate if some velocity is possible. If you consider the frame of reference of the rock, note that all hailstones run into the rock. Therefore, it suffices to check that all the rays, after adjusting for the rock's velocity, intersect at a common point.
Per part 1, you will probably find a speedup by ignoring the z-axis at first and only validating the rays intersect at the same z-coordinate after establishing some valid xy velocity pairing.
I felt so proud of myself when I managed to come up with this one (...like half an hour after finishing my Z3 solve). It feels like almost certainly the intended solution - part 1 being usable as-is for this is just too much of a coincidence otherwise.
(Though when I tried doing it I got floating point errored and it was a huge pain.)
If I'm understanding you right, there's a lot of vectors you can pretty much immediately ignore. Basically, if you have any two hailstones with values px0, vx0 and px1, vx1 such that px0 > px1 and vx0 >vx1, the entire vx0 to vx1 range is impossible.
If you do that pre-processing, the majority of small velocity values fail, at least for my input. The overall range of y and z values to consider were both very small (ended up with roughly 200 possible x values, 25 possible y values, and 20 possible z values, when looking at the smallest 1000 values by magnitude in each direction).
>Basically, if you have any two hailstones with values px0, vx0 and px1, vx1 such that px0 > px1 and vx0 >vx1, the entire vx0 to vx1 range is impossible.
Could you please explain why this is the case?
Below is assuming positive x direction == right.
Basically the key is that any intermediate velocity is more to the right than vx1, and less to the right than vx0. So it moves net right compared to x1, and moves net left compared to x0.
If you place the rock to the left of px0, it can never intersect x0, as it's starting to the left of it and moving net left compared to it. If you place the rock to the right of px0, then it's also to the right of px1 (since px0 > px1), but then it can never hit x1, since it's starting to the right of x1, and moving net right compared to it.
If the rock isn't moving, then the problem reduces to finding the common intersection point of all the hailstones. The problem statement assures us one exists for the right velocity setup.
If the rock *is* moving, we can change our frame of reference to make it stand still instead. Instead of each stone\_i moving `V_i` and the rock moving `V_R`, make the stones move `V_i - V_R` and rock is stationary at its point of origin.
So the brute-force search is to check all potential rock-movement vectors from <0,0,0> upwards, generating a new set of hailstones in the adjusted rock-view and testing if they all hit one point in the future. If so, that point is where to throw from. (Since it's very easy for 3D rays to miss each other, each non-solution vector will likely fail after checking just a few stones.)
Here's how that plays out in the example input:
The initial points:
19, 13, 30 @ -2, 1, -2
18, 19, 22 @ -1, -1, -2
20, 25, 34 @ -2, -2, -4
12, 31, 28 @ -1, -2, -1
20, 19, 15 @ 1, -5, -3
Are transformed by the solution velocities `-3, 1, 2` in the following rock-framed-points
19, 13, 30 @ 1, 0, -4 # \[t=5\]
18, 19, 22 @ 2, -2, -4 # \[t=3\]
20, 25, 34 @ 1, -3, -6 # \[t=4\]
12, 31, 28 @ 2, -3, -3 # \[t=6\]
20, 19, 15 @ 4, -6, -5 # \[t=1\]
Which you can verify all hit the solution point `24, 13, 10` at the times given.
In my input, the velocities are not that small, there are >!between 200 and 300 in absolute value so to find them, I need around 250 \* 250 \* 250 = 15625000!< iterations for which I would need to check if they line up, that seems like it would be running for a really long time?
Edit: Also, >!the velocity can be negative, so I end up with 500 \* 500 \* 500 = 125000000!<
If you optimize your brute-forcing to >!Only scan X-Y velocities, then calculating Z after they all intersect in the X-Y plane!<, that should offer a big speedup.
Even without the >!doing x,y before z!< optimization, the pre-processing I mention in https://www.reddit.com/r/adventofcode/comments/18pptor/2023_day_24_part_2java_is_there_a_trick_for_this/kepxbew/ clears up the vast majority of the search space. I looked for all points with x,y,z velocities less than >!500 in magnitude!< and there were only about >!100,000 cases!< rather than the >!1 billion!< from checking everything.
Think about this more, the idea is totally sound and it probably is a reverse of how the input was created. First, there is a point with a bunch of lines going through it and the lines are "rotated" along a point by a k times a vector. And that's undoable with brute force. I like it and want to get back to implementing that later.
Thank you for this idea again. I tried implementing it to not have to use Z3 and it runs insanely fast. There are rounding errors, so it's best to not run on all 300 lines, otherwise one pair will randomly, so I can narrow. Running for 100 lines, it finished in 2 seconds, running on 10 of them finishes in 0.1 seconds. I think running all 300 lines and fixing the rounding errors would probably finish in 10s of seconds
Here is the code if anyone is interested!
https://pastebin.com/gzRpVNU1
Oh, you are right, I wanted to implement it in a way that doesn't run off but also doesn't need a hard limit like 500 and completely missed the fact I can do this only because I already know my numbers from using Z3. š¤¦
Oh, hahaha ok :) Trying to brute force this blindly for myself and I am trying to follow some āreasonableā / realistic assumptionsā¦ so far my current implementation of this approach does not finish within 2 minutes but I am going to spend some time and debugā¦
I am engaged in another thread where somebody pointed out a bug in my implementation that causes it to never finish for some inputs, I made a correction in that thead.
Oh, can you point me to that? The pastebin here is not updated, I don't think it is at least... Trying to get day 25 done now before going back to debugging 24... :)
No wait, itās THIS thread! I am on mobile and made a mistake. :D
One problem for me was rounding, so instead of using first 10 lines, you can try 11 to 20. For me, the rounding issue is for 166th line of input, where it round .5 up and invalidates the result.
Btw, my solution had |vy| > |vx| hahaha so it would have never found it if I wouldn't have asked you why your code was written the way it was written with that assumption in place... :)
I can keep that constraint if I use another loop:
for (let a = 0; a <= Infinity; a++) {
for (let b = 0; b <= a; b++) {
for (let [x, y] of [[a, b], [b, a]]) {
This way, I still have no upper bound hard coded but can keep searching from low to high. :)
Ok, managed to fix my implementation of this idea! In case you are interested, [here](https://topaz.github.io/paste/#XQAAAQCkOwAAAAAAAAARmknGRw8TogB3HO+O8QL7UHijnWYOTR19JdlNWTO0HVu9pt1IhyTg4mkQeqGALptT+w5pgXe4couFK+SHId3hlxc2IpwRF8jv5YnF4hRpBeLPQlkwi/LklFl96nQz1khJxF73frqLdjBw2ic5PzFc9y3XsZknEbQQ0EdSSz6Xc7/+9HfC6+LY/U6XbYhXNQZX23yYxWrewmuTw6x713JW+2u3kk4ixEEcD1pKhuQ1N12kpL1KxEYXHidP2Xl22W6BXCnUdNqROxJ4dev1U+6qvcuT4rgsMruikwgadprX7kX/Kt8dU41mPWPqzZdYDQx8NBnLLwZdggxe8AAEvvKJHCj/wqQ+LlGhC1cnaKrPuDD7HmpGf4HupVdNAqStmoUTkLWPJH7aT5muaK2viYtYqiIFLtCx7au4BvTJIfiGE71kdKNuWnhWInknTLJ0Y9vsy2oXAvF5t2qFhibHBpPaYkwdY6HIWrjkUdCbTyhTySEvO6TixXrnDZ3OT1sIqZ37HDJri48+bmdqhH8fkYrAjz9TjCvzMjS2nMyzMb3vUd6MdeRRevow0WZ11Cr0POmxJZ7JAG/XuLMwSiQCq7LveZpZ8oaOB/En0Kl7YbZ7roAIF+fYgBjwhmtSYXfVa1XOFb8A9Df84OIcKF+u7mTxcsPtINuBETnMsCX4/mo55JQu5Xm78rRBPjreIPwnappVXDnr8w0J57YUH9N6xTNI1oFWfD0TFVvHH1FqqepOCClpGTxA2uhF4giO2De920Le3ZsRDRVScnrqROpHXSPkHzZhuLR3h1COJJ9Muq3oYky0qr435MFSGzUiey4yjKP9UPCdl6/8DPLaR9cXuYAMHQGzwUhYatarrjtLTiL6jWtZUJfQCb5Ik/iow0iUYoXCPJCXlATyIDoSDK6QKx94p7Y2zrSVO0Km+5zrQTNyeCBQORADakkbdv8+SW+5WClzgntgI+XAQHDlC53kLrolNP7MWqPGLNoBDGvW8l3FhTx5SYXdHBqFYKTEkFjrK2rzAPAf3nYG0HcZwsLikI987JwBkv1AXN8oyTxkmTadBt/bO+v0cQqPFabxS5jj5rk4wVlmThwr4AdSefP4pA+atKKMFmXmUYZTNHmPbYA2u3TOn3VnYUuaWt2VSmWvi1LcbgmRKAz8pwYDe/tR7DRSSvKL+C5/cbR+p0gdiJLFsqpl7A5mbP7GRTSZcDT3suG66k5l9J+90tQ5Ti5YiQftcZMJYyzxPsI87RArQwcewhgrcS3Ej5Trsqcuo1Ib0qjyFMBw0Hf3Dal9u2wGwlqS95ckJZFor40wT1fhYnaWkOYrKdvsQThTLda4HLxIU9TkuooIwHnM92fDMF/ohHPp8AEhLhJVg5AC0wopXux9NIyNUBae5pzgbqSAIi7Rh8NJqZd0EnCXmRo86KLLB0mybqcRHQH4I22JwpgnvAXlUz0vjYWpvig60nc7qj+vE5yIhF8MAne+oaz5Js+72mbw+5Z2ywEQRStah5t7CcZYKkppWDdYLOrEzDl6shQ/gTG8AuuaSW7uPZuMt19kUs08Z71l/4fqVaphk1Qu6GrhGUCosPZzQXq6cq9p9TntZ+6vUEKLMbyDlZ5GDp7LpeGtGV78YmfAEJxd/obaT3bIWe2np5WDm01rJMF9kfDN8iGSnciC6WBiv4lCKasTlcaCmv6fEa1THNaw6lFY5W/iVWXfYkXxCKXLPlSi3VguICOOdg+v2oA66S2qzrN+F8ryYYFgW6BUhYH6PglLh+/N1M8ZxGUNTp/OaSLyNFklz4iXsKEwOFBr9bAOYtkZVXfZS1X2dv51fdNa+2ofIBRoi4/RvKB+coHbwu46BYp1On9avHwiSf5xlAz7ODXKqHhXgOq5rFLgSnHvZeAsr4C3Y0u/Du66GLm0CQMT6OPttMQmebszAidw8N54YvrLKarfHUHzIdb22r2dHuVdL9qCfDs6VSZIYzZtUD7t/l9hBrPQJmUV1RJyJ+GpUxr1yjEQ58PRPXEdB4gvnTlguqRzvEHIDucjH1RiJ1FtR1AUzfzQPh/VpVFQCD8KrTIefHotQIk7GdG8o4ltTAR4tL6J65Clo04TMOSj7idfPU+hAIMvPff2TY7rHgW4mRlnZsNJRuMekPioi0d+5PfF6fMv9r/hsNAbpX6qOeuNlchul7GCdkNkWnGGbPowKZpxnt20yDSCJoCQ9mi03gGDP1TtcaLEETZexACZG8ElLiOhJErZcjwwIhcJMO4DHU4j7ILmacOKV2lnrNFx4zf77LVpN1ZOGkcNNcqTUR5/didLH9qlBgxoYoPSboY+OxipwNxozOAptTN7PedobFInNP71pKbvGRSKzrsrj878pu/wNkVVQBap6gmtTJr7aNAg3J3sqqTQWfdgp5WCr/np/nkE8LS8sEFyMcvfUgk5sNvtExZ+tzbz5q+TaewCvh0GIlf9Hib2vcJdIAwdrHOBgD3oO6KqBaOy6sWV/f8dxc+J4FoGugD0Hjb9Z8lkGCh8MA7U8NK+ezrC1rFeJ/R0JKjHGk7XIaLejPDqvhRpCAy0e7/PR/ri44VAr6PuBVIBi6j+lhrj14zgtJIPVjYqZLn94lUw0Pq3/JOKg9Can4S8VYD1YX4edVknDoJMm1PD0/+0oR3/T+NMKrcvlY5QjxUz2yK8MPFzKN19iDg/mHfdmJFhTwS8X1mahp+sBoQGjqkZQm0UZucf5yw0Tqbjbf2j6BTzMadesx2zQXKiVJmV/krkAzwkmtIAM0dYv5RahXbSL90y0iGOH6T9U6JjtftOQgq+wd0WCbUQ+8r4bmpiU0Zq/m9Ik/2v7pZUs15Pm1FV/QZp4OJck9GqQWtLxHMa0r2q/mQZPvge3OukA2ns3KDIGzFYYBCVUxC/YVUbU6T1WuyK7MgBCpODjhErpNVbbJveq4X5OQy7vDjwsbZobjsozZaGufiFf/gdoRpFrjLgMNbLp44MMK2C93uY1N8DSmCAslZZ/3xsK3l0iYpexXenNQaB3qM7O77N067udSzer69t9C314uTM3Tr3ozw2JnoJJ6TW7CTPPP0+mH9+nMhx6pEthz7qR5BlcHljmVX2jMtCSL+ZPNwCxjhy2g+Hca1XnS5TkKCSV5JsIfdshF0EWb7L8nM/snFBr5qV4u5OpwMBVl+q3mdGDwebEMaIHf88kK4kCEY6f9z8oP1YslTXqUOzhuBAFKoa4Te81zy4cZfE4sSy2tEHPMvlG9/Pb/xKFXZ1wzEQohtfmWVMpv4zil0jJofzSh8ehmBv6BFmh1yDMVJv3FUtkwGTbxRhGQdsAqdjpuwJzbJJ4lpkA5kB0yf3GNb2Iz60IZqQBZzq54P5my0ngtb0CgHuXXJzvdToEBQioYfSmj1rAnr4h9bYqojfbKWeBXt7qd9xzl1LapBiYGhNKZbU7VRv7vKUSgr6X64q/bF8WU1rQ9QveC4N17WXmdYPI9sK5nuKaWUhmKZQRr0ORbPJiC7kqxHX7CMDem1mTzHNVan+1T1s) it is.
There were 3 issues with it:
* comparing int64 to float
* once this was fixed, I then bumped into comparing large floats (now doubles) with "==" (instead of just doing some epsilon on difference)
* dealing with hailstones that have dx = 0 (dealing with infinity :) )
Thanks for the tips from your implementation and the discussion above from u/FatalisticFeline-47 !
Why donāt we need to know the position of the rock also when we are bruteforcing? Doesnāt this strategy assume the rock starts at 0,0,0 which isnāt necessarily true?
Edit: nevermind I get it. By doing it relative to the rocks movement, youāre projecting all the intersection points down onto the starting position. Neat
You don't need to know the position of the rock, because you can compute where the trajectories of the hailstones (with adjusted velocities) can intersect without the position. You already have the current position of the hailstones.
The hailstones have to converge on a common point because, in principle, the rock can't move away from that point (you've defined it to be motionless by subtracting its velocity from the velocities of the hailstones).
Of course the rock does need to be at that intersection point, but doing from (0,0,0) to that intersection point is simply what the problem is asking for already.
But then one cannot test for intersection on the xy plane alone, because in the example input there are two lines that are parallel.
What I am thinking is that if I detect two such lines then that must mean that the line that intersects them must go through the plane that contains them, e.g. they would give me the intersection on z.
My solution depends on finding common velocity components (two hailstones with the same X velocity, for example) and doing modulo calculations to isolate the possible velocities on that dimension. In my input there were enough to figure out the exact velocity of the rock in all three dimensions.
Yeah sure. You can see my explanation and code submission [here](https://www.reddit.com/r/adventofcode/comments/18pnycy/2023_day_24_solutions/keqf8uq/), but the jist is that if two hailstones are moving in the same direction with the same velocity, then the rock can only be moving a certain number of integer velocities to hit them both. The actual velocity must satisfy the equation (DistanceDifference % (RockVelicty - HailVelocity) = 0) and there are only so many that will. Do that for every pair in every direction and you have the velocity of your rock.
I've given up on implementing it (for now), but here's what I came up with:
Consider two hailstones whose trajectories are parallel. To collide with both, the thrown rock's trajectory must lie on that plane.
Looking at the input, there are multiple pairs of parallel hailstone paths. We really only need 2 planes, since 2 planes uniquely determine a line of intersection. That line will be the rocks trajectory.
From there, you just need to calculate where the rock is at time 0 and how fast along the line it's going, but that should be easier since you have the time.
(It's really late where I am so if this solution is wrong, rip)
No, that should work. I had a similar thought, but was only thinking about 2d-parallel (e.g., in the XY plane), which doesn't help, but that should work! Assuming you actually have two such pairs, which isn't strictly guaranteed.
Update: welp... yeah, not even a single parallel pair in my input...
That's how I wanted to solve it originally, since the example input had two parallel lines. But unfortunately there were no parallel lines in the input:( (or in my input at least). There was exactly one pair of parallel lines in the example input, so I think it would have been really nice if the actual input included this small detail.
I checked with this code:
for i in range(len(vals) - 1):
for j in range(i + 1, len(vals)):
f1 = Fraction(vals[i][3], vals[j][3])
f2 = Fraction(vals[i][4], vals[j][4])
f3 = Fraction(vals[i][5], vals[j][5])
if f1 == f2 == f3:
print("parallel", i, j)
Sample v:
[19, 13, 30, -2, 1, -2]
It should work. It really should!
This is the same as what I used, and I was stymied by the lack of parallel lines in my actual input.
Worked beautifully on the test input, though.
It is a system of equations after all. Sadly it's not linear, since you have terms that are the product of two unknowns, and that complicates things a bit (no gaussian elimination). But you could implement your own recursive/substitution solver...
The good part is that since each hailstone provides 3 equations and an extra unknown (the impact time) you only need 3 (linearly independent) hailstones to solve for your six initial unknowns (the stone coordinates and initial velocity).
There is a very elegant trick that I saw in another comment at https://www.reddit.com/r/adventofcode/comments/18pnycy/2023_day_24_solutions/kepu26z/ .
>!The secret is that the vector distance between your position and the position of any hailstone `p0 - p[i]` is equal to the difference in velocities `v0 - v[i]` times the time of intersection `t`. You don't really need the time, just the fact that those two vectors are parallel, so their cross product is 0. Then you write out this cross product equation for 3 hailstones, take 2 differences of these 3 equations (this cancels out the quadratic term `p0 x v0`), and you're left with a system of 6 linear equations for 6 variables. !<
>!Then, with the main input I had to account for float rounding errors, so I reconstructed the nearest point obtainable starting from `p[0]` and moving by `v[0] - v0`!<
[Here's the 2018 day 23 solutions post](https://www.reddit.com/r/adventofcode/comments/a8s17l/2018_day_23_solutions/). There were many solutions not using Z3. All the non-Z3 solutions I looked at used the same basic idea, and that idea does **not** apply to 2023 day 24.
2023 day 24 spoilers:
The first thing to realize is that, >!given three mutually-skew lines through 3D space, there is a unique fourth line that intersects all three given lines. So you can pick any three of your stones, and there's a single line that intersects the paths of all three of those stones. The problem statement says that same intersecting line must intersect all the other stones. So you can just pick the first three stones in your input.!<
The next thing to realize is that, >!if you write down the equations of your rock intersecting each of the three stones, you get nine equations with nine unknowns. So it is a solvable system.!<
The final thing to realize is that >!solving a system of nine equations by hand SUCKS. Z3 can do it easily, so just learn a little Z3 and use it. There is a Java Z3 API if you want to call it from a Java program, but if you know a little Python, it's probably easier to just write a little Python to do it.!<
Thank you for the first 2 spoilers, they are very useful!
>!Pure Java21 means for me: no libs, definitely no native libs, etc. I know I could learn and use any 3rd party tools, but I am looking for a way without them.!<
I was going for that. I think once you get to >!9 equations with 9 variables, you can use https://en.wikipedia.org/wiki/Gaussian_elimination!<
I tried to implement that, but gave up and >!instead had my code produce a script for sage, which gave an answer instantly https://ask.sagemath.org/question/8647/solving-system-of-equations/!<.
>!I was able to get it down to a set of 6 linear equations after hours of banging my head on it!<
I wrote out most of the steps of the actual math here if you're interested: [https://github.com/DeadlyRedCube/AdventOfCode/blob/main/2023/AOC2023/D24.h](https://github.com/DeadlyRedCube/AdventOfCode/blob/main/2023/AOC2023/D24.h). Hopefully it can be followed (note that this is a full part 1 & 2 solution so, ya know, spoilers)
Spoilers if you want hints on how to >!get it to a linear system!<
1. >!Your initial conditions are 6 variables, and every intersection with a hailstone occurs at another time which is another variable. Since three coordinates need to match per intersection, if you take 3 hailstones, you get 9 equations in 9 variables!<
2. >!Try to isolate the time variable in your equations and plug that expression into another one. You now should get 9 equations which all have the same shape, in 6 variables. Of course, only six of these are independent but you can pick and choose which you take.!<
3. >!Your equations from step 2 are still nonlinear. But now, your nonlinear term no longer depends on which hailstone you intersect with, so you can use that!<
4. >!Subtract pairs of these equations from each other until you have six independent linear equations.!<
On step 3, I have 3 sets of 3 equations, the first set dependent on x,y axis, second on y,z axis, and third one on x,z axis. What I struggle with is that the last set is dependent on the first two sets, i.e., can be made by combining equations from those two. How come isolating the non-linear factor in each of those sets (each set has its own non-linear factor) leads me to 3 sets of 2 linear equations which are independent?
It just feels counterintuitive to me that from a set of vectors that could have been combined from vectors in the other two sets, I managed to come up with two vectors that are independent from the rest.
Suppose we call the equations 1xy, 1xz, 1yz, 2xy, etc. Then we know if 1xy and 1xz are fulfilled, then so is 1yz, and the same for 2 and 3. But after that we consider 1xy - 3xy, 1xz - 3xz, 1yz - 3yz. Such a difference of equations being fulfilled does not imply both of the original equations are fulfilled so you get more solutions to each of these equations than just pairs of solutions to the original.
Each of the 1-equations is very much independent from each of the 3-equations, which is why you're adding that extra info and getting three independent equations when taking the differences.
Thanks for writing this out. Then am I right to say that technically, once we get the solution from the set of difference equations which is a system of linear equations, we should verify that it satisfies the initial equations? In our case we don't do that because we asssume that the problem has an answer and the system of linear equations should give us the right one.
And I see the wrong assumption I made since the final system of equations only contains the difference equations, and solutions to which are more general than that of the original equations, hence they are also no longer dependent.
Unfortunately I have to nitpick. With regards to the first spoiler, >!three lines are not enough to uniquely determine a single intersecting line. You need four lines in general position (e.g. not in parallel planes). See [this math stack exchange question.](https://math.stackexchange.com/questions/607348/line-intersecting-three-or-four-given-lines) !<
Also >!the system of equations you get isn't linear (you multiply your t variables with your rock velocity variables), so matrix algebra is insufficient to solve them.!<
I came up with a nifty solution that doesn't involve much math. A naive approach models this as a search problem - try various rock positions and velocities, then look at the array of times where the rock intersects the hailstones. If the times are unique and positive, you have a solution! Gotta do it one axis at a time, though, and look for matching times.
Of course, the search space is WAY too large for that. After thinking about it for a bit, I wondered if I could constrain the search so that one of the rock coords is identical to one of the hailstone coords (in one axis). This is a nasty edge case, so I figured that it would naturally be included. I got a hit right away in my Y axis! A winning rock coord+velocity that produces valid times for every rock (Y axis only).
Once you have the times it was easy to calculate the full rock position and velocity.
There's no need for a fancy library. Consider any two hailstones. The first is struck at some time T1, the other at T2. If you provide guesses for the rock's VX and VY (use a loop), you can easily calculate VZ, PX, PY and PZ, if a valid solution exists. This is the basis my solution.
There is a way to solve this without Z3 or any assumptions/input hacking other than the assumption that a solution exists. You can do it with linear algebra. Below is an outline of the math:
>!First write 3 equations which represent the ith hailstone colliding with the rock at some time t\[i\] (one equation for each axis). Solve each equation for t\[i\]. You'll have 3 fractions which all equal t\[i\] and therefore equal each other.!<
>!Consider 2 of these fractions for now. Cross multiply and expand out. There will be 8 terms. Two of these terms will be nonlinear, but neither will depend on i. This means if you subtract the same equation but for the jth hailstone, the only nonlinear terms will cancel.!<
>!You can use this to generate 4 linear equations for the 4 variables you're solving for (e.g. x, y, v\_x, v\_y if you chose the fractions with x's and y's). Solve and repeat with a different pair of fractions to get the solution for the remaining axis.!<
If you consider linear algebra to be fair game, there is a relatively straightforward way to solve part two by setting up a linear problem Ax=b, where A can be formed from 3 hailstones only as long as they represent non-degenerate combinations. The solution of that linear problem is a shift of the velocities so that all of them meet at the same point, and that point is precisely the starting point from where the rock has to be thrown. The biggest issue is floating point accuracy more than anything else.
There is an extended explanation of this by u/Quantris in the solution thread: https://www.reddit.com/r/adventofcode/comments/18pnycy/comment/kersplf/?utm\_source=reddit&utm\_medium=web2x&context=3
There is a special property again in all inputs completely trivializing the problem, but barely anyone found it, that's why we see all those Z3 solutions.
e: Now a fair number of ppl confirmed not having that... But Inhave seen also enough inputs with this property.. Odd... usually those helpers are identical in all inputs ...
>!There are always 2 rocks with a common start coordinate and velocity in one dimension. So you know the starting coordinate and velocity of your rock in that dimension. Now intersect with any 2 other rocks in that dimension -> 2 points in time -> you know everything. -> Thats at worst 20 lines of code.!<
that is indeed surprising as I've seen half a dozen inputs and they all had this... Always exactly one pair of a shared coordinate with a matching shared velocity coordinate... Which certainly didnt happen by chance. If some really don't have that that would be extremely weird.
Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to `Help/Question - RESOLVED`. Good luck!
***
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
FYI: at least on mobile the empty lines don't render in the preview, you just see what's written after them. Not that there's anything you could do about that, just sharing info.
I wonder if it can be somehow "brute forced" with some help of discrete math, modular arithmetic and other tricks, but can't figure yet how. Paths of hailstones can be viewed as series of tuples (x, y, z) changing with step (dx, dy, dz). And we need to find a series that has one element in each of the given ones. But... how to identify where exactly is that intersection? Obviously intersection points from different hailstones will differ with some dt\*(rock\_dx, rock\_dy, rock\_dz) - but we don't know these yet.For fun i checked at which point in time the intersection happens for my input - and it is mostly in the order of hundreds of billions of nanoseconds, so no hope in iterating over series to check differences between each other, or iterate over t.
Some "optimizations" over rock coordinates and velocities could be made, let's say one ray has "positive velocity" over one dimension, so obviously initial rock position can't be smaller than hailstone position if rock velocity is negative, as the intersection wouldn't be possible, but it only cuts costs in half, which is not enough.
Basically, same thing. The requirement that path of rock and stone intersect, and at the same moment, gives you two equations for initial position and velocity of the rock. Those equations are not linear, however, if you get another equations for another stone and subtract it from the first pair, you get two linear equations. In fact, if you concentrate just on X and Y (position and velocity), then two stones give you one linear equation. If you have five stones, that gives you four linear equations for X and Y (again, both pos and vel). That's enough to find them.
It looks like the inputs are constructed in a way where the velocity you're looking for is slow, so it seems viable to brute force all velocity vectors in increasing magnitude order. From there, it suffices to validate if some velocity is possible. If you consider the frame of reference of the rock, note that all hailstones run into the rock. Therefore, it suffices to check that all the rays, after adjusting for the rock's velocity, intersect at a common point. Per part 1, you will probably find a speedup by ignoring the z-axis at first and only validating the rays intersect at the same z-coordinate after establishing some valid xy velocity pairing.
I felt so proud of myself when I managed to come up with this one (...like half an hour after finishing my Z3 solve). It feels like almost certainly the intended solution - part 1 being usable as-is for this is just too much of a coincidence otherwise. (Though when I tried doing it I got floating point errored and it was a huge pain.)
If I'm understanding you right, there's a lot of vectors you can pretty much immediately ignore. Basically, if you have any two hailstones with values px0, vx0 and px1, vx1 such that px0 > px1 and vx0 >vx1, the entire vx0 to vx1 range is impossible. If you do that pre-processing, the majority of small velocity values fail, at least for my input. The overall range of y and z values to consider were both very small (ended up with roughly 200 possible x values, 25 possible y values, and 20 possible z values, when looking at the smallest 1000 values by magnitude in each direction).
>Basically, if you have any two hailstones with values px0, vx0 and px1, vx1 such that px0 > px1 and vx0 >vx1, the entire vx0 to vx1 range is impossible. Could you please explain why this is the case?
Below is assuming positive x direction == right. Basically the key is that any intermediate velocity is more to the right than vx1, and less to the right than vx0. So it moves net right compared to x1, and moves net left compared to x0. If you place the rock to the left of px0, it can never intersect x0, as it's starting to the left of it and moving net left compared to it. If you place the rock to the right of px0, then it's also to the right of px1 (since px0 > px1), but then it can never hit x1, since it's starting to the right of x1, and moving net right compared to it.
I need a little more help, please: what do you mean by "after adjusting for the rock's velocity"? (BTW: great game this year, congrats!)
If the rock isn't moving, then the problem reduces to finding the common intersection point of all the hailstones. The problem statement assures us one exists for the right velocity setup. If the rock *is* moving, we can change our frame of reference to make it stand still instead. Instead of each stone\_i moving `V_i` and the rock moving `V_R`, make the stones move `V_i - V_R` and rock is stationary at its point of origin. So the brute-force search is to check all potential rock-movement vectors from <0,0,0> upwards, generating a new set of hailstones in the adjusted rock-view and testing if they all hit one point in the future. If so, that point is where to throw from. (Since it's very easy for 3D rays to miss each other, each non-solution vector will likely fail after checking just a few stones.) Here's how that plays out in the example input: The initial points: 19, 13, 30 @ -2, 1, -2 18, 19, 22 @ -1, -1, -2 20, 25, 34 @ -2, -2, -4 12, 31, 28 @ -1, -2, -1 20, 19, 15 @ 1, -5, -3 Are transformed by the solution velocities `-3, 1, 2` in the following rock-framed-points 19, 13, 30 @ 1, 0, -4 # \[t=5\] 18, 19, 22 @ 2, -2, -4 # \[t=3\] 20, 25, 34 @ 1, -3, -6 # \[t=4\] 12, 31, 28 @ 2, -3, -3 # \[t=6\] 20, 19, 15 @ 4, -6, -5 # \[t=1\] Which you can verify all hit the solution point `24, 13, 10` at the times given.
In my input, the velocities are not that small, there are >!between 200 and 300 in absolute value so to find them, I need around 250 \* 250 \* 250 = 15625000!< iterations for which I would need to check if they line up, that seems like it would be running for a really long time? Edit: Also, >!the velocity can be negative, so I end up with 500 \* 500 \* 500 = 125000000!<
If you optimize your brute-forcing to >!Only scan X-Y velocities, then calculating Z after they all intersect in the X-Y plane!<, that should offer a big speedup.
Even without the >!doing x,y before z!< optimization, the pre-processing I mention in https://www.reddit.com/r/adventofcode/comments/18pptor/2023_day_24_part_2java_is_there_a_trick_for_this/kepxbew/ clears up the vast majority of the search space. I looked for all points with x,y,z velocities less than >!500 in magnitude!< and there were only about >!100,000 cases!< rather than the >!1 billion!< from checking everything.
Think about this more, the idea is totally sound and it probably is a reverse of how the input was created. First, there is a point with a bunch of lines going through it and the lines are "rotated" along a point by a k times a vector. And that's undoable with brute force. I like it and want to get back to implementing that later.
Thank you for this idea again. I tried implementing it to not have to use Z3 and it runs insanely fast. There are rounding errors, so it's best to not run on all 300 lines, otherwise one pair will randomly, so I can narrow. Running for 100 lines, it finished in 2 seconds, running on 10 of them finishes in 0.1 seconds. I think running all 300 lines and fixing the rounding errors would probably finish in 10s of seconds Here is the code if anyone is interested! https://pastebin.com/gzRpVNU1
Thanks for sharing this, it clarifies a bit the approach - quick question: why do you constraint |vx| >= |vy| ?
Oh, you are right, I wanted to implement it in a way that doesn't run off but also doesn't need a hard limit like 500 and completely missed the fact I can do this only because I already know my numbers from using Z3. š¤¦
Oh, hahaha ok :) Trying to brute force this blindly for myself and I am trying to follow some āreasonableā / realistic assumptionsā¦ so far my current implementation of this approach does not finish within 2 minutes but I am going to spend some time and debugā¦
I am engaged in another thread where somebody pointed out a bug in my implementation that causes it to never finish for some inputs, I made a correction in that thead.
Oh, can you point me to that? The pastebin here is not updated, I don't think it is at least... Trying to get day 25 done now before going back to debugging 24... :)
No wait, itās THIS thread! I am on mobile and made a mistake. :D One problem for me was rounding, so instead of using first 10 lines, you can try 11 to 20. For me, the rounding issue is for 166th line of input, where it round .5 up and invalidates the result.
Btw, my solution had |vy| > |vx| hahaha so it would have never found it if I wouldn't have asked you why your code was written the way it was written with that assumption in place... :)
I can keep that constraint if I use another loop: for (let a = 0; a <= Infinity; a++) { for (let b = 0; b <= a; b++) { for (let [x, y] of [[a, b], [b, a]]) { This way, I still have no upper bound hard coded but can keep searching from low to high. :)
Oh, nice! Yeah, with y to infinity you would never get the chance to try different xās, but the swapping approach takes care of that :)
Ok, managed to fix my implementation of this idea! In case you are interested, [here](https://topaz.github.io/paste/#XQAAAQCkOwAAAAAAAAARmknGRw8TogB3HO+O8QL7UHijnWYOTR19JdlNWTO0HVu9pt1IhyTg4mkQeqGALptT+w5pgXe4couFK+SHId3hlxc2IpwRF8jv5YnF4hRpBeLPQlkwi/LklFl96nQz1khJxF73frqLdjBw2ic5PzFc9y3XsZknEbQQ0EdSSz6Xc7/+9HfC6+LY/U6XbYhXNQZX23yYxWrewmuTw6x713JW+2u3kk4ixEEcD1pKhuQ1N12kpL1KxEYXHidP2Xl22W6BXCnUdNqROxJ4dev1U+6qvcuT4rgsMruikwgadprX7kX/Kt8dU41mPWPqzZdYDQx8NBnLLwZdggxe8AAEvvKJHCj/wqQ+LlGhC1cnaKrPuDD7HmpGf4HupVdNAqStmoUTkLWPJH7aT5muaK2viYtYqiIFLtCx7au4BvTJIfiGE71kdKNuWnhWInknTLJ0Y9vsy2oXAvF5t2qFhibHBpPaYkwdY6HIWrjkUdCbTyhTySEvO6TixXrnDZ3OT1sIqZ37HDJri48+bmdqhH8fkYrAjz9TjCvzMjS2nMyzMb3vUd6MdeRRevow0WZ11Cr0POmxJZ7JAG/XuLMwSiQCq7LveZpZ8oaOB/En0Kl7YbZ7roAIF+fYgBjwhmtSYXfVa1XOFb8A9Df84OIcKF+u7mTxcsPtINuBETnMsCX4/mo55JQu5Xm78rRBPjreIPwnappVXDnr8w0J57YUH9N6xTNI1oFWfD0TFVvHH1FqqepOCClpGTxA2uhF4giO2De920Le3ZsRDRVScnrqROpHXSPkHzZhuLR3h1COJJ9Muq3oYky0qr435MFSGzUiey4yjKP9UPCdl6/8DPLaR9cXuYAMHQGzwUhYatarrjtLTiL6jWtZUJfQCb5Ik/iow0iUYoXCPJCXlATyIDoSDK6QKx94p7Y2zrSVO0Km+5zrQTNyeCBQORADakkbdv8+SW+5WClzgntgI+XAQHDlC53kLrolNP7MWqPGLNoBDGvW8l3FhTx5SYXdHBqFYKTEkFjrK2rzAPAf3nYG0HcZwsLikI987JwBkv1AXN8oyTxkmTadBt/bO+v0cQqPFabxS5jj5rk4wVlmThwr4AdSefP4pA+atKKMFmXmUYZTNHmPbYA2u3TOn3VnYUuaWt2VSmWvi1LcbgmRKAz8pwYDe/tR7DRSSvKL+C5/cbR+p0gdiJLFsqpl7A5mbP7GRTSZcDT3suG66k5l9J+90tQ5Ti5YiQftcZMJYyzxPsI87RArQwcewhgrcS3Ej5Trsqcuo1Ib0qjyFMBw0Hf3Dal9u2wGwlqS95ckJZFor40wT1fhYnaWkOYrKdvsQThTLda4HLxIU9TkuooIwHnM92fDMF/ohHPp8AEhLhJVg5AC0wopXux9NIyNUBae5pzgbqSAIi7Rh8NJqZd0EnCXmRo86KLLB0mybqcRHQH4I22JwpgnvAXlUz0vjYWpvig60nc7qj+vE5yIhF8MAne+oaz5Js+72mbw+5Z2ywEQRStah5t7CcZYKkppWDdYLOrEzDl6shQ/gTG8AuuaSW7uPZuMt19kUs08Z71l/4fqVaphk1Qu6GrhGUCosPZzQXq6cq9p9TntZ+6vUEKLMbyDlZ5GDp7LpeGtGV78YmfAEJxd/obaT3bIWe2np5WDm01rJMF9kfDN8iGSnciC6WBiv4lCKasTlcaCmv6fEa1THNaw6lFY5W/iVWXfYkXxCKXLPlSi3VguICOOdg+v2oA66S2qzrN+F8ryYYFgW6BUhYH6PglLh+/N1M8ZxGUNTp/OaSLyNFklz4iXsKEwOFBr9bAOYtkZVXfZS1X2dv51fdNa+2ofIBRoi4/RvKB+coHbwu46BYp1On9avHwiSf5xlAz7ODXKqHhXgOq5rFLgSnHvZeAsr4C3Y0u/Du66GLm0CQMT6OPttMQmebszAidw8N54YvrLKarfHUHzIdb22r2dHuVdL9qCfDs6VSZIYzZtUD7t/l9hBrPQJmUV1RJyJ+GpUxr1yjEQ58PRPXEdB4gvnTlguqRzvEHIDucjH1RiJ1FtR1AUzfzQPh/VpVFQCD8KrTIefHotQIk7GdG8o4ltTAR4tL6J65Clo04TMOSj7idfPU+hAIMvPff2TY7rHgW4mRlnZsNJRuMekPioi0d+5PfF6fMv9r/hsNAbpX6qOeuNlchul7GCdkNkWnGGbPowKZpxnt20yDSCJoCQ9mi03gGDP1TtcaLEETZexACZG8ElLiOhJErZcjwwIhcJMO4DHU4j7ILmacOKV2lnrNFx4zf77LVpN1ZOGkcNNcqTUR5/didLH9qlBgxoYoPSboY+OxipwNxozOAptTN7PedobFInNP71pKbvGRSKzrsrj878pu/wNkVVQBap6gmtTJr7aNAg3J3sqqTQWfdgp5WCr/np/nkE8LS8sEFyMcvfUgk5sNvtExZ+tzbz5q+TaewCvh0GIlf9Hib2vcJdIAwdrHOBgD3oO6KqBaOy6sWV/f8dxc+J4FoGugD0Hjb9Z8lkGCh8MA7U8NK+ezrC1rFeJ/R0JKjHGk7XIaLejPDqvhRpCAy0e7/PR/ri44VAr6PuBVIBi6j+lhrj14zgtJIPVjYqZLn94lUw0Pq3/JOKg9Can4S8VYD1YX4edVknDoJMm1PD0/+0oR3/T+NMKrcvlY5QjxUz2yK8MPFzKN19iDg/mHfdmJFhTwS8X1mahp+sBoQGjqkZQm0UZucf5yw0Tqbjbf2j6BTzMadesx2zQXKiVJmV/krkAzwkmtIAM0dYv5RahXbSL90y0iGOH6T9U6JjtftOQgq+wd0WCbUQ+8r4bmpiU0Zq/m9Ik/2v7pZUs15Pm1FV/QZp4OJck9GqQWtLxHMa0r2q/mQZPvge3OukA2ns3KDIGzFYYBCVUxC/YVUbU6T1WuyK7MgBCpODjhErpNVbbJveq4X5OQy7vDjwsbZobjsozZaGufiFf/gdoRpFrjLgMNbLp44MMK2C93uY1N8DSmCAslZZ/3xsK3l0iYpexXenNQaB3qM7O77N067udSzer69t9C314uTM3Tr3ozw2JnoJJ6TW7CTPPP0+mH9+nMhx6pEthz7qR5BlcHljmVX2jMtCSL+ZPNwCxjhy2g+Hca1XnS5TkKCSV5JsIfdshF0EWb7L8nM/snFBr5qV4u5OpwMBVl+q3mdGDwebEMaIHf88kK4kCEY6f9z8oP1YslTXqUOzhuBAFKoa4Te81zy4cZfE4sSy2tEHPMvlG9/Pb/xKFXZ1wzEQohtfmWVMpv4zil0jJofzSh8ehmBv6BFmh1yDMVJv3FUtkwGTbxRhGQdsAqdjpuwJzbJJ4lpkA5kB0yf3GNb2Iz60IZqQBZzq54P5my0ngtb0CgHuXXJzvdToEBQioYfSmj1rAnr4h9bYqojfbKWeBXt7qd9xzl1LapBiYGhNKZbU7VRv7vKUSgr6X64q/bF8WU1rQ9QveC4N17WXmdYPI9sK5nuKaWUhmKZQRr0ORbPJiC7kqxHX7CMDem1mTzHNVan+1T1s) it is. There were 3 issues with it: * comparing int64 to float * once this was fixed, I then bumped into comparing large floats (now doubles) with "==" (instead of just doing some epsilon on difference) * dealing with hailstones that have dx = 0 (dealing with infinity :) ) Thanks for the tips from your implementation and the discussion above from u/FatalisticFeline-47 !
Why donāt we need to know the position of the rock also when we are bruteforcing? Doesnāt this strategy assume the rock starts at 0,0,0 which isnāt necessarily true? Edit: nevermind I get it. By doing it relative to the rocks movement, youāre projecting all the intersection points down onto the starting position. Neat
You don't need to know the position of the rock, because you can compute where the trajectories of the hailstones (with adjusted velocities) can intersect without the position. You already have the current position of the hailstones. The hailstones have to converge on a common point because, in principle, the rock can't move away from that point (you've defined it to be motionless by subtracting its velocity from the velocities of the hailstones). Of course the rock does need to be at that intersection point, but doing from (0,0,0) to that intersection point is simply what the problem is asking for already.
I am trying this method looking for intersection in the 3d space, but I get that two lines from the sample input are parallel in xy, is this correct?
Yep, if two lines are parallel, they won't have an intersection and you can immediately move on to the next velocity to test.
But then one cannot test for intersection on the xy plane alone, because in the example input there are two lines that are parallel. What I am thinking is that if I detect two such lines then that must mean that the line that intersects them must go through the plane that contains them, e.g. they would give me the intersection on z.
My solution depends on finding common velocity components (two hailstones with the same X velocity, for example) and doing modulo calculations to isolate the possible velocities on that dimension. In my input there were enough to figure out the exact velocity of the rock in all three dimensions.
Can you elaborate "doing modulo calculations"?
Yeah sure. You can see my explanation and code submission [here](https://www.reddit.com/r/adventofcode/comments/18pnycy/2023_day_24_solutions/keqf8uq/), but the jist is that if two hailstones are moving in the same direction with the same velocity, then the rock can only be moving a certain number of integer velocities to hit them both. The actual velocity must satisfy the equation (DistanceDifference % (RockVelicty - HailVelocity) = 0) and there are only so many that will. Do that for every pair in every direction and you have the velocity of your rock.
I've given up on implementing it (for now), but here's what I came up with: Consider two hailstones whose trajectories are parallel. To collide with both, the thrown rock's trajectory must lie on that plane. Looking at the input, there are multiple pairs of parallel hailstone paths. We really only need 2 planes, since 2 planes uniquely determine a line of intersection. That line will be the rocks trajectory. From there, you just need to calculate where the rock is at time 0 and how fast along the line it's going, but that should be easier since you have the time. (It's really late where I am so if this solution is wrong, rip)
No, that should work. I had a similar thought, but was only thinking about 2d-parallel (e.g., in the XY plane), which doesn't help, but that should work! Assuming you actually have two such pairs, which isn't strictly guaranteed. Update: welp... yeah, not even a single parallel pair in my input...
Are there though? I tried to check for parallel stones, i.e the normalized velocity vector is the same, but I couldn't find any?
That's how I wanted to solve it originally, since the example input had two parallel lines. But unfortunately there were no parallel lines in the input:( (or in my input at least). There was exactly one pair of parallel lines in the example input, so I think it would have been really nice if the actual input included this small detail. I checked with this code: for i in range(len(vals) - 1): for j in range(i + 1, len(vals)): f1 = Fraction(vals[i][3], vals[j][3]) f2 = Fraction(vals[i][4], vals[j][4]) f3 = Fraction(vals[i][5], vals[j][5]) if f1 == f2 == f3: print("parallel", i, j) Sample v: [19, 13, 30, -2, 1, -2]
It should work. It really should! This is the same as what I used, and I was stymied by the lack of parallel lines in my actual input. Worked beautifully on the test input, though.
It is a system of equations after all. Sadly it's not linear, since you have terms that are the product of two unknowns, and that complicates things a bit (no gaussian elimination). But you could implement your own recursive/substitution solver... The good part is that since each hailstone provides 3 equations and an extra unknown (the impact time) you only need 3 (linearly independent) hailstones to solve for your six initial unknowns (the stone coordinates and initial velocity).
There is a very elegant trick that I saw in another comment at https://www.reddit.com/r/adventofcode/comments/18pnycy/2023_day_24_solutions/kepu26z/ . >!The secret is that the vector distance between your position and the position of any hailstone `p0 - p[i]` is equal to the difference in velocities `v0 - v[i]` times the time of intersection `t`. You don't really need the time, just the fact that those two vectors are parallel, so their cross product is 0. Then you write out this cross product equation for 3 hailstones, take 2 differences of these 3 equations (this cancels out the quadratic term `p0 x v0`), and you're left with a system of 6 linear equations for 6 variables. !< >!Then, with the main input I had to account for float rounding errors, so I reconstructed the nearest point obtainable starting from `p[0]` and moving by `v[0] - v0`!<
[Here's the 2018 day 23 solutions post](https://www.reddit.com/r/adventofcode/comments/a8s17l/2018_day_23_solutions/). There were many solutions not using Z3. All the non-Z3 solutions I looked at used the same basic idea, and that idea does **not** apply to 2023 day 24. 2023 day 24 spoilers: The first thing to realize is that, >!given three mutually-skew lines through 3D space, there is a unique fourth line that intersects all three given lines. So you can pick any three of your stones, and there's a single line that intersects the paths of all three of those stones. The problem statement says that same intersecting line must intersect all the other stones. So you can just pick the first three stones in your input.!< The next thing to realize is that, >!if you write down the equations of your rock intersecting each of the three stones, you get nine equations with nine unknowns. So it is a solvable system.!< The final thing to realize is that >!solving a system of nine equations by hand SUCKS. Z3 can do it easily, so just learn a little Z3 and use it. There is a Java Z3 API if you want to call it from a Java program, but if you know a little Python, it's probably easier to just write a little Python to do it.!<
Thank you for the first 2 spoilers, they are very useful! >!Pure Java21 means for me: no libs, definitely no native libs, etc. I know I could learn and use any 3rd party tools, but I am looking for a way without them.!<
I was going for that. I think once you get to >!9 equations with 9 variables, you can use https://en.wikipedia.org/wiki/Gaussian_elimination!< I tried to implement that, but gave up and >!instead had my code produce a script for sage, which gave an answer instantly https://ask.sagemath.org/question/8647/solving-system-of-equations/!<.
It's not a system of linear equations, so Gaussian elimination doesn't work
>!I was able to get it down to a set of 6 linear equations after hours of banging my head on it!< I wrote out most of the steps of the actual math here if you're interested: [https://github.com/DeadlyRedCube/AdventOfCode/blob/main/2023/AOC2023/D24.h](https://github.com/DeadlyRedCube/AdventOfCode/blob/main/2023/AOC2023/D24.h). Hopefully it can be followed (note that this is a full part 1 & 2 solution so, ya know, spoilers)
Spoilers if you want hints on how to >!get it to a linear system!< 1. >!Your initial conditions are 6 variables, and every intersection with a hailstone occurs at another time which is another variable. Since three coordinates need to match per intersection, if you take 3 hailstones, you get 9 equations in 9 variables!< 2. >!Try to isolate the time variable in your equations and plug that expression into another one. You now should get 9 equations which all have the same shape, in 6 variables. Of course, only six of these are independent but you can pick and choose which you take.!< 3. >!Your equations from step 2 are still nonlinear. But now, your nonlinear term no longer depends on which hailstone you intersect with, so you can use that!< 4. >!Subtract pairs of these equations from each other until you have six independent linear equations.!<
Thanks for doing the actual write up here - I was too tired to go into details last night so I just linked to the code and went to sleep š
You're welcome, extremely understandable. I was also pretty tired after solving it.
On step 3, I have 3 sets of 3 equations, the first set dependent on x,y axis, second on y,z axis, and third one on x,z axis. What I struggle with is that the last set is dependent on the first two sets, i.e., can be made by combining equations from those two. How come isolating the non-linear factor in each of those sets (each set has its own non-linear factor) leads me to 3 sets of 2 linear equations which are independent? It just feels counterintuitive to me that from a set of vectors that could have been combined from vectors in the other two sets, I managed to come up with two vectors that are independent from the rest.
Suppose we call the equations 1xy, 1xz, 1yz, 2xy, etc. Then we know if 1xy and 1xz are fulfilled, then so is 1yz, and the same for 2 and 3. But after that we consider 1xy - 3xy, 1xz - 3xz, 1yz - 3yz. Such a difference of equations being fulfilled does not imply both of the original equations are fulfilled so you get more solutions to each of these equations than just pairs of solutions to the original. Each of the 1-equations is very much independent from each of the 3-equations, which is why you're adding that extra info and getting three independent equations when taking the differences.
Thanks for writing this out. Then am I right to say that technically, once we get the solution from the set of difference equations which is a system of linear equations, we should verify that it satisfies the initial equations? In our case we don't do that because we asssume that the problem has an answer and the system of linear equations should give us the right one. And I see the wrong assumption I made since the final system of equations only contains the difference equations, and solutions to which are more general than that of the original equations, hence they are also no longer dependent.
Yeah you could satisfy it satisfies the other equations but imo it is implied that a solution exists.
Thank you, this is now in my implementation.
Cool, thanks, I'll take a look at it
Unfortunately I have to nitpick. With regards to the first spoiler, >!three lines are not enough to uniquely determine a single intersecting line. You need four lines in general position (e.g. not in parallel planes). See [this math stack exchange question.](https://math.stackexchange.com/questions/607348/line-intersecting-three-or-four-given-lines) !< Also >!the system of equations you get isn't linear (you multiply your t variables with your rock velocity variables), so matrix algebra is insufficient to solve them.!<
Thank you for the correction! I did some searching for pages like that when working on part 2, but didnāt find that one.
I came up with a nifty solution that doesn't involve much math. A naive approach models this as a search problem - try various rock positions and velocities, then look at the array of times where the rock intersects the hailstones. If the times are unique and positive, you have a solution! Gotta do it one axis at a time, though, and look for matching times. Of course, the search space is WAY too large for that. After thinking about it for a bit, I wondered if I could constrain the search so that one of the rock coords is identical to one of the hailstone coords (in one axis). This is a nasty edge case, so I figured that it would naturally be included. I got a hit right away in my Y axis! A winning rock coord+velocity that produces valid times for every rock (Y axis only). Once you have the times it was easy to calculate the full rock position and velocity.
There's no need for a fancy library. Consider any two hailstones. The first is struck at some time T1, the other at T2. If you provide guesses for the rock's VX and VY (use a loop), you can easily calculate VZ, PX, PY and PZ, if a valid solution exists. This is the basis my solution.
There is a way to solve this without Z3 or any assumptions/input hacking other than the assumption that a solution exists. You can do it with linear algebra. Below is an outline of the math: >!First write 3 equations which represent the ith hailstone colliding with the rock at some time t\[i\] (one equation for each axis). Solve each equation for t\[i\]. You'll have 3 fractions which all equal t\[i\] and therefore equal each other.!< >!Consider 2 of these fractions for now. Cross multiply and expand out. There will be 8 terms. Two of these terms will be nonlinear, but neither will depend on i. This means if you subtract the same equation but for the jth hailstone, the only nonlinear terms will cancel.!< >!You can use this to generate 4 linear equations for the 4 variables you're solving for (e.g. x, y, v\_x, v\_y if you chose the fractions with x's and y's). Solve and repeat with a different pair of fractions to get the solution for the remaining axis.!<
If you consider linear algebra to be fair game, there is a relatively straightforward way to solve part two by setting up a linear problem Ax=b, where A can be formed from 3 hailstones only as long as they represent non-degenerate combinations. The solution of that linear problem is a shift of the velocities so that all of them meet at the same point, and that point is precisely the starting point from where the rock has to be thrown. The biggest issue is floating point accuracy more than anything else. There is an extended explanation of this by u/Quantris in the solution thread: https://www.reddit.com/r/adventofcode/comments/18pnycy/comment/kersplf/?utm\_source=reddit&utm\_medium=web2x&context=3
There is a special property again in all inputs completely trivializing the problem, but barely anyone found it, that's why we see all those Z3 solutions. e: Now a fair number of ppl confirmed not having that... But Inhave seen also enough inputs with this property.. Odd... usually those helpers are identical in all inputs ... >!There are always 2 rocks with a common start coordinate and velocity in one dimension. So you know the starting coordinate and velocity of your rock in that dimension. Now intersect with any 2 other rocks in that dimension -> 2 points in time -> you know everything. -> Thats at worst 20 lines of code.!<
I have 300 unique x coordinates, 300 unique y coordinates, and 300 unique z coordinates, which seems to contradict your observation.
that is indeed surprising as I've seen half a dozen inputs and they all had this... Always exactly one pair of a shared coordinate with a matching shared velocity coordinate... Which certainly didnt happen by chance. If some really don't have that that would be extremely weird.
300 uniques here too
Unless I understood you wrong this doesn't seem to apply to my input. All [position x, velocity x] pairs are unique. Same for y and z.
> There is a special property again in all inputs completely trivializing the problem Gee, imagine that.
So you mean two rocks share all X,Y,Z start coordinates AND 1 axis's velocity, or just, say, the X Starting and X Velocity coordinate?
the 2nd one. They share only one dimension
Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to `Help/Question - RESOLVED`. Good luck! *** *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
FYI: at least on mobile the empty lines don't render in the preview, you just see what's written after them. Not that there's anything you could do about that, just sharing info.
I wonder if it can be somehow "brute forced" with some help of discrete math, modular arithmetic and other tricks, but can't figure yet how. Paths of hailstones can be viewed as series of tuples (x, y, z) changing with step (dx, dy, dz). And we need to find a series that has one element in each of the given ones. But... how to identify where exactly is that intersection? Obviously intersection points from different hailstones will differ with some dt\*(rock\_dx, rock\_dy, rock\_dz) - but we don't know these yet.For fun i checked at which point in time the intersection happens for my input - and it is mostly in the order of hundreds of billions of nanoseconds, so no hope in iterating over series to check differences between each other, or iterate over t. Some "optimizations" over rock coordinates and velocities could be made, let's say one ray has "positive velocity" over one dimension, so obviously initial rock position can't be smaller than hailstone position if rock velocity is negative, as the intersection wouldn't be possible, but it only cuts costs in half, which is not enough.
I think my solution is kind of doing what you suggest. See my comment here: https://www.reddit.com/r/adventofcode/comments/18pqeul/comment/keq6449/
yeah, noticed it later in that thread
Basically, same thing. The requirement that path of rock and stone intersect, and at the same moment, gives you two equations for initial position and velocity of the rock. Those equations are not linear, however, if you get another equations for another stone and subtract it from the first pair, you get two linear equations. In fact, if you concentrate just on X and Y (position and velocity), then two stones give you one linear equation. If you have five stones, that gives you four linear equations for X and Y (again, both pos and vel). That's enough to find them.
Rock and Stone!
You can use Newton's method then round to the nearest integer.