aoc2024/day-18/internal/two/graph.go

package two

import (
	"slices"
	"strings"

	"github.com/onyx-and-iris/aoc2024/day-18/internal/point"
	"github.com/onyx-and-iris/aoc2024/day-18/internal/queue"
	log "github.com/sirupsen/logrus"
)

type graph struct {
	start point.Point
	end   point.Point
	data  []string
}

func newGraph(width, height, numCorruptions int, corruptedCoords [][]int) *graph {
	var data []string
	var sb strings.Builder
	for range height {
		for range width {
			sb.WriteRune('.')
		}
		data = append(data, sb.String())
		sb.Reset()
	}

	for _, coords := range corruptedCoords[:numCorruptions] {
		data[coords[1]] = replaceAtIndex(data[coords[1]], '#', coords[0])
	}

	return &graph{point.Point{X: 0, Y: 0}, point.Point{X: len(data[0]) - 1, Y: len(data) - 1}, data}
}

func (g *graph) String() string {
	return strings.Join(g.data, "\n")
}

func (g *graph) isOutOfBounds(p point.Point) bool {
	return p.X < 0 || p.Y < 0 || p.Y >= len(g.data) || p.X >= len(g.data[p.Y])
}

func (g *graph) valueAt(p point.Point) rune {
	return rune(g.data[p.Y][p.X])
}

func (g *graph) addCorruption(p point.Point) {
	g.data[p.Y] = replaceAtIndex(g.data[p.Y], '#', p.X)
}

func (g *graph) bfs() bool {
	queue := queue.New[point.Point]()
	queue.Enqueue(g.start)
	visited := make(map[point.Point]struct{})

	for !queue.IsEmpty() {
		current := queue.Dequeue()

		if current == g.end {
			return true
		}

		_, ok := visited[current]
		if ok {
			continue
		}
		visited[current] = struct{}{}

		for _, n := range neighbours(current) {
			if g.isOutOfBounds(n) {
				continue
			}

			if g.valueAt(n) == '#' {
				continue
			}

			queue.Enqueue(n)
		}
	}
	log.Debugf("\n%s\n", g.debug(visited))

	return false
}

func (g *graph) debug(visited map[point.Point]struct{}) string {
	temp := slices.Clone(g.data)
	for p := range visited {
		if g.valueAt(p) == '#' {
			continue
		}
		temp[p.Y] = replaceAtIndex(temp[p.Y], 'O', p.X)
	}
	return strings.Join(temp, "\n")
}