adventofcode/2025/day8/day8.go

package main

import (
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

type Edge struct {
	dist int64
	i, j int
}

type DSU struct {
	parent []int
}

func NewDSU(n int) *DSU {
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	return &DSU{parent: p}
}

func (d *DSU) Find(x int) int {
	if d.parent[x] != x {
		d.parent[x] = d.Find(d.parent[x])
	}
	return d.parent[x]
}

func (d *DSU) Union(a, b int) {
	ra := d.Find(a)
	rb := d.Find(b)
	if ra != rb {
		d.parent[ra] = rb
	}
}

type Point struct {
	x, y, z int
}

func main() {
	data, _ := os.ReadFile("input.txt")
	lines := strings.Split(strings.TrimSpace(string(data)), "\n")

	points := []Point{}
	for _, line := range lines {
		fields := strings.Split(line, ",")
		if len(fields) != 3 {
			continue
		}
		x, _ := strconv.Atoi(strings.TrimSpace(fields[0]))
		y, _ := strconv.Atoi(strings.TrimSpace(fields[1]))
		z, _ := strconv.Atoi(strings.TrimSpace(fields[2]))
		points = append(points, Point{x, y, z})
	}

	n := len(points)

	edges := make([]Edge, 0, n*(n-1)/2)
	for i := range n {
		p1 := points[i]
		for j := range i {
			p2 := points[j]
			dx := int64(p1.x - p2.x)
			dy := int64(p1.y - p2.y)
			dz := int64(p1.z - p2.z)
			dist := dx*dx + dy*dy + dz*dz
			edges = append(edges, Edge{dist, i, j})
		}
	}

	sort.Slice(edges, func(a, b int) bool {
		return edges[a].dist < edges[b].dist
	})

	dsu := NewDSU(n)

	connections := 0

	for t, e := range edges {
		if t == 1000 {
			sz := make(map[int]int)
			for x := range n {
				root := dsu.Find(x)
				sz[root]++
			}

			list := make([]int, 0, len(sz))
			for _, v := range sz {
				list = append(list, v)
			}
			sort.Ints(list)

			if len(list) >= 3 {
				fmt.Println(list[len(list)-1] * list[len(list)-2] * list[len(list)-3])
			} else {
				fmt.Println(0)
			}
		}

		ri := dsu.Find(e.i)
		rj := dsu.Find(e.j)
		if ri != rj {
			connections++
			if connections == n-1 {
				fmt.Println(points[e.i].x * points[e.j].x)
			}
			dsu.Union(ri, rj)
		}
	}
}