advent-of-code-2025/day8/main.go

package main

import (
	"bufio"
	"flag"
	"fmt"
	"io"
	"log"
	"maps"
	"math"
	"os"
	"slices"
	"strconv"
	"strings"
	"time"
)

func main() {
	connections := flag.Int("connect", -1, "Number of connections to perform (-1 unlimited).")
	debug := flag.Bool("debug", false, "Debug.")
	flag.Parse()

	f := os.Stdin
	if flag.NArg() > 0 && flag.Arg(0) != "-" {
		var err error
		f, err = os.Open(flag.Arg(0))
		if err != nil {
			log.Fatal(err)
		}
		defer f.Close()
	}

	positions, err := readPositions(f)
	if err != nil {
		log.Fatal(err)
	}
	circuit := make([]int, len(positions))
	for i := range positions {
		circuit[i] = i
	}

	start := time.Now()
	distances := computeDistances(positions)
	var last connection
	fmt.Println("distances computed in", time.Since(start))

	start = time.Now()
	for i := 0; ; i++ {
		if *connections >= 0 && i >= *connections {
			break
		}
		c, ok := distances.FindMin()
		if !ok {
			break
		}
		bCircuit := circuit[c.B]
		for i := range circuit {
			if circuit[i] == bCircuit {
				circuit[i] = circuit[c.A]
			}
		}
		if *debug {
			fmt.Println("connect", positions[c.A], "and", positions[c.B])
		}
		if allEqual(circuit) {
			last = c
			break
		}
		delete(distances, c)
	}
	fmt.Println("connections computed in", time.Since(start))

	countsMap := make(map[int]int)
	for _, c := range circuit {
		countsMap[c]++
	}
	counts := slices.Sorted(maps.Values(countsMap))
	// if *debug {
	// 	fmt.Println("counts:", counts)
	// }

	ans := 1
	for _, c := range counts[max(0, len(counts)-3):] {
		ans *= c
	}
	fmt.Println("three largest mult:", ans)
	fmt.Println("last connection X mult:", positions[last.A].X*positions[last.B].X)
}

type position struct {
	X, Y, Z int
}

func (p position) String() string {
	return fmt.Sprintf("%d,%d,%d", p.X, p.Y, p.Z)
}

func (p position) DistanceTo(p1 position) float64 {
	compX := float64((p.X - p1.X) * (p.X - p1.X))
	compY := float64((p.Y - p1.Y) * (p.Y - p1.Y))
	compZ := float64((p.Z - p1.Z) * (p.Z - p1.Z))
	return math.Sqrt(compX + compY + compZ)
}

func readPositions(r io.Reader) ([]position, error) {
	var positions []position
	sc := bufio.NewScanner(r)
	for sc.Scan() {
		fields := strings.Split(sc.Text(), ",")
		if len(fields) != 3 {
			return nil, fmt.Errorf("position %q: unexpected number of fields", sc.Text())
		}
		x, err := strconv.Atoi(fields[0])
		if err != nil {
			return nil, fmt.Errorf("position %q: x: %w", sc.Text(), err)
		}
		y, err := strconv.Atoi(fields[1])
		if err != nil {
			return nil, fmt.Errorf("position %q: y: %w", sc.Text(), err)
		}
		z, err := strconv.Atoi(fields[2])
		if err != nil {
			return nil, fmt.Errorf("position %q: z: %w", sc.Text(), err)
		}
		positions = append(positions, position{
			X: x,
			Y: y,
			Z: z,
		})
	}
	return positions, sc.Err()
}

type connection struct {
	A, B int
}

func (c connection) Reverse() connection {
	return connection{c.B, c.A}
}

type distances map[connection]float64

func (d distances) Get(aIndex, bIndex int) float64 {
	c := connection{aIndex, bIndex}
	if dist, ok := d[c]; ok {
		return dist
	}
	return d[c.Reverse()]
}

func (d distances) Set(aIndex, bIndex int, dist float64) {
	d[connection{aIndex, bIndex}] = dist
}

func (d distances) FindMin() (c connection, ok bool) {
	for pair, dist := range d {
		if !ok || dist < d[c] {
			c = pair
			ok = true
		}
	}
	return c, ok
}

func computeDistances(positions []position) distances {
	table := make(distances)
	for i, p := range positions {
		for j := i + 1; j < len(positions); j++ {
			dist := p.DistanceTo(positions[j])
			table.Set(i, j, dist)
		}
	}
	return table
}

func allEqual(s []int) bool {
	if len(s) < 1 {
		return true
	}
	for _, v := range s[1:] {
		if v != s[0] {
			return false
		}
	}
	return true
}