# AoC 2025: Day 8

**URL:** <https://ziggit.dev/t/aoc-2025-day-8/13431>\
**Category:** Challenge\
**Tags:** advent-of-code\
**Created:** [December 8, 2025, 4:38pm UTC](https://ziggit.dev/t/aoc-2025-day-8/13431 "2025-12-08T16:38:05Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Calder-Ty](https://ziggit.dev/user_avatar/ziggit.dev/calder-ty/32/10237_2.png) [@Calder-Ty](https://ziggit.dev/u/Calder-Ty)\
**Post date:** [December 8, 2025, 4:38pm UTC](https://ziggit.dev/t/aoc-2025-day-8/13431/1 "2025-12-08T16:38:05Z")

</div>

Main thread for Day 8 of the 2025 advent of code. Feel free to discuss the challenge and ask questions. If particular discussions become large, we can break them off into new threads.

Notice that Advent of Code has changed it’s schedule and there will only be 12 days of puzzles this year.

Some Rules:

1. Please try to keep spoilers within spoiler tags. This is done by typing [spoiler]text to be blurred[\spoiler]. If you have longer sections you can also use the [details=“Title”] tags. If you use the new WYSIWYG editor, remember to _close_ the details section, as it is opened by default. This is an issue (feature?) of the newest discourse updates. If you use markdown, then you can remove the “open" parameter (not in by default unless you use the WYSIWYG editor)
2. Have Fun

[Day 8 Challenge](https://adventofcode.com/2025/day/8)

Templates:

- [GitHub - SpexGuy/Zig-AoC-Template: A template for Advent of Code participants using Zig](https://github.com/SpexGuy/Zig-AoC-Template)
- [GitHub - evaleek/advent-of-code-template: Advent of Code template for Zig solutions](https://github.com/evaleek/advent-of-code-template)

Resources:

- [Advent of Code in Zig | Loris Cro’s Blog](https://kristoff.it/blog/advent-of-code-zig): Advice and Tips on How to do AoC with Zig
- [https://zigbin.io](https://zigbin.io/): A website for sharing zig code
- [Documentation - The Zig Programming Language](https://ziglang.org/documentation/master/) : Zig Language Reference
- [Zig Documentation](https://ziglang.org/documentation/master/std/): Zig Standard Library Docs
- [Docs](https://ziggit.dev/docs) : Community Created Docs and Tutorials
- Private Leaderboard: 1910115-f465b6d3

---

<div class="post-metadata">

**Author:** ![dbushell](https://ziggit.dev/user_avatar/ziggit.dev/dbushell/32/4741_2.png) [@dbushell](https://ziggit.dev/u/dbushell)\
**Post date:** [December 8, 2025, 5:07pm UTC](https://ziggit.dev/t/aoc-2025-day-8/13431/2 "2025-12-08T17:07:48Z")

</div>

No worries about any delay 🙂 these challenges are getting harder, I might struggle to finish the same day.

Apparently [Disjoint-set data](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) is a thing I learning about now but I’m too dumb/tired to understand. Anyway, I just used hash maps and pointers! Performance seems ok.

> **[advent-of-code/2025/08/main.zig at main](https://git.dbushell.com/dbushell/advent-of-code/src/branch/main/2025/08/main.zig)**
>
> advent-of-code - 🎄 My solutions to Advent of Code

---

<div class="post-metadata">

**Author:** ![Lowell](https://ziggit.dev/user_avatar/ziggit.dev/lowell/32/7145_2.png) [@Lowell](https://ziggit.dev/u/Lowell)\
**Post date:** [December 8, 2025, 9:04pm UTC](https://ziggit.dev/t/aoc-2025-day-8/13431/3 "2025-12-08T21:04:44Z")

</div>

I mainly used index mappings (not exactly sure the correct term for that) - essentially a slice whose job it is to map one index into another index.

I used two of them for this problem: one to hold `i_pair -> .{ i_position_left, i_position_right}`, and another to hold `i_sorted_distance -> i_pair`.

I then used a variant of the Union Find algorithm to keep track of the circuits (disjoint sets): for each disjoint set, keep track of a single “root” node. When attempting to merge two nodes, I update all references of the higher root to instead point to the lower root.

The normal way to do this is via parent pointer trees, but I just directly kept track of the root for each index because it was easier to reason about.

---

<div class="post-metadata">

**Author:** ![Nico792](https://ziggit.dev/user_avatar/ziggit.dev/nico792/32/2439_2.png) [@Nico792](https://ziggit.dev/u/Nico792)\
**Post date:** [December 8, 2025, 9:39pm UTC](https://ziggit.dev/t/aoc-2025-day-8/13431/4 "2025-12-08T21:39:50Z")

</div>

Harder day today. [repo](https://codeberg.org/NicoElbers/aoc-2025/src/branch/main/day8)

Times:

```zig
❯ zig build day8 -Dlog_level=err --release=fast
Day 8, part 1:
  - Took 4.669ms on average over 1000 runs
Day 8, part 2:
  - Took 4.52ms on average over 1000 runs

```

Was surpised to find Zig’s std doesn’t have a partition method, but I can write my own.

This is a very fucky algorithm that mashes a bunch of concepts together, but  
at least it’s fast. I’ve let myself be told that Prims is a little faster still, but I’m proud of what I came up with on my own.

My part 1 has similar ideas, but with a modified UnionFind to keep track of the  
cluster sizes.

part2:

```zig
fn solution(r: *Reader, _: Io, gpa: Allocator) !u64 {
    // O(n)
    const boxes: []const Box = blk: {
        var boxes: ArrayList(Box) = .empty;
        errdefer boxes.deinit(gpa);

        while (try r.takeDelimiter('\n')) |line| {
            var it = mem.tokenizeScalar(u8, line, ',');

            const x: f32 = @floatFromInt(try fmt.parseInt(u32, it.next().?, 10));
            const y: f32 = @floatFromInt(try fmt.parseInt(u32, it.next().?, 10));
            const z: f32 = @floatFromInt(try fmt.parseInt(u32, it.next().?, 10));
            assert(it.next() == null);

            try boxes.append(gpa, .{ .x = x, .y = y, .z = z });
        }

        break :blk try boxes.toOwnedSlice(gpa);
    };
    defer gpa.free(boxes);
    std.log.info("Found {d} boxes", .{boxes.len});

    // (n * (n - 1)) / 2 == O(n^2)
    var connections: ArrayList(Connection) = try .initCapacity(gpa, (boxes.len * (boxes.len - 1)) / 2);
    defer connections.deinit(gpa);

    for (0..boxes.len - 1) |i| {
        for (i + 1..boxes.len) |j| {
            connections.appendAssumeCapacity(.init(
                boxes,
                .from(@intCast(i)),
                .from(@intCast(j)),
            ));
        }
    }
    std.log.info("Found {d} connections", .{connections.items.len});

    var uf: UnionFind = try .init(gpa, @intCast(boxes.len));
    defer uf.deinit(gpa);

    const connLessThanFn = struct {
        pub fn connLessThanFn(_: void, lhs: Connection, rhs: Connection) bool {
            return lhs.dist < rhs.dist;
        }
    }.connLessThanFn;

    var clusters = boxes.len;

    var stack: ArrayList([]Connection) = .empty;
    defer stack.deinit(gpa);

    // Partioning: avg O(nlogn) worst O(n^2)
    // Sorting partitions: O(nlogn)
    // Iterating conns: O(#connections) == O(n^2)
    // Uniting: O(alpha(n))
    //
    // Strictly speaking O(n^2 * alpha(n))
    try stack.append(gpa, connections.items);
    while (stack.pop()) |slice| {
        // cutoff is kinda arbitrary
        if (slice.len > boxes.len) {
            const pivot = partition(
                Connection,
                slice,
                slice.len / 2,
                {},
                connLessThanFn,
            );

            // Put the latter half first, so the former half is popped first
            try stack.append(gpa, slice[pivot..]);
            try stack.append(gpa, slice[0..pivot]);
            continue;
        }

        mem.sortUnstable(Connection, slice, {}, connLessThanFn);
        for (slice) |connection| {
            if (uf.unite(connection.id_a, connection.id_b)) {
                clusters -= 1;

                if (clusters == 1) {
                    const box_a = boxes[connection.id_a.to()];
                    const box_b = boxes[connection.id_b.to()];
                    const x_a: u64 = @intFromFloat(box_a.x);
                    const x_b: u64 = @intFromFloat(box_b.x);
                    return x_a * x_b;
                }
            }
        }
    }
    unreachable;
}

pub fn partition(
    comptime T: type,
    items: []T,
    partition_index: usize,
    context: anytype,
    comptime lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) usize {
    const swapIdx = struct {
        pub fn swapIdx(list: []T, a: usize, b: usize) void {
            if (a == b) return;
            mem.swap(T, &list[a], &list[b]);
        }
    }.swapIdx;

    assert(items.len >= 1);
    assert(partition_index < items.len);
    if (items.len == 1) return 0;

    // Get the partition point to a known and stable location
    swapIdx(items, partition_index, 0);
    const partition_point = items[0];

    var low_ptr: usize = 1;
    var high_ptr: usize = items.len - 1;

    while (low_ptr <= high_ptr) {
        while (low_ptr <= high_ptr and
            lessThanFn(context, items[low_ptr], partition_point)) : (low_ptr += 1)
        {}

        while (low_ptr <= high_ptr and
            lessThanFn(context, partition_point, items[high_ptr])) : (high_ptr -= 1)
        {}

        if (low_ptr <= high_ptr) {
            swapIdx(items, low_ptr, high_ptr);
            low_ptr += 1;
            high_ptr -= 1;
        }
    }

    // swap the partition point into place
    swapIdx(items, 0, low_ptr - 1);

    return low_ptr - 1;
}

const Id = enum(u32) {
    _,

    pub fn from(i: u32) Id {
        return @enumFromInt(i);
    }

    pub fn to(id: Id) u32 {
        return @intFromEnum(id);
    }
};

const UnionFind = struct {
    const Element = struct {
        parent: Id,
    };

    clusters: []Element,

    pub fn init(gpa: Allocator, size: u32) !UnionFind {
        const clusters = try gpa.alloc(Element, size);

        for (0..size) |i|
            clusters[i] = .{ .parent = .from(@intCast(i)) };

        return .{ .clusters = clusters };
    }

    pub fn deinit(uf: UnionFind, gpa: Allocator) void {
        gpa.free(uf.clusters);
    }

    pub fn find(uf: UnionFind, id: Id) Id {
        const i = id.to();
        const direct_parent = uf.clusters[i].parent;

        if (direct_parent == id) {
            return id;
        }

        const actual_parent = uf.find(direct_parent);

        uf.clusters[i].parent = actual_parent; // 'cache' lookup

        return actual_parent;
    }

    pub fn unite(uf: UnionFind, id_a: Id, id_b: Id) bool {
        const parent_a = uf.find(id_a);
        const parent_b = uf.find(id_b);

        if (parent_a == parent_b) return false;

        uf.clusters[parent_a.to()] = .{
            .parent = parent_a,
        };

        uf.clusters[parent_b.to()] = .{
            .parent = parent_a,
        };

        return true;
    }
};

const Box = struct {
    x: f32,
    y: f32,
    z: f32,

    pub fn dist(a: Box, b: Box) f32 {
        @setFloatMode(.optimized);
        const square = struct {
            pub fn square(e: f32) f32 {
                return e * e;
            }
        }.square;
        const res = @sqrt(square(a.x - b.x) + square(a.y - b.y) + square(a.z - b.z));
        assert(res == 0 or math.isNormal(res));
        assert(res >= 0);
        return res;
    }
};

const Connection = struct {
    id_a: Id,
    id_b: Id,
    dist: f32,

    pub fn init(boxes: []const Box, id_a: Id, id_b: Id) Connection {
        const dist = boxes[id_a.to()].dist(boxes[id_b.to()]);
        return .{ .id_a = id_a, .id_b = id_b, .dist = dist };
    }

    pub fn compare(a: Connection, b: Connection) math.Order {
        return math.order(a.dist, b.dist);
    }
};

```

---

<div class="post-metadata">

**Author:** ![npc1054657282](https://ziggit.dev/user_avatar/ziggit.dev/npc1054657282/32/5790_2.png) [@npc1054657282](https://ziggit.dev/u/npc1054657282)\
**Post date:** [December 9, 2025, 12:37am UTC](https://ziggit.dev/t/aoc-2025-day-8/13431/5 "2025-12-09T00:37:03Z")

</div>

It took me some time to find a solution that doesn’t use heap allocation. This is probably what is called the Prim algorithm.

```zig
pub fn part2(input: []const u8) !u64 {
    const point_num = 1000;
    const Point = struct {
        x: u32,
        y: u32,
        z: u32,
        fn distSq(self: @This(), another: @This()) !u64 {
            return @intCast(try std.math.powi(i64, @as(i64, self.x) - @as(i64, another.x), 2) +
                try std.math.powi(i64, @as(i64, self.y) - @as(i64, another.y), 2) +
                try std.math.powi(i64, @as(i64, self.z) - @as(i64, another.z), 2));
        }
    };
    var boxes: [point_num]Point = undefined;
    var line_it = std.mem.splitScalar(u8, input, '\n');
    for (0..point_num) |point_id| {
        const line = line_it.next().?;
        var it = std.mem.splitScalar(u8, line, ',');
        boxes[point_id] = .{
            .x = try std.fmt.parseUnsigned(u32, it.next().?, 10),
            .y = try std.fmt.parseUnsigned(u32, it.next().?, 10),
            .z = try std.fmt.parseUnsigned(u32, it.next().?, 10),
        };
    }
    var attachments: [point_num]struct {
        anchor: usize,
        dist_sq: u64,
        in_circuit: bool,
    } = undefined;
    attachments[0] = .{ .anchor = 0, .dist_sq = 0, .in_circuit = true };
    for (1..point_num) |id| {
        attachments[id] = .{ .anchor = 0, .dist_sq = try boxes[0].distSq(boxes[id]), .in_circuit = false };
    }
    while (true) {
        var closest_point_to_circuit: ?usize = null;
        for (0..point_num) |point| {
            if (attachments[point].in_circuit) continue;
            if (closest_point_to_circuit) |*closest| {
                if (attachments[closest.*].dist_sq > attachments[point].dist_sq) closest.* = point;
            } else closest_point_to_circuit = point;
        }
        if (closest_point_to_circuit) |closest| {
            attachments[closest].in_circuit = true;
            for (0..point_num) |point| {
                if (attachments[point].in_circuit) continue;
                const dist_sq = try boxes[point].distSq(boxes[closest]);
                if (dist_sq < attachments[point].dist_sq) {
                    attachments[point].anchor = closest;
                    attachments[point].dist_sq = dist_sq;
                }
            }
        } else break;
    }
    var largest_attachment_idx: usize = 0;
    for (1..point_num) |id| {
        if (attachments[id].dist_sq >= attachments[largest_attachment_idx].dist_sq) largest_attachment_idx = id;
    }
    return @as(u64, boxes[largest_attachment_idx].x) * @as(u64, boxes[attachments[largest_attachment_idx].anchor].x);
}

```
