aoc2025/day8/day8b.zig

const std = @import("std");

var printBuffer: [1024]u8 = undefined;
var allocatorBuffer: [100*1024*1024]u8 = undefined;

const Junction = struct {
    x: i64 = 0,
    y: i64 = 0,
    z: i64 = 0,
};

const JunctionPair = struct {
    a: usize = 0,
    b: usize = 0,

    pub fn distanceSquared(self: JunctionPair, junctions: []Junction) i64 {
        const ja = &junctions[self.a];
        const jb = &junctions[self.b];
        const dx = ja.x - jb.x;
        const dy = ja.y - jb.y;
        const dz = ja.z - jb.z;
        return  dx * dx + dy * dy + dz * dz;
    }
};

const JunctionIdNode = struct {
    id: usize = 0,
    node: std.DoublyLinkedList.Node = .{},
};

const Circuit = struct {
    junctions: std.DoublyLinkedList = .{},
    node: std.DoublyLinkedList.Node = .{},
};

fn junctionPairCompareLT(junctions: []Junction, left: JunctionPair, right: JunctionPair) bool {
    return left.distanceSquared(junctions) < right.distanceSquared(junctions);
}

const Error = error {
    JunctionIdNotFound,
};

fn findCircuitForJunction(circuits: std.DoublyLinkedList, junctionId: usize) !*std.DoublyLinkedList.Node {
    var circuitIter = circuits.first;
    while (circuitIter) |circuitNode| : (circuitIter = circuitNode.next) {
        const circuit: *Circuit = @fieldParentPtr("node", circuitNode);

        var found = false;
        var junctionIdIter = circuit.junctions.first;
        while (junctionIdIter) |node| : (junctionIdIter = node.next) {
            const junctionIdNode: *JunctionIdNode = @fieldParentPtr("node", node);
            if (junctionIdNode.id == junctionId) {
                found = true;
                break;
            }
        }

        if (found) {
            return circuitNode;
        }
    }

    return Error.JunctionIdNotFound;
}

pub fn main() !void {
    var fb_alloc = std.heap.FixedBufferAllocator.init(&allocatorBuffer);
    var allocator = fb_alloc.allocator();

    const inputFile = try std.fs.cwd().openFile(
        "input.txt",
        .{
            .mode = .read_only,
        },
    );
    defer inputFile.close();

    var inputFileBuffer: [1024]u8 = undefined;
    var inputFileReader = inputFile.reader(&inputFileBuffer);
    const inputFileSize = try inputFileReader.getSize();

    const inputBuffer = try allocator.alloc(u8, inputFileSize);
    try inputFileReader.interface.readSliceAll(inputBuffer);

    var junctions = std.ArrayList(Junction).empty;

    var i = std.mem.tokenizeScalar(u8, inputBuffer, '\n');
    while (i.next()) |newJunctionText| {
        var j = std.mem.tokenizeAny(u8, newJunctionText, ",\n");

        var newJunction = try junctions.addOne(allocator);
        newJunction.x = try std.fmt.parseInt(i64, j.next().?, 10);
        newJunction.y = try std.fmt.parseInt(i64, j.next().?, 10);
        newJunction.z = try std.fmt.parseInt(i64, j.next().?, 10);
    }

    var junctionPairs = std.ArrayList(JunctionPair).empty;
    for (0..junctions.items.len) |a| {
        for (a+1..junctions.items.len) |b| {
            var newJunctionPair = try junctionPairs.addOne(allocator);
            newJunctionPair.a = a;
            newJunctionPair.b = b;
        }
    }
    std.sort.block(JunctionPair, junctionPairs.items, junctions.items, junctionPairCompareLT);

    var junctionIdNodeStorage = try std.ArrayList(JunctionIdNode).initCapacity(allocator, junctions.items.len);
    var circuitsStorage = try std.ArrayList(Circuit).initCapacity(allocator, junctions.items.len);
    var circuits: std.DoublyLinkedList = .{};
    for (0..junctions.items.len) |a| {
        var newJunctionIdNode = try junctionIdNodeStorage.addOne(allocator);
        newJunctionIdNode.id = a;

        var newCircuit = try circuitsStorage.addOne(allocator);
        newCircuit.junctions = .{};
        newCircuit.junctions.append(&newJunctionIdNode.node);
        circuits.append(&newCircuit.node);
    }

    var circuitsCount:usize = junctions.items.len;
    for (0..junctionPairs.items.len) |wire| {
        const a = junctionPairs.items[wire].a;
        const b = junctionPairs.items[wire].b;

        const circuitANode = try findCircuitForJunction(circuits, a);
        const circuitBNode = try findCircuitForJunction(circuits, b);
        if (circuitANode == circuitBNode) {
            continue;
        }

        const circuitA: *Circuit = @fieldParentPtr("node", circuitANode);
        const circuitB: *Circuit = @fieldParentPtr("node", circuitBNode);

        circuitA.junctions.concatByMoving(&circuitB.junctions);
        circuits.remove(circuitBNode);

        circuitsCount -= 1;
        if (circuitsCount == 1) {
            try std.fs.File.stdout().writeAll(
              try std.fmt.bufPrint(&printBuffer, "{}\n", .{junctions.items[a].x*junctions.items[b].x}));
            break;
        }
    }
}