aoc2023/day23/day23.go

package day23

import (
	"fmt"
	"log"

	"gitea.paas.celticinfo.fr/oabrivard/aoc2023/utils"
)

type Coord struct {
	row int
	col int
}

var cache map[Coord]int = map[Coord]int{}

func getNeighbors(matrix [][]byte, point Coord) []Coord {
	result := []Coord{}
	height := len(matrix)
	width := len(matrix[0])

	switch matrix[point.row][point.col] {
	case '^':
		if point.row > 0 && matrix[point.row-1][point.col] != 'O' && matrix[point.row-1][point.col] != '#' && matrix[point.row-1][point.col] != 'v' {
			result = append(result, Coord{point.row - 1, point.col})
		}
	case 'v':
		if point.row < height-1 && matrix[point.row+1][point.col] != 'O' && matrix[point.row+1][point.col] != '#' && matrix[point.row+1][point.col] != '^' {
			result = append(result, Coord{point.row + 1, point.col})
		}
	case '>':
		if point.col < width-1 && matrix[point.row][point.col+1] != 'O' && matrix[point.row][point.col+1] != '#' && matrix[point.row][point.col+1] != '<' {
			result = append(result, Coord{point.row, point.col + 1})
		}
	case '<':
		if point.col > 0 && matrix[point.row][point.col-1] != 'O' && matrix[point.row][point.col-1] != '#' && matrix[point.row][point.col-1] != '>' {
			result = append(result, Coord{point.row, point.col - 1})
		}
	case '.':
		if point.row > 0 && matrix[point.row-1][point.col] != 'O' && matrix[point.row-1][point.col] != '#' && matrix[point.row-1][point.col] != 'v' {
			result = append(result, Coord{point.row - 1, point.col})
		}
		if point.row < height-1 && matrix[point.row+1][point.col] != 'O' && matrix[point.row+1][point.col] != '#' && matrix[point.row+1][point.col] != '^' {
			result = append(result, Coord{point.row + 1, point.col})
		}
		if point.col > 0 && matrix[point.row][point.col-1] != 'O' && matrix[point.row][point.col-1] != '#' && matrix[point.row][point.col-1] != '>' {
			result = append(result, Coord{point.row, point.col - 1})
		}
		if point.col < width-1 && matrix[point.row][point.col+1] != 'O' && matrix[point.row][point.col+1] != '#' && matrix[point.row][point.col+1] != '<' {
			result = append(result, Coord{point.row, point.col + 1})
		}
	case 'O':
		// nothing to do, since we already explored this point
	default:
		log.Fatalln("Impossible state")
	}

	return result
}

func findLongestPath(matrix [][]byte, start, end Coord) int {

	if length, found := cache[start]; found {
		return length
	}

	//fmt.Printf("(%d,%d) ", start.row, start.col)
	if start.row == 21 && start.col == 17 {
		fmt.Print("break")
	}

	if start == end {
		return 0
	}

	maxlength := -1

	neighbors := getNeighbors(matrix, start)
	old := matrix[start.row][start.col]
	matrix[start.row][start.col] = 'O'

	for _, neighbor := range neighbors {
		length := findLongestPath(matrix, neighbor, end)

		if length > maxlength {
			maxlength = length
		}
	}

	matrix[start.row][start.col] = old

	if maxlength == -1 {
		return -1
	}

	//fmt.Printf("(%d,%d) = %d\n", start.row, start.col, maxlength+1)

	cache[start] = maxlength + 1
	return maxlength + 1
}

func Part1(lines []string) int {
	matrix := [][]byte{}

	for _, line := range lines {
		matrix = append(matrix, []byte(line))
	}

	height := len(matrix)
	width := len(matrix[0])

	start := Coord{0, 1}
	end := Coord{height - 1, width - 2}
	result := findLongestPath(matrix, start, end)

	return result
}

type Vertice struct {
	ID      int
	coord   Coord
	edges   map[int]*Edge
	treated bool
}

type Edge struct {
	left  *Vertice
	right *Vertice
	cost  int
}

var verticeID int = 0
var vertices map[int]*Vertice = map[int]*Vertice{}

func findExitCoords(matrix [][]byte, point, previous Coord) []Coord {
	height := len(matrix)
	width := len(matrix[0])
	result := []Coord{}

	if point.row > 0 && matrix[point.row-1][point.col] != '#' && previous.row != point.row-1 {
		result = append(result, Coord{point.row - 1, point.col})
	}
	if point.row < height-1 && matrix[point.row+1][point.col] != '#' && previous.row != point.row+1 {
		result = append(result, Coord{point.row + 1, point.col})
	}
	if point.col > 0 && matrix[point.row][point.col-1] != '#' && previous.col != point.col-1 {
		result = append(result, Coord{point.row, point.col - 1})
	}
	if point.col < width-1 && matrix[point.row][point.col+1] != '#' && previous.col != point.col+1 {
		result = append(result, Coord{point.row, point.col + 1})
	}

	return result
}

func findNextJunction(matrix [][]byte, curr, previous, end Coord) (Coord, Coord, int) {
	exitCoords := findExitCoords(matrix, curr, previous)
	dist := 1
	for len(exitCoords) == 1 && exitCoords[0] != end {
		previous = curr
		curr = exitCoords[0]
		dist++
		exitCoords = findExitCoords(matrix, curr, previous)
	}

	return curr, previous, dist
}

func buildGraph(matrix [][]byte, treated map[Coord]*Vertice, curr, previous, end Coord) *Vertice {
	if vertice, found := treated[curr]; found {
		return vertice
	}

	verticeID++
	currVertice := Vertice{verticeID, curr, map[int]*Edge{}, false}
	vertices[currVertice.ID] = &currVertice
	treated[curr] = &currVertice

	exitCoords := findExitCoords(matrix, curr, previous)
	// here we have a junction or the end
	for _, exitCoord := range exitCoords {
		nextCoord, prevCoord, dist := findNextJunction(matrix, exitCoord, curr, end)
		// create a vertice for next Coord
		nextVertice := buildGraph(matrix, treated, nextCoord, prevCoord, end)

		// Create two edges (one for both directions of the relationship)
		edgeLeft := Edge{&currVertice, nextVertice, dist}
		edgeRight := Edge{nextVertice, &currVertice, dist}

		// add the left edge to the current vertice
		currVertice.edges[nextVertice.ID] = &edgeLeft

		// add the right edge to the target vertice
		nextVertice.edges[currVertice.ID] = &edgeRight
	}

	return &currVertice
}

/*
	type Vertice struct {
		ID      int
		coord   Coord
		edges   []*Edge
		treated bool
	}

	type Edge struct {
		left  *Vertice
		right *Vertice
		cost  int
	}

var verticeID int = 0

	func findExitCoords(matrix [][]byte, point Coord) []Coord {
		height := len(matrix)
		width := len(matrix[0])
		result := []Coord{}

		if point.row > 0 && matrix[point.row-1][point.col] != '#' {
			result = append(result, Coord{point.row - 1, point.col})
		}
		if point.row < height-1 && matrix[point.row+1][point.col] != '#' {
			result = append(result, Coord{point.row + 1, point.col})
		}
		if point.col > 0 && matrix[point.row][point.col-1] != '#' {
			result = append(result, Coord{point.row, point.col - 1})
		}
		if point.col < width-1 && matrix[point.row][point.col+1] != '#' {
			result = append(result, Coord{point.row, point.col + 1})
		}

		return result
	}

	func findNextJunction(matrix [][]byte, curr, end Coord) (Coord, int) {
		exitCoords := findExitCoords(matrix, curr)
		dist := 1
		for len(exitCoords) == 2 && exitCoords[0] != end && exitCoords[1] != end {
			curr = exitCoords[0]
			dist++
			exitCoords = findExitCoords(matrix, curr)
		}

		return curr, dist
	}

	func buildGraph(matrix [][]byte, treated map[Coord]*Vertice, curr, end Coord) *Vertice {
		if vertice, found := treated[curr]; found {
			return vertice
		}

		verticeID++
		currVertice := Vertice{verticeID, curr, []*Edge{}, false}
		treated[curr] = &currVertice

		exitCoords := findExitCoords(matrix, curr)
		// here we have a junction or the end
		for _, exitCoord := range exitCoords {
			nextCoord, dist := findNextJunction(matrix, exitCoord, end)
			// create a node for next Coord
			nextNode := buildGraph(matrix, treated, nextCoord, end)

			// Create an edge
			edge := Edge{&currVertice, nextNode, dist}

			// add this edge to the current node
			currVertice.edges = append(currVertice.edges, &edge)
		}

		return &currVertice
	}
*/
func printGraph(start *Vertice) {
	if start.treated {
		return
	}
	start.treated = true
	for _, edge := range start.edges {
		fmt.Printf("(%d,%d) --%d--> (%d,%d)\n", edge.left.coord.row, edge.left.coord.col, edge.cost, edge.right.coord.row, edge.right.coord.col)
	}

	for _, edge := range start.edges {
		printGraph(edge.right)
	}

}

func longestPath(start *Vertice, distSoFar int, visited map[int]bool, end Coord) int {
	if start.coord == end {
		return distSoFar
	}

	if visited[start.ID] {
		return 0
	}

	visited[start.ID] = true

	maximum := -1

	for _, edge := range start.edges {
		vertex := edge.right
		visitedClone := utils.CloneMap(visited)
		dist := longestPath(vertex, distSoFar+edge.cost, visitedClone, end)

		if dist > maximum {
			maximum = dist
		}
	}

	return maximum
}

func Part2(lines []string) int {
	height := len(lines)
	width := len(lines[0])
	matrix := make([][]byte, height)

	for row, line := range lines {
		matrix[row] = make([]byte, width)
		for col, r := range line {
			if r == '#' {
				matrix[row][col] = '#'
			} else {
				matrix[row][col] = '.'
			}
		}
	}

	treated := map[Coord]*Vertice{}
	start := Coord{0, 1}
	end := Coord{height - 1, width - 2}
	graph := buildGraph(matrix, treated, start, Coord{-1, -1}, end)

	printGraph(graph)

	result := longestPath(graph, 0, map[int]bool{}, end)

	return result
}