advent-of-code/grids.go

297 lines
6.0 KiB
Go
Raw Permalink Normal View History

package aoc
2024-01-02 17:02:12 -07:00
import (
"cmp"
2024-01-22 16:07:16 -07:00
"fmt"
2024-10-30 13:32:44 -06:00
"iter"
2024-01-02 17:02:12 -07:00
"sort"
2024-01-22 16:07:16 -07:00
"strings"
2024-01-12 12:09:44 -07:00
"golang.org/x/exp/maps"
2024-01-02 17:02:12 -07:00
)
type Vector struct {
2024-01-01 09:26:31 -07:00
Offset Point[int]
Scale int
}
2024-01-01 09:26:31 -07:00
func (v Vector) Point() Point[int] {
return v.Offset.Scale(v.Scale)
}
2024-01-01 09:26:31 -07:00
type Point[T integer] [2]T
2024-01-01 09:26:31 -07:00
func (p Point[T]) Add(a Point[T]) Point[T] {
return Point[T]{p[0] + a[0], p[1] + a[1]}
}
2024-01-01 09:26:31 -07:00
func (p Point[T]) Scale(m T) Point[T] {
return Point[T]{p[0] * m, p[1] * m}
}
2024-01-01 09:26:31 -07:00
func (p Point[T]) Less(b Point[T]) bool {
2023-12-28 18:57:22 -07:00
if p[0] != b[0] {
return p[0] < b[0]
}
return p[1] < b[1]
}
func Transpose[T any](matrix [][]T) [][]T {
rows, cols := len(matrix), len(matrix[0])
m := make([][]T, cols)
for i := range m {
m[i] = make([]T, rows)
}
for i := 0; i < cols; i++ {
for j := 0; j < rows; j++ {
m[i][j] = matrix[j][i]
}
}
return m
}
// NumPoints the number of the points inside an outline plus the number of points in the outline
2024-01-01 09:26:31 -07:00
func NumPoints(outline []Point[int], borderLength int) int {
// shoelace - find the float area in a shape
sum := 0
for _, p := range Pairwise(outline) {
row1, col1 := p[0][0], p[0][1]
row2, col2 := p[1][0], p[1][1]
sum += row1*col2 - row2*col1
}
area := sum / 2
// pick's theorem - find the number of points in a shape given its area
return (ABS(area) - borderLength/2 + 1) + borderLength
}
2023-12-28 18:57:22 -07:00
2024-01-01 09:26:31 -07:00
type Map[I integer, T any] [][]T
2023-12-28 18:57:22 -07:00
2024-01-02 17:02:12 -07:00
func (m *Map[I, T]) Get(p Point[I]) (Point[I], T, bool) {
2023-12-28 18:57:22 -07:00
var zero T
if !m.Valid(p) {
2024-01-01 09:26:31 -07:00
return [2]I{0, 0}, zero, false
2023-12-28 18:57:22 -07:00
}
return p, (*m)[p[0]][p[1]], true
}
2024-01-02 17:02:12 -07:00
func (m *Map[I, T]) Size() (I, I) {
2023-12-28 18:57:22 -07:00
if m == nil || len(*m) == 0 {
return 0, 0
}
2024-01-01 09:26:31 -07:00
return I(len(*m)), I(len((*m)[0]))
2023-12-28 18:57:22 -07:00
}
2024-01-02 17:02:12 -07:00
func (m *Map[I, T]) Valid(p Point[I]) bool {
2023-12-28 18:57:22 -07:00
rows, cols := m.Size()
return p[0] >= 0 && p[0] < rows && p[1] >= 0 && p[1] < cols
}
2024-01-02 17:02:12 -07:00
2024-01-12 12:09:44 -07:00
type cmap[C number, N comparable] struct {
base pather[C, N]
neighbors map[N]map[N]C
}
func (m *cmap[C, N]) Cost(a, b N) C {
if v, ok := m.neighbors[a]; ok {
return v[b]
}
return 0
}
func (m *cmap[C, N]) Neighbors(n N) []N {
if v, ok := m.neighbors[n]; ok {
return maps.Keys(v)
}
return nil
}
func (m *cmap[C, N]) Target(n N, c C) bool {
return m.base.Target(n, c)
}
func (m *cmap[C, N]) String() string {
var b = &strings.Builder{}
for k, nbs := range m.neighbors {
fmt.Fprintln(b, k)
2024-01-22 16:07:16 -07:00
for to, c := range nbs {
fmt.Fprintln(b, " ", to, c)
2024-01-12 12:09:44 -07:00
}
}
return b.String()
}
func CompressMap[C number, N comparable](p pather[C, N], start N) pather[C, N] {
var next = []N{start}
var visited = make(map[N]map[N]C)
var n N
for len(next) > 0 {
n, next = next[len(next)-1], next[:len(next)-1]
if _, ok := visited[n]; ok {
continue
}
nbs := p.Neighbors(n)
if len(nbs) == 2 {
a, b := nbs[0], nbs[1]
if to, ok := visited[a]; ok {
to[b] = to[n] + p.Cost(n, b)
delete(to, n)
visited[a] = to
2024-01-22 16:07:16 -07:00
} else if to, ok := visited[b]; ok {
2024-01-12 12:09:44 -07:00
to[a] = to[n] + p.Cost(n, a)
delete(to, n)
visited[b] = to
}
continue
}
visited[n] = make(map[N]C)
next = append(next, nbs...)
for _, to := range nbs {
visited[n][to] = p.Cost(n, to)
}
}
return &cmap[C, N]{base: p, neighbors: visited}
}
2024-10-30 13:32:44 -06:00
type adjacencyList[V comparable] map[V][]V
type graph[V comparable, W cmp.Ordered] map[V]*vertex[V, W]
type graphOption[V comparable, W cmp.Ordered] func(g *graph[V, W])
type vertex[V comparable, W cmp.Ordered] struct {
2024-01-02 17:02:12 -07:00
Value V
Edges edges[V, W]
}
func (v *vertex[V, W]) Neighbors() []V {
var nbs []V
sort.Sort(v.Edges)
for _, e := range v.Edges {
nbs = append(nbs, e.Vertex.Value)
}
return nbs
}
2024-10-30 13:32:44 -06:00
type edge[V comparable, W cmp.Ordered] struct {
2024-01-02 17:02:12 -07:00
Vertex *vertex[V, W]
Weight W
}
2024-10-30 13:32:44 -06:00
type edges[V comparable, W cmp.Ordered] []edge[V, W]
2024-01-02 17:02:12 -07:00
func (e edges[V, W]) Len() int { return len(e) }
func (e edges[V, W]) Less(i, j int) bool { return e[i].Weight < e[j].Weight }
func (e edges[V, W]) Swap(i, j int) { e[i], e[j] = e[j], e[i] }
2024-10-30 13:32:44 -06:00
func Graph[V comparable, W cmp.Ordered](opts ...graphOption[V, W]) *graph[V, W] {
g := make(graph[V, W])
2024-01-02 17:02:12 -07:00
for _, opt := range opts {
opt(&g)
}
return &g
}
2024-10-30 13:32:44 -06:00
func (g *graph[V, W]) AddVertex(id V, value V) {
2024-01-12 12:09:44 -07:00
(*g)[id] = &vertex[V, W]{Value: value}
2024-01-02 17:02:12 -07:00
}
2024-10-30 13:32:44 -06:00
func (g *graph[V, W]) AddEdge(from, to V, w W) {
2024-01-02 17:02:12 -07:00
if g == nil {
return
}
if _, ok := (*g)[from]; !ok {
2024-11-20 09:07:01 -07:00
g.AddVertex(from, from)
2024-01-02 17:02:12 -07:00
}
if _, ok := (*g)[to]; !ok {
2024-11-20 09:07:01 -07:00
g.AddVertex(to, to)
2024-01-02 17:02:12 -07:00
}
2024-01-12 12:09:44 -07:00
(*g)[from].Edges = append((*g)[from].Edges, edge[V, W]{(*g)[to], w})
2024-01-02 17:02:12 -07:00
}
2024-10-30 13:32:44 -06:00
func (g *graph[V, W]) Neighbors(v V) []V {
2024-01-02 17:02:12 -07:00
if g == nil {
return nil
}
return (*g)[v].Neighbors()
}
2024-10-30 13:32:44 -06:00
func (g *graph[V, W]) AdjacencyList() adjacencyList[V] {
m := make(map[V][]V)
2024-01-02 17:02:12 -07:00
for id, v := range *g {
if len(v.Edges) == 0 {
continue
}
m[id] = v.Neighbors()
}
return m
}
2024-10-30 13:32:44 -06:00
func WithAdjacencyList[W cmp.Ordered, V comparable](list adjacencyList[V]) graphOption[V, W] {
2024-01-02 17:02:12 -07:00
var zeroW W
2024-10-30 13:32:44 -06:00
return func(g *graph[V, W]) {
2024-01-02 17:02:12 -07:00
for vertex, edges := range list {
if _, ok := (*g)[vertex]; !ok {
g.AddVertex(vertex, vertex)
}
// add edges to vertex
for _, edge := range edges {
// add edge as vertex, if not added
if _, ok := (*g)[edge]; !ok {
g.AddVertex(edge, edge)
}
g.AddEdge(vertex, edge, zeroW) // no weights in this adjacency list
}
}
}
}
2024-10-30 13:32:44 -06:00
func (g *graph[V, W]) BFS(start V) iter.Seq[V] {
visited := make(map[V]bool)
stack := NewStack(start)
return func(yield func(V) bool) {
for !stack.IsEmpty() {
current := stack.Pull()
if visited[current] {
continue
}
visited[current] = true
if !yield(current) {
return
}
neighbors := g.Neighbors(current)
for _, n := range neighbors {
if !visited[n] {
stack.Push(n)
}
}
}
}
}
// DFS returns a sequence of vertices in depth-first order, starting at the
// given vertex.
func (g *graph[V, W]) DFS(start V) iter.Seq[V] {
visited := make(map[V]bool)
stack := NewStack(start)
return func(yield func(V) bool) {
for !stack.IsEmpty() {
current := stack.Pop()
if visited[current] {
continue
}
visited[current] = true
if !yield(current) {
return
}
for _, n := range Reverse(g.Neighbors(current)) {
if !visited[n] {
stack.Push(n)
}
}
}
}
}