Advent of Code 2021 Day 9: Smoke Basin
By Andreas Røssland
https://adventofcode.com/2021/day/9 https://github.com/roessland/advent-of-code
Today’s problem was to find the three biggest basins in a height map. Assuming that smoke flows downhill, and cannot rise to z=9 or above, smoke will fill the basins. Each tile with z<9 will then belong to exactly one basin.
These basins sure sound like connected components, so I dug up my old DisjointSet data structure (aka Union-Find), instead of doing a flood-fill or any kind of graph traversal. (Obviously we have to do some kind of traversal, but that is neatly hidden away inside the DisjointSet implementation.)
I start out with one component per tile, and then connect the tile to neighboring tiles that should be in the same basin. In my implementation I initially assumed that there is only one “lowest” point, by only connecting tiles to strictly downstream tiles. This would not work if the two lowest tiles in a basin were on the same height, but luckily for me the input is crafted to avoid this problem. I then realized that the level 9 “walls” effectively form a barrier around each basic, so we can simplify and just connect every tile to every z!=9 tile.
Now I know which basin each tile belongs to, so what is left is to compute the size of each basin and find the three largest basins.
func part2(m Map) {
// Start with every tile being its own component.
basins := disjointset.Make(m.Height * m.Width)
for pos := range m.AllPositions() {
height := m.At(pos)
if height == 9 {
continue // Don't join walls with anything.
}
adjPositions := m.AdjacentPositions(pos)
for _, adjPos := range adjPositions {
adjHeight := m.At(adjPos)
if adjHeight != 9 {
// Same basin -- connect the components.
basins.Union(m.Id(pos), m.Id(adjPos))
}
}
}
// Find the basin ID for every tile.
basinSizes := make([]int, m.Width*m.Height)
for j := 0; j < m.Height; j++ {
for i := 0; i < m.Width; i++ {
pos := Pos{i, j}
basinId := basins.Find(m.Id(pos))
basinSizes[basinId]++
}
}
sort.Sort(sort.Reverse(sort.IntSlice(basinSizes)))
result := basinSizes[0] * basinSizes[1] * basinSizes[2]
fmt.Println("Part 2:", result)
}
The rest of code
Mostly boilerplate and I/O.
package main
import (
"bufio"
"fmt"
"github.com/roessland/gopkg/disjointset"
"log"
"os"
"sort"
)
type Map struct {
Width, Height int
heights []int
}
type Pos struct {
I, J int
}
func (m Map) At(pos Pos) int {
return m.heights[pos.J*m.Width+pos.I]
}
// Id returns an unique ID for each position.
// This is needed by the DisjointSet/UnionFind implementation.
func (m Map) Id(pos Pos) int {
return pos.J*m.Width + pos.I
}
func (m Map) AllPositions() <-chan Pos {
ch := make(chan Pos)
go func() {
for j := 0; j < m.Height; j++ {
for i := 0; i < m.Width; i++ {
ch <- Pos{i, j}
}
}
close(ch)
}()
return ch
}
func (m Map) AdjacentPositions(pos Pos) []Pos {
var legalAdjPositions []Pos
for _, adjPos := range []Pos{
{pos.I - 1, pos.J}, {pos.I + 1, pos.J},
{pos.I, pos.J - 1}, {pos.I, pos.J + 1},
} {
if adjPos.I < 0 || adjPos.I >= m.Width {
continue
}
if adjPos.J < 0 || adjPos.J >= m.Height {
continue
}
legalAdjPositions = append(legalAdjPositions, adjPos)
}
return legalAdjPositions
}
func main() {
m := ReadInput()
part1(m)
part2(m)
}
func part1(m Map) {
totalRisk := 0
for pos := range m.AllPositions() {
height := m.At(pos)
adjPositions := m.AdjacentPositions(pos)
lowPoint := true
for _, adjPosition := range adjPositions {
adjHeight := m.At(adjPosition)
if height >= adjHeight {
lowPoint = false
break
}
}
if lowPoint {
risk := 1 + height
totalRisk += risk
}
}
fmt.Println("Part 1:", totalRisk)
}
func ReadInput() Map {
f, err := os.Open("input.txt")
if err != nil {
log.Fatal(err)
}
scanner := bufio.NewScanner(f)
var lines []string
for scanner.Scan() {
lines = append(lines, scanner.Text())
}
m := Map{
Height: len(lines),
Width: len(lines[0]),
heights: make([]int, len(lines)*len(lines[0])),
}
for j, line := range lines {
for i, c := range line {
m.heights[j*m.Width+i] = int(c - '0')
}
}
return m
}
DisjointSet implementation
You can import this package using go get github.com/roessland/gopkg/disjointset and then import thub.com/roessland/gopkg/disjointset.
It is inspired by Robert Sedgewick’s Algorithms course, which has a great explanation of Union-Find/DisjointSet.
package disjointset
// For usage, see the tests
type DisjointSet struct {
rank []int
parent []int
Count int // Number of connected components
}
func Make(size int) *DisjointSet {
var ds DisjointSet
ds.Count = size
ds.rank = make([]int, size)
ds.parent = make([]int, size)
for i := 0; i < size; i++ {
ds.parent[i] = i
}
return &ds
}
func (ds *DisjointSet) Find(i int) int {
if ds.parent[i] != i {
ds.parent[i] = ds.Find(ds.parent[i])
}
return ds.parent[i]
}
func (ds *DisjointSet) Connected(x, y int) bool {
return ds.Find(x) == ds.Find(y)
}
func (ds *DisjointSet) Union(x, y int) {
xRoot := ds.Find(x)
yRoot := ds.Find(y)
if xRoot != yRoot {
if ds.rank[xRoot] < ds.rank[yRoot] {
ds.parent[xRoot] = yRoot
} else if ds.rank[xRoot] > ds.rank[yRoot] {
ds.parent[yRoot] = xRoot
} else {
ds.parent[yRoot] = xRoot
ds.rank[xRoot]++
}
ds.Count--
}
}