AoC2023 Day24 Part2

public dynamic SolvePart2()
{
    var range = 300;

    // Brute force rock velocities in the XY plane
    foreach (var x in Range(range))
    {
        foreach (var y in Range(range))
        {
            // Grab the intersection of the first four hailstone trajectories with their velocities modified by (x,y).
            // A rock with velocity (3,1) hitting a hailstone with velocity (1,1) is the same as
            // a rock with velocity (0,0) and a hailstone with velocity (-2,0).
            var intersect1 = TryIntersectPos(Hails[1], Hails[0], (x, y));
            var intersect2 = TryIntersectPos(Hails[2], Hails[0], (x, y));
            var intersect3 = TryIntersectPos(Hails[3], Hails[0], (x, y));

            // If they don't align, keep searching
            if (!intersect1.intersects || intersect1.pos != intersect2.pos || intersect1.pos != intersect3.pos) continue;

            // Brute force the Z velocity as well.
            foreach (var z in Range(range))
            {
                // We know at what timestamp we would intersect the rock its initial position, so we can just check where the Z would end up at
                // Check them for the first four hailstones as well
                var intersectZ = Hails[1].Pos.Z + intersect1.time * (Hails[1].Vel.Z + z);
                var intersectZ2 = Hails[2].Pos.Z + intersect2.time * (Hails[2].Vel.Z + z);
                var intersectZ3 = Hails[3].Pos.Z + intersect3.time * (Hails[3].Vel.Z + z);

                // If they don't align, keep searching
                if (intersectZ != intersectZ2 || intersectZ != intersectZ3) continue;

                // If four hailstones happen to align, just assume we found the answer and exit.
                return intersect1.pos.X + intersect1.pos.Y + intersectZ;
            }


        }
    }

    return -1;
}

// 0, -1, 1, -2, 2, -3, 3...
public IEnumerable<int> Range(int max)
{
    var i = 0;
    yield return i;

    while (i < max)
    {
        if (i >= 0)
            i++;
        i *= -1;
        yield return i;
    }
}

// Maths:
// https://math.stackexchange.com/a/3176648
public (bool intersects, (BigInteger X, BigInteger Y) pos, BigInteger time) TryIntersectPos(Hail one, Hail two, (int x, int y) offset)
{
    var a = (Pos: (one.Pos.X, one.Pos.Y), Vel: (X: one.Vel.X + offset.x, Y: one.Vel.Y + offset.y));
    var c = (Pos: (two.Pos.X, two.Pos.Y), Vel: (X: two.Vel.X + offset.x, Y: two.Vel.Y + offset.y));

    //Determinant
    BigInteger D = (a.Vel.X * -1 * c.Vel.Y) - (a.Vel.Y * -1 * c.Vel.X);

    if (D == 0) return (false, (-1, -1), -1);

    var Qx = (-1 * c.Vel.Y * (c.Pos.X - a.Pos.X)) - (-1 * c.Vel.X * (c.Pos.Y - a.Pos.Y));
    var Qy = (a.Vel.X * (c.Pos.Y - a.Pos.Y)) - (a.Vel.Y * (c.Pos.X - a.Pos.X));

    var t = Qx / D;
    var s = Qy / D;

    var Px = (a.Pos.X + t * a.Vel.X);
    var Py = (a.Pos.Y + t * a.Vel.Y);

    // Returns the intersection point, as well as the timestamp at which "one" will reach it with the given velocity.
    return (true, (Px, Py), t);
}

public class Hail
{
    public (BigInteger X, BigInteger Y, BigInteger Z) Pos;
    public (int X, int Y, int Z) Vel;

    public Hail((BigInteger X, BigInteger Y, BigInteger Z) pos, (int X, int Y, int Z) vel)
    {
        Pos = pos;
        Vel = vel;
    }
}