aoc-2024/cmd/day_12/main.go

package main

import (
	"bufio"
	"errors"
	"fmt"
	"io"
	"log"
	"os"
	"slices"
)

func trim(l []byte) []byte {
	if len(l) == 0 {
		return l
	}
	if l[len(l)-1] != '\n' {
		return l
	}
	return l[:len(l)-1]
}

func main() {
	width, height := 0, 0
	r := bufio.NewReader(os.Stdin)

	// Read input
	plat := make([]byte, 0, 256)
	for {
		line, err := r.ReadBytes('\n')
		if errors.Is(err, io.EOF) {
			break
		}
		if err != nil {
			log.Fatalf("While reading input: %v", err)
		}
		line = trim(line)
		if width == 0 {
			width = len(line)
		}
		if len(line) != width {
			log.Fatalf("Expected input line to be of length %d but has length %d", width, len(line))
		}
		height++
		plat = append(plat, line...)
	}

	// Find regions
	regions := make([][]int, 1, 32)
	degree := make([]int, len(plat))
	incidence := make([]int, len(plat))
	for i, plot := range plat {
		up, lt, rt, dn := i-width, i-1, i+1, i+width

		if dn < len(plat) && plot == plat[dn] {
			degree[i]++
		}
		if i/width == rt/width && plot == plat[rt] {
			degree[i]++
		}
		if 0 <= up && plot == plat[up] {
			degree[i]++
			regionId := incidence[up]
			incidence[i] = regionId
			regions[regionId] = append(regions[regionId], i)
		}
		if 0 <= lt && i/width == lt/width && plot == plat[lt] {
			degree[i]++
			regionId := incidence[lt]
			if incidence[i] == 0 {
				incidence[i] = regionId
				regions[regionId] = append(regions[regionId], i)
				continue
			}
			if incidence[i] == regionId {
				continue
			}
			// If we made it this far, then incidence[i] was just
			// set to incidence[plat[up]]. Therefore, plat[up]
			// exists.
			// Join subregions with different ids.
			var src, tgt int
			switch {
			case regionId < incidence[i]:
				tgt, src = regionId, incidence[i]
			case regionId > incidence[i]:
				src, tgt = regionId, incidence[i]
			}
			for _, pid := range regions[src] {
				incidence[pid] = tgt
				regions[tgt] = append(regions[tgt], pid)
			}
			regions = slices.Delete(regions, src, src+1)
			incidence[i] = tgt
			continue
		}
		if incidence[i] > 0 {
			continue
		}
		region := make([]int, 1, 32)
		region[0] = i
		regions = append(regions, region)
		incidence[i] = len(regions) - 1
	}
	regions = regions[1:]

	// Find prices
	total := 0
	for _, r := range regions {
		perimeter := 0
		for _, pid := range r {
			perimeter += 4 - degree[pid]
		}
		total += len(r) * perimeter
	}
	fmt.Printf("%d\n", total)
}