Marketing Pitch and Impressions#

Build simple, secure, scalable systems with Go

  • An open-source programming language supported by Google
  • Easy to learn and great for teams
  • Built-in concurrency and a robust standard library
  • Large ecosystem of partners, communities, and tools

— go.dev

In my view, Go (aka Golang if you want to google something), is a great language for folks that value getting stuff done. The language designers have made a language that has deliberately kept the core set of functionality and keywords small and opinionated. For example, there are no public or private or even protected keywords in Go. Public declarations start with a capital letter (eg PublicFunction()), and non-public declarations do not (eg nonPublicFunction()).

Some of this convention and uniformity can be a bit grating initially for folks like me that prefer to exercise some control over code layout. For example in Visual Studio Code, upon saving a source file it is automatically reformatted. Using tabs, no less. I presume this can be turned off or customised, but it all seems to be part of a larger, apparently successful plan to make folks more productive in the language.

Visual Studio Code support for Go is excellent. Tooling is excellent. Everything is fast and smooth.

The Code#

I really like Go. The syntax is easy to read, the tooling is excellent, and the available ecosystem is huge. One possible drawback is that simplicity seems to come at a cost of expressiveness and conciseness. This is the largest number of lines of code in all the solutions— for comparison, an equivalent Kotlin implementation for this is around 50 lines, almost half of the code.

For this puzzle, the two major elements we use are a list of possible connections sorted by length, and a union-find disjoint set of junction boxes.

For part 1, we join up the 1,000 closest junctions and then query the disjoint set for the largest members and multiply them.

For part 2, we use Kruskal’s algorithm: keep connecting junctions in distance order, until the disjoint set has size 1. We then compute the product of the two x coordinates of the last connected edge.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

package main

import (
	"bufio"
	"fmt"
	"os"
	"slices"
	"strconv"
	"strings"
)

type p3d struct{ x, y, z int64 }
type edge struct{ u, v int }

func (p p3d) distSq(q p3d) int64 {
	dx, dy, dz := p.x-q.x, p.y-q.y, p.z-q.z
	return dx*dx + dy*dy + dz*dz
}

type unionFind struct {
	parents, sizes []int
	count          int
}

func newUnionFind(n int) *unionFind {
	parents, sizes := make([]int, n), make([]int, n)
	for i := range parents {
		parents[i] = i
		sizes[i] = 1
	}
	return &unionFind{parents, sizes, n}
}

func (u *unionFind) find(i int) int {
	if u.parents[i] != i {
		u.parents[i] = u.find(u.parents[i])
	}
	return u.parents[i]
}

func (u *unionFind) union(i, j int) bool {
	rooti, rootj := u.find(i), u.find(j)
	if rooti == rootj {
		return false
	}
	if u.sizes[rooti] < u.sizes[rootj] {
		rooti, rootj = rootj, rooti
	}
	u.parents[rootj], u.sizes[rooti] = rooti, u.sizes[rooti]+u.sizes[rootj]
	u.count -= 1
	return true
}

func main() {
	f, _ := os.Open("y25d08.txt")
	defer f.Close()

	var pts []p3d
	for s := bufio.NewScanner(f); s.Scan(); {
		p := strings.Split(s.Text(), ",")
		x, _ := strconv.ParseInt(p[0], 10, 64)
		y, _ := strconv.ParseInt(p[1], 10, 64)
		z, _ := strconv.ParseInt(p[2], 10, 64)
		pts = append(pts, p3d{x, y, z})
	}

	var edges []edge
	for i := range pts {
		for j := i + 1; j < len(pts); j++ {
			edges = append(edges, edge{i, j})
		}
	}
	slices.SortFunc(edges, func(a, b edge) int {
		return int(pts[a.u].distSq(pts[a.v]) - pts[b.u].distSq(pts[b.v]))
	})

	uf1 := newUnionFind(len(pts))
	for _, e := range edges[:min(1000, len(edges))] {
		uf1.union(e.u, e.v)
	}
	sizes := make(map[int]int)
	for i := range pts {
		sizes[uf1.find(i)] += 1
	}
	var groups []int
	for _, v := range sizes {
		groups = append(groups, v)
	}
	slices.SortFunc(groups, func(a, b int) int { return b - a })
	fmt.Println("Result1:", groups[0]*groups[1]*groups[2])

	uf2 := newUnionFind(len(pts))
	for _, e := range edges {
		if uf2.union(e.u, e.v) && uf2.count == 1 {
			fmt.Println("Result2:", pts[e.u].x*pts[e.v].x)
			break
		}
	}
}

Install Go and run#

You can download installers and whatnot from the go.dev website, but installing via your package manager is probably going to be easier over time.

# I installed via Homebrew
brew install golang

# Download from the website if you must
# https://go.dev/dl/

# Execute the code
go run d08.go