AoC 2025 Day 8 Part 2

import core.time;
import std.stdio;
import std.typecons;

struct Box
{
    long x, y, z;

    long distance_to(const ref Box other) const
    {
        return
            (x - other.x)^^2 +
            (y - other.y)^^2 +
            (z - other.z)^^2;
    }

    /*
    string toString() const
    {
        return format("%d,%d,%d", x, y, z);
    }
    */
}

int main()
{
    MonoTime t1 = MonoTime.currTime;

    Box[] boxes;
    for (auto read_result = read_box();
         read_result.result;
         read_result = read_box())
    {
        boxes ~= read_result.box;

        //
        // writefln("%d, %d, %d, %d", read_result.box.circuit, read_result.box.x, read_result.box.y, read_result.box.z);
        //
    }

    MonoTime t2 = MonoTime.currTime;
    writefln("Reading:\t%u", (t2 - t1).total!"usecs");

    const int boxes_length = cast(int) boxes.length;

    t1 = MonoTime.currTime;

    long[] cheapestCost = new long[boxes_length];
    int[] cheapestEdge = new int[boxes_length];
    bool[] explored = new bool[boxes_length];

    for (int i = 0; i < boxes_length; ++i)
    {
        cheapestCost[i] = long.max;
    }

    cheapestCost[0] = 0;

    t2 = MonoTime.currTime;
    writefln("Assign:\t\t%u", (t2 - t1).total!"usecs");

    t1 = MonoTime.currTime;

    for (int step = 0; step < boxes_length; ++step)
    {
        int current_vertex;
        long min_cost = long.max;
        for (int i = 0; i < boxes_length; ++i)
        {
            long cheapestCost_i = cheapestCost[i];
            if (!explored[i] && (cheapestCost_i < min_cost))
            {
                min_cost = cheapestCost_i;
                current_vertex = i;
            }
        }

        explored[current_vertex] = true;
        const ref current_vertex_box = boxes[current_vertex];
        const int current_vertex_edge = current_vertex << 16;

        for (int neighbor = 0; neighbor < boxes_length; ++neighbor)
        {
            if (neighbor == current_vertex)
            {
                continue;
            }

            if (!explored[neighbor])
            {
                long distance = current_vertex_box.distance_to(boxes[neighbor]);
                if (distance < cheapestCost[neighbor])
                {
                    cheapestCost[neighbor] = distance;
                    cheapestEdge[neighbor] = current_vertex_edge | neighbor;
                }
            }
        }
    }

    t2 = MonoTime.currTime;
    writefln("Prim:\t\t%u", (t2 - t1).total!"usecs");

    t1 = MonoTime.currTime;

    long max_distance = 0;
    int longest_edge;
    for (int i = 0; i < boxes_length; ++i)
    {
        int cheapestEdge_i = cheapestEdge[i];
        if (cheapestEdge_i != 0)
        {
            long cheapestCost_i = cheapestCost[i];
            if (cheapestCost_i > max_distance)
            {
                max_distance = cheapestCost_i;
                longest_edge = cheapestEdge_i;
            }
        }
    }

    t2 = MonoTime.currTime;
    writefln("Result:\t\t%u", (t2 - t1).total!"usecs");

    long result = boxes[longest_edge >> 16].x * boxes[longest_edge & 0xffff].x;
    writeln(result);
    return 0;
}

Tuple!(bool, "result", Box, "box") read_box()
{
    Box box;
    return tuple!("result", "box")(3 == readf("%d,%d,%d\n", box.x, box.y, box.z), box);
}