aoc2025/day8/day8b.zig

const std = @import("std");

var allocatorBuffer: [100*1024*1024]u8 = undefined;
var fb_alloc = std.heap.FixedBufferAllocator.init(&allocatorBuffer);
var allocator = fb_alloc.allocator();

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 Circuit = struct {
    junctions: std.AutoHashMap(usize,bool),
    wires: std.AutoHashMap(usize,bool),

    pub fn clear(self: *Circuit) void {
        self.junctions.clearRetainingCapacity();
        self.wires.clearRetainingCapacity();
    }

    pub fn addOtherCircuit(self: *Circuit, other: Circuit) !void {
        var junctionsIterator = other.junctions.keyIterator();
        while(junctionsIterator.next()) |junction| {
            try self.junctions.put(junction.*, true);
        }

        var wiresIterator = other.wires.keyIterator();
        while(wiresIterator.next()) |wire| {
            try self.wires.put(wire.*, true);
        }
    }
};

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

fn circuitPairCompareGT(_: void, left: Circuit, right: Circuit) bool {
    return left.junctions.count() > right.junctions.count();
}

const Error = error {
    JunctionIdNotFound,
};

fn findCircuitForJunction(circuits: std.ArrayList(Circuit), junctionId: usize) !usize {
    for (0 .. circuits.items.len) |circuitId| {
        if (circuits.items[circuitId].junctions.contains(junctionId)) {
            return circuitId;
        }
    }

    return Error.JunctionIdNotFound;
}

pub fn main() !void {
    var printBuf: [1024]u8 = undefined;

    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 circuits = std.ArrayList(Circuit).empty;
    for (0..junctions.items.len) |a| {
        var newCircuit = try circuits.addOne(allocator);
        newCircuit.junctions = std.AutoHashMap(usize,bool).init(allocator);
        newCircuit.wires = std.AutoHashMap(usize,bool).init(allocator);
        try newCircuit.junctions.put(a, true);
    }

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

        const circuitA = try findCircuitForJunction(circuits, a);
        const circuitB = try findCircuitForJunction(circuits, b);

        if (circuitA == circuitB) {
            continue;
        }

        try circuits.items[circuitA].addOtherCircuit(circuits.items[circuitB]);
        try circuits.items[circuitA].wires.put(wire, true);
        circuits.items[circuitB].clear();

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