aoc24/day16/main.go

package main

// Look at https://topaz.github.io/paste/#XQAAAQB1CAAAAAAAAAA4GEiZzRd1JAgz+whYRQxSFI7XvmlfhtGDinecZE7XVglOhhPLih7tF+1f6vGBXHx2f7N/fIfjMG8zy2b5K1bcEP2Fo6yufIOrK2Xv9CFqxAiFcqXF+B4dWDdaic6Mhmi96bCxTu3B1MuJ8XPiKzAsC1j5U5qhN1K9v/wrCnRnSs483gy4bYiKZacHfPN6AsZrOcqsgagmb5XZWYgYt6yR6lJ7yx0goiNLILnmpT8E9yBh5igU8VCxKT8lpj05Ce5ffUlcz4mCgQC5jenYOl86fCFPgFC05AvKYVOmGpjW8syIdhCLxhQJnhNsljM5wHIUezS9qwRsjXZTfItq30EnkIM9mdSPZY2/eGBlasPQi5LR+l5JFw9w3W3fesXYEB2u9yc/umujdgTI4RikSMdOfdYOrgCLuPFA72fHU3tGk2oyL5k58ZAR1SKFm+7XExv3gFPh6t+mrFjJ9QZ7qEb19gn0kMt2MaSiNLzyB8cJ9Dr3yxTGqfBOPsJPSI2jM2H1xgg1fu7gBZAYu5+KQ1CyctZ9mFzm25QxvrNyLFoNTPKn9ikZw7kUmqL6mIwu4bdJPwHivcPJTg0gNw03vByP90Yd/JGfGc+sFDd3V3R+LWLj3r3vIqs4QiSSgF/FOsQQjPPCt51Px1gtSR0opaqNeKHOAZirql6UaFuE/UPgUVH87T/q/Qi+jeLtc+pE3KySx42V4YJvPFEZKYCmGhrt1inGQXpS4K53V+VuCMBmo0jFayu8azXUyXaf2TgAtRNMmzCr2UmW+XnhCuMrdiEzj/vEH6WMrnJsfQlB8LrkwLYjdp16kMGavefwDk84W4C0lIcaDLRrxd+z5tN8+6jBpamqrsJy7BiKbDq7swhTXGoss0Xl2ZychI1h95+ZkFRQPm2ykeIwRcMwUIIA3WE8mXvo79noiPpQgasyUEqfGBEulP9/AaIidnEmK20OPFW4iwxCy/DinEok9tpMRocHYYQyyjFiqgd4D4blrPIDPjy0PE+zGhhrpyOOPEL7lEOoLCOHm8E54KuYX0eX1jnnjOSBlhO2//OOAmyWb2adhy5ir5ZWsqnXQaLo0FPwefYre1c6QuppDgiDgww0DhyroJ4YLvEn70ELBqlTIlcHI2XLDrD2wJF8lKa0TzrS3W+o3w86g1WSRLOWmcaCinUYEFSgaGsJzkNjkHS0IILRn2pWSxHqDxE5o2vR6ji41ijmNUDfq2gM9Gi+gTs+WgPKG+a4RX9qWY3aNqRleT89ZdORfsfz5/H1B0R7NDXcvoUY8fZ76k0ylqS1uc4Dc2ZTynjcufAHl4PbX9Sd/X1rXgvWac3RO5F8ztK8ESr1LqYZDqrQYNiwY+7F6P/W/BYU
// and https://topaz.github.io/paste/#XQAAAQDkCQAAAAAAAAA4GEiZzRd1JAgz+whYRQxSFI7XvmlfhtGDinecZE7XVglOhhPLih7tF+1f6vGBXHx2f7N/fIfjMG8zy2b5K1bcEP2Fo6yufIOrK2Xv9CFqxAiFcqXF+B4dWDZXMbthHyfiUnWQNzkV0hcT5wVw9evKcKh6zuVp40d6Delxu4q84FVJ2dhY/eNJLsgsqMaSnCN8+e4FFMobzvc4ZXLFZQrIjVJ0UJwQ7ZKOvJDlemAVoOBoABHsgOgAJCFm4JV2lELwBITIKT9LzmRsO7giPuslQ7Zsz3Hs9czf3v/ly4cWYb2QQMsQPahsGW2aIYGEflk2nhYJPAosdN9zZ285PGXNNrW5e9NHP5AnsS9lkvf3Kedlg2bQd+ByV/EhMGpwOQjNYG0JpZBF5rJzWVdsuYwvetCboF9ZqInecZftwTsJtyTV2P70EYjs5ipojuXXieZ6QG/XxI/aDOh4WXuWORVA0TxxMtLzuiUElWvTdAjA17uwb1/1i12tbP6s6EFNB6IMgaZnQv0o2zAcIH7em3/HdDXdRytvqC96G34ml/kFYUvvQu1tbK0f9lZIfUtPt30fKSM2zg4NJ60S2DNHt8zU6JvrGqyk/2CPSoeineqtMlQLoTm+a+jRr0FcUEpSMNWYm5bOpcllImxoVUXA7HV0FTDYM0yo8q/pMptPAp/971Z4HCMjsOyJTKuQeAXK8iIYqWaXXpcyhwaaDZ99+p8rlz5K1xAT308o5A4ZdcIALJ3ZEtNlD/9Y5aZ7+Ynngr4O72arMxGuS6wAUj001ocWXbSOEGlmGeCWVUdIEuRF2RQUlcBzFluDR9FeUkVoGqnjGLQ1MWSyRCfKm2btiWELjge8ge4TZEd7KVG5Nrm8cKrZDAYjZ0xkO8p8nnSTlIGJ1Vft1y7SEsxexvx0O0Flz4rQg1Z6SR1JNqOuTkGjhirnSdBN+r6Mvs2Fqb/Kq/FJlHe+kXSF1bitp2skfxdiFYqEEdL+unScYL7SAczwANBr/IiznSJyyL9zfBYvXQcVerkWkfAlm5ape09UaxgGv9LKREALhYAzN6AJDDB9c6tRbN+plzVIRN9CBmDVLReSIo7R8E0etA8L3yhbe2BBLfN4lL2gAXtzzJjYvkUp9raqCz61WMvHreUD2PhTazl+kwjM8IUzmo2DFrXU1ZzOF/T7XWXrjlqgOzBmEE/rldgY0ddx8e0vSj7gKD8EUIPAlR6trZcdCA0L2ENYbOisKQnTn/cfnHJl8NeXH0AOxNKw+V+mRh3W7S747+nBiRmseGkDM17g3MR6hoVdW3V3thtUuwgtP7VBfwdvjlumN1m2L3a6of+hqL7djDL3IzQQBnlhEdszcToONrRBmVRJOMf0ECPY5A9brSO1jR6sVTjQF1nKabW6tEFLuVHcr+BiKUP+pZKKz8amUuffmQixFGfeWUKS0RJTMJt8TVzczSpqNvaJ02r+5qgkN5PddKwMufcpMeTEQy4IRFTCwM6spWm9FVB/8uR3Htfv1KgA0Z6cSkH/+Y3ogw==
// Maybe also https://github.com/AhmedYassineMaalej/AoC-2024/blob/master/src/problems/day16.rs
// And more https://github.com/ayoubzulfiqar/advent-of-code/blob/main/2024/Go/Day16/part_1.go

import (
	"fmt"
	"math"
	"slices"
	"strings"

	"git.mstar.dev/mstar/goutils/sliceutils"

	"git.mstar.dev/mstar/aoc24/util"
)

// A crossing is a path location with 3 or 4 other paths next to it
type Crossing struct {
	At          util.Vec2
	LowestScore int
	LowestFrom  util.Vec2   // Index into list of crossings
	Neighbours  []util.Vec2 // Directions where a path is
}

type Area map[int64]map[int64]*Crossing

type Wrapper struct {
	A Area
}

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, at.Up())
	}
	if util.SafeGet(lines, at.Down()) != '#' {
		paths = append(paths, at.Down())
	}
	if util.SafeGet(lines, at.Left()) != '#' {
		paths = append(paths, at.Left())
	}
	if util.SafeGet(lines, at.Right()) != '#' {
		paths = append(paths, at.Right())
	}
	return paths
}

func linesToMap(lines [][]rune, size util.Vec2) Area {
	area := Area{}
	// Ensure area has full maps
	for i := range size.Y {
		area[i] = map[int64]*Crossing{}
	}
	for iy, line := range lines {
		for ix, char := range line {
			pos := util.Vec2{X: int64(ix), Y: int64(iy)}
			switch char {
			case '.', 'E', 'S':
				dirs := countPathsAt(lines, pos)
				area[int64(ix)][int64(iy)] = &Crossing{
					At:          pos,
					LowestScore: math.MaxInt64,
					LowestFrom:  util.Vec2{X: -1, Y: -1},
					Neighbours:  dirs,
				}
			default:
			}
		}
	}
	return area
}

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 invalid positon if none found
	return util.Vec2{X: -1, Y: -1}
}

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 invalid positon if none found
	return util.Vec2{X: -1, Y: -1}
}

func walk(
	area *Wrapper,
	from util.Vec2,
	dir util.Vec2,
	score int,
) {
	// Idea: walk forward from start until crossing or wall
	// At crossing, defer a walker for both sides (if not walled off) but prioritise forwards
	// At crossing, check if own score is lower than current score
	// If it is, update score and set own origin
	// Else if crossing has a lower score than self, abort

	// Special case:
	// If at end, update end "crossing" following the earlier rules

	// Walk forward in dir until no node found
	type WalkTarget struct {
		Pos, Dir util.Vec2
		Score    int
	}
	// targets := []WalkTarget{}
	defer fmt.Println("Deffered done", from)
	fmt.Println("Starting", from)
	prev := from
	for pos := from.Add(dir); area.A[pos.X][pos.Y] != nil; pos = pos.Add(dir) {
		score++
		node := area.A[pos.X][pos.Y]
		if node.LowestScore <= score {
			return
		}
		node.LowestScore = score
		node.LowestFrom = prev
		// node.LowestFrom = pos.Add(dir.Mult(-1))
		fmt.Println("Setting node", pos, score, node.LowestFrom)
		// Get all directions that don't match current walking direction (and reverse)
		filtered := sliceutils.Filter(node.Neighbours, func(t util.Vec2) bool {
			return !t.Add(pos.Mult(-1)).Eq(dir) && !t.Add(pos.Mult(-1)).Eq(dir.Mult(-1))
		})
		// fmt.Println("Filtered neighbours of node", filtered)
		for _, neighbour := range filtered {
			fmt.Println("Adding target", neighbour)
			// targets = append(targets, WalkTarget{
			// 	neighbour, neighbour.Add(pos.Mult(-1)), score + 1001,
			// })
			defer walk(area, neighbour, neighbour.Add(pos.Mult(-1)), score+1001)
		}
		fmt.Println("Stepping", dir)
		prev = pos
	}
	// fmt.Println("Hitting stored targets", from)
	// for _, target := range targets {
	// 	walk(area, target.Pos, target.Dir, target.Score)
	// }
	fmt.Println("Done, walking deferred", from)
}

func visualisePath(area Area, endPos, size util.Vec2, inputLineRunes [][]rune) string {
	lineCopy := [][]rune{}
	for _, line := range inputLineRunes {
		lineCopy = append(lineCopy, slices.Clone(line))
	}
	for pos := endPos; pos.IsInBounds(size); pos = area[pos.X][pos.Y].LowestFrom {
		fmt.Println("Path elem", pos)
		lineCopy[pos.Y][pos.X] = 'x'
	}
	builder := strings.Builder{}
	for _, line := range lineCopy {
		for _, char := range line {
			builder.WriteRune(char)
		}
		builder.WriteRune('\n')
	}
	return builder.String()
}

func main() {
	inputLines := util.FileContentToNonEmptyLines(util.LoadFileFromArgs())
	size := getSize(inputLines)
	inputLineChars := sliceutils.Map(inputLines, func(t string) []rune { return []rune(t) })
	area := linesToMap(inputLineChars, size)

	start := findStart(inputLineChars)
	end := findEnd(inputLineChars)
	// Fill entire map
	fmt.Println("Filling right")
	wrapped := Wrapper{area}
	walk(&wrapped, start, DirRight, 0)
	fmt.Println("Filling up")
	walk(&wrapped, start, DirUp, 1000)
	fmt.Println("Filling down")
	walk(&wrapped, start, DirDown, 1000)
	fmt.Println("Filling left")
	walk(&wrapped, start, DirLeft, 2000)
	fmt.Printf("%#v\n", area[start.X][start.Y])
	fmt.Printf("Task 1: %d\n", area[end.X][end.Y].LowestScore)
	fmt.Println(visualisePath(area, end, size, inputLineChars))
}