https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 24> :thread:
# advent-of-code
a
j
I struggle with lines, have not used them for a while
m
theres gotta be an edge case for part1 I'm missing
j
Oh man, do we really have to solve 3d vector equasions for part 2
@Michael de Kaste have a look at the line equation
m
yeah im doing exactly that, I got 2 slopes and calculating their intersection point
j
and also only point is the future of the hailstone are reachable
so you have to check if x speed is negative if the point is smaller than the initial x and same for y
if your example gives you 5, that's the thing that's wrong
m
Copy code
fun intersects(input1: Input, input2: Input): Boolean {
    val x: Double = (input2.equation.b - input1.equation.b) / (input1.equation.slope - input2.equation.slope)
    val y: Double = (input1.equation.slope * x + input1.equation.b)
    val rangex1 = if(input1.xDiff >= 0L) input1.x.toDouble()..UPPERBOUND else LOWERBOUND..input1.x.toDouble()
    val rangey1 = if(input1.yDiff >= 0L) input1.y.toDouble()..UPPERBOUND else LOWERBOUND..input1.y.toDouble()
    val rangex2 = if(input2.xDiff >= 0L) input2.x.toDouble()..UPPERBOUND else LOWERBOUND..input2.x.toDouble()
    val rangey2 = if(input2.yDiff >= 0L) input2.y.toDouble()..UPPERBOUND else LOWERBOUND..input2.y.toDouble()
    val toReturn = x in rangex1 && x in rangex2 && y in rangey1 && y in rangey2
    return toReturn
}
where equation
Copy code
val equation = run {
    val x2 = x + xDiff
    val y2 = y + yDiff
    val slope = (y2 - y) / (x2 - x).toDouble()
    val b = y - slope * x
    Equation(slope, b)
}
it works for the example
classic
😄
b
wow p1 was another reading comprehension problem for me, i couldn't figure out how to count "how many of the hailstone's paths will intersect"
j
@Michael de Kaste did you forget to adjust the bounds, they are different for example and real input
m
Copy code
const val LOWERBOUND = 200000000000000.0
const val UPPERBOUND = 400000000000000.0
b
also, one thing that got me was that some intersections were future for one stone but past for the other, so check both...
j
For part2 I have no idea atm how to solve it, will have to take a step back
m
Solved part 2 finally
Part 2 😅
🙌 1
m
this is not what I expected to do this sunday
m
apt install z3
, done, easy. 😄
m
yeah, linux is on my work laptop, might jjust grab that one lol
d
I’m stuck in the “_works perfectly for the example_” phase 😒 … leaving it for now
p
I used KSMT although I wish I didn't need to. I'm sure there's a smarter way than using a numeric solver...
d
Bloody hell… I had a 
Double
vs 
BigDecimal
issue for part 1 (where I needed to use the latter) 🤦‍♂️
Can we simplify the problem for part 2 if we flatten it to the three x/y, x/z, y/z planes?
I.e. try to find lines on all three, then combine?
(just thinking out loud)
Never mind 😅 … I’ll stop thinking out loud because more incoherent thoughts pop up when thinking about this 🤯
j
@phldavies thanks for the tip with the linear equations solver
👍 1
e
You don’t need a solver. There is a peculiar fact about the inputs and the answer. Once you know this fact, it takes very little code to find the answer.
p
I didn't think a solver was needed, but it did provide a solution that my far-too-early-was-woken-by-child brain couldn't find.
t
@elizarov Is it only the main input or also the test input that shows this peculiarity? 🤔
w
Are all collision times by definition integer? If yes then it’s a matter of finding some common divisor? t = (position2 - position1) / (velocity1 - velocity2) if this has to be integer than the task should be a lot easier
The example says it is
I think the algorithm could be as follows:
Copy code
- We can treat each component (x, y, z) separately
- We can brute force check all possible speeds (the max speed for any of the stones seem to be quite small)
- (position2 - position1) / (velocity1 - velocity2) has to be integer divisible for each stone, a fact we can use to thin out a possible range of positions by comparing with each stone
I have not been able to work out all the details, but quickly scanning the solution of @elizarov this seems to be the right direction.
e
It is even simpler. All the complexity of my original solution is not needed at all. I’ve golfed the correct part 2 solution into 17 lines of code. https://github.com/elizarov/AdventOfCode2023/blob/main/src/Day24_2_golf.kt
🤯 1
j
Hm seems to be correct
w
Genius
I found this solution as well: basically use the algo of part 1 but offset the velocities of all stones with some deltaV = vx, vy, vz. Now if you find a deltaV for which all intersections coincide, you found your point. You can brute force this over v-s within some small range.
👍 2
Using Einsteins theory of relativity 🙂 it doesn’t matter if the rock is standing still or if the stones are moving (as long as the relative speeds are the same)
e
In my golfed solution maybe you don’t even need the firstNotNullOf by k. Maybe x coordinate always works (in my input x and z work). Maybe you don’t need to find i and j at line 14. Maybe the first two lines (i=0, j=1) always work. If that is true, it can be made even shorter.
d
@elizarov can you point me to something where I can read about the theory behind your (golfed) solution?
t
Part 2 today was my worst task so far during AoC 😞 I did it eventually (without a numerical solver like z3), but only because I read on reddit how to solve it (and I still struggled a lot). Nightmare 😱
j
The numerical solver idea I had a few minutes after seeing the problem for part2, but I did not know one and kinda wanted to solve it myself. After a few hours I saw one of the solvers mentioned, so I solved with that, but have to say, I'm still not happy about it
d
Yeah, hence my question on Roman's golfed solution... It looks so simple. I've heard about "golf" before, but lost the context and don't know anything about the theory behind it.
m
Spent the day at the coffee table thinking about the problem and finally implemented a working solution https://github.com/fabmax/aoc-2023/blob/main/src/main/kotlin/day24/Day24.kt Definitely not as elegant as Romans solution but I'm happy with it. My idea was that obviously all hailstones have to intersect the line of the rock. So I'm picking two hailstones and approximate the times where both stones are on a line that intersects (or is very close to) all other hailstones. These two times are the collision times with the stone, so once I have them I can compute the velocity and start position of the rock. The approximation uses a decreasing step size and gets to the final solution in only a few iterations, total runtime < 10 ms.
👍 1
Also, I'm using several Double <-> Long casts, so it's definitely not pretty. But all values stay within the 53 bits of Double mantissa, so it should be fine
e
@daugian “code golf” means short code. No theory. The fact is that in two of the axes the rock’s starting position and velocity are equal to position and velocity of one of the hailstones. As simple as that. Once you’ve found it, you can compute intersection times (ts in my code) for all the other hailstones. Then getting to the answer is straightforward.
👍 1
b
but how do you arrive at that assumption without already having a solution?
d
Thanks @elizarov! I’ll ponder on it some more… but first… Day 25 🙌
e
@bj0 I don’t know. You guess it. I found it out because my original code assumed that a rock’s velocity is never equal to any of the hailstone’s velocities in the axis. It did not work for 2 out of 3 axes and I spent an hour debugging it only to realize this assumption was wrong.
w
I revisited and coded a complete working solution without assumptions: https://github.com/werner77/AdventOfCode/blob/master/src/main/kotlin/com/behindmedia/adventofcode/year2023/day24/Day24.kt Following key insights: • Instead of processing three dimensions you can process three times a projection to any of the other dimensions so you can reuse the 2D solution from part 1 • Moving rock with velocity v is the same as keeping the rock stationary and moving all stones by applying a velocity of -v as delta • Pair wise paths of the stones must then intersect at the position of the rock, because the rocks path should intersect the path of all stones, again we can reuse the algorithm from part 1.
🆒 1
b
@Max Thiele i tried something similar but it didnt work. so I tried to use your code to see if I just made a an error and your solution didn't work for my input.
m
Hmm interesting. Have you tried picking other hailstones as seeds for the approximation? I simply take the first and second one but it might be problematic if these are too close to each other.
b
i tried picking stones at random
if i pick one randomly and make sure the second one is linearly independent, and also make the step size drop much less severe, it sometimes works
m
I tried it with random picks as well and your are right I also get combinations that don't work. I thought it would be more robust.
b
i added code to check the distance to see if it was below a threshold after "converging" and if not abandon it and retry... since good points work in less than 70ms on my machine i can even limit each try to 100ms, that makes it find a solution almost every time
👍 1
e
I did part 2 with z3 originally. came back later after picking up an idea: • pick first hailstone. subtract its position and velocity from all others. in this reference frame, the colliding rock must pass through the origin • pick a second hailstone. assuming it is skew to the first, there is some unique plane containing both it and the origin, perpendicular to the cross-product of position and velocity vectors • pick a third skew hailstone, with corresponding plane. • assuming those two hailstones were not parallel, the line formed by the intersection of those planes intersection both lines and the origin. it is in the direction of the cross-product of the plane-perpendicular vectors. • given the times those intersections happened at (which we can compute along each axis, assuming non-zero velocity), we can work backwards to determine where the original rock was placed (and undo the offset from the first hailstone) • since the input requires arithmetic beyond the size of 
Long
, I'm using 
Double
which leads to rounding errors. so I'm actually performing the above calculation for all triples, then taking the most common result
I'm not doing that last step in any other language, btw: both Haskell and Python have arbitrary-precision integers and rational numbers in their standards libraries, and Rust has 
i128
built-in which is enough (picking up 
Ratio
from the 
num-rational
crate, but that's much easier to implement from scratch than bigints, having done both before)
I can't use 
java.lang.BigInteger
because I'm targeting JS and Native too
👍 1
b
After days of struggling (and a little help from a reddit post) was finally able to solve part 2 using linear algebra. And only needed 3 hailstones! https://github.com/bnorm/advent-of-code/blob/main/year2023/src/aoc/day24/main.kt#L33-L101
😮 2
26 Views
Open in Slack
PreviousNext
Powered by