aoc24/day16/dijsktra.go.disabled

package main

import (
	"fmt"
	"slices"

	"git.mstar.dev/mstar/aoc24/util"
	"git.mstar.dev/mstar/goutils/sliceutils"
	"github.com/RyanCarrier/dijkstra/v2"
)

type NodeType int

// A crossing is a path location with 3 or 4 other paths next to it
type Node struct {
	At    util.Vec2
	Type  NodeType
	Dirs  []util.Vec2
	Index int
}

const (
	NodeInvalid NodeType = iota
	NodeCrossing
	NodeCorner
	NodeDeadEnd
)

var (
	DirUp    = util.Vec2{X: 0, Y: -1}
	DirRight = util.Vec2{X: 1, Y: 0}
	DirDown  = util.Vec2{X: 0, Y: 1}
	DirLeft  = util.Vec2{X: -1, Y: 0}
)

var startDir = DirRight

// Get the size of the bord
func getSize(lines []string) util.Vec2 {
	return util.Vec2{X: int64(len(lines[0])), Y: int64(len(lines))}
}

// Count the paths next to a given positon
func countPathsAt(lines [][]rune, at util.Vec2) []util.Vec2 {
	center := lines[at.Y][at.X]
	paths := []util.Vec2{}
	if center == '#' {
		return paths
	}
	if util.SafeGet(lines, at.Up()) != '#' {
		paths = append(paths, DirUp)
	}
	if util.SafeGet(lines, at.Down()) != '#' {
		paths = append(paths, DirDown)
	}
	if util.SafeGet(lines, at.Left()) != '#' {
		paths = append(paths, DirLeft)
	}
	if util.SafeGet(lines, at.Right()) != '#' {
		paths = append(paths, DirRight)
	}
	return paths
}

func getCrossingsAndCornerPositions(lines [][]rune) []Node {
	out := []Node{}

	for iy, line := range lines {
		for ix, char := range line {
			if char == '#' {
				continue
			}
			pos := util.Vec2{X: int64(ix), Y: int64(iy)}
			dirs := countPathsAt(lines, pos)
			// Crossings have 3 or more paths out
			if len(dirs) >= 3 {
				out = append(out, Node{pos, NodeCrossing, dirs, len(out)})
			}
			// Also include dead ends
			if len(dirs) == 1 {
				out = append(out, Node{pos, NodeDeadEnd, dirs, len(out)})
			}
			// Location is a corner if the paths are not opposite each other
			if len(dirs) == 2 {
				if !dirs[0].Mult(-1).Eq(dirs[1]) {
					out = append(out, Node{pos, NodeCorner, dirs, len(out)})
				}
			}
		}
	}
	return out
}

func getNeighbourNodes(nodes []Node, index int) []int {
	target := nodes[index]

	potential := sliceutils.Filter(nodes, func(t Node) bool {
		return t.Index != index && (t.At.X == target.At.X || t.At.Y == target.At.Y)
	})

	hits := []Node{}
	for _, dir := range target.Dirs {
		switch dir {
		case DirUp:
			hits = append(hits, slices.MinFunc(potential, func(a, b Node) int {
				if a.At.X != target.At.X || a.At.Y > target.At.Y {
					return -1
				}
				if b.At.X != target.At.X || b.At.Y > target.At.Y {
					return 1
				}
				return util.AbsI(
					int(target.At.Y)-int(a.At.Y),
				) - util.AbsI(
					int(target.At.Y)-int(b.At.Y),
				)
			}))
		case DirDown:
			hits = append(hits, slices.MinFunc(potential, func(a, b Node) int {
				if a.At.X != target.At.X || a.At.Y < target.At.Y {
					return -1
				}
				if b.At.X != target.At.X || b.At.Y < target.At.Y {
					return 1
				}
				return util.AbsI(
					int(target.At.Y)-int(a.At.Y),
				) - util.AbsI(
					int(target.At.Y)-int(b.At.Y),
				)
			}))
		case DirLeft:
			hits = append(hits, slices.MinFunc(potential, func(a, b Node) int {
				if a.At.Y != target.At.Y || a.At.X > target.At.X {
					return -1
				}
				if b.At.Y != target.At.Y || b.At.X > target.At.X {
					return 1
				}
				return util.AbsI(
					int(target.At.X)-int(a.At.X),
				) - util.AbsI(
					int(target.At.X)-int(b.At.X),
				)
			}))
		case DirRight:
			hits = append(hits, slices.MinFunc(potential, func(a, b Node) int {
				if a.At.Y != target.At.Y || a.At.X > target.At.X {
					return -1
				}
				if b.At.Y != target.At.Y || b.At.X > target.At.X {
					return 1
				}
				return util.AbsI(
					int(target.At.X)-int(a.At.X),
				) - util.AbsI(
					int(target.At.X)-int(b.At.X),
				)
			}))
		default:
			panic("Unknown dir")
		}
	}
	return sliceutils.Map(hits, func(t Node) int { return t.Index })
}

func addNodesToGraph(nodes []Node, graph *dijkstra.Graph) {
	for i := range len(nodes) {
		if err := graph.AddEmptyVertex(i); err != nil {
			panic(err)
		}
	}
	for _, node := range nodes {
		for _, n := range getNeighbourNodes(nodes, node.Index) {
			if err := graph.AddArc(node.Index, n, node.At.Add(nodes[n].At.Mult(-1)).LenSquared()); err != nil {
				panic(err)
			}
		}
	}
}

func findEnd(lines [][]rune) util.Vec2 {
	for iy, line := range lines {
		for ix, char := range line {
			if char == 'E' {
				return util.Vec2{X: int64(ix), Y: int64(iy)}
			}
		}
	}
	return util.Vec2{X: -1, Y: -1}
}

func findStart(lines [][]rune) util.Vec2 {
	for iy, line := range lines {
		for ix, char := range line {
			if char == 'S' {
				return util.Vec2{X: int64(ix), Y: int64(iy)}
			}
		}
	}
	return util.Vec2{X: -1, Y: -1}
}

func main() {
	inputLines := util.FileContentToNonEmptyLines(util.LoadFileFromArgs())
	// size := getSize(inputLines)
	inputLineChars := sliceutils.Map(inputLines, func(t string) []rune { return []rune(t) })
	nodes := getCrossingsAndCornerPositions(inputLineChars)
	// fmt.Println(nodes)
	// slices.MaxFunc(x S, cmp func(a E, b E) int)
	graph := dijkstra.NewGraph()
	addNodesToGraph(nodes, &graph)
	startVec := findStart(inputLineChars)
	endVec := findEnd(inputLineChars)
	startI := slices.IndexFunc(nodes, func(e Node) bool { return e.At == startVec })
	endI := slices.IndexFunc(nodes, func(e Node) bool { return e.At == endVec })

	path, err := graph.Shortest(startI, endI)
	fmt.Println(path, err)
}