AoC2021/src/day23/day23.go

package main

import (
	"AOC2021/src/helper"
	"fmt"
	"strings"
)

type board struct {
	corridor [11]rune
	rooms    [4][4]rune
}

var costs = map[rune]int{
	'A': 1,
	'B': 10,
	'C': 100,
	'D': 1000,
}

var destX = map[rune]int{
	'A': 0,
	'B': 1,
	'C': 2,
	'D': 3,
}

var enterableCorridorPos = [7]int{0, 1, 3, 5, 7, 9, 10}

func main() {
	playBoard := board{
		[11]rune{'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
		[4][4]rune{{'D', 'D', 'D', 'B'}, {'D', 'C', 'B', 'A'}, {'C', 'B', 'A', 'A'}, {'B', 'A', 'C', 'C'}}}
	currentBoards := make(map[board]int)
	endBoards := make(map[board]int)
	currentBoards[playBoard] = 0
	for len(currentBoards) > 0 {
		step(&currentBoards, &endBoards)
	}
	minEnergy := 9999999
	for endBoard, energy := range endBoards {
		if checkWinner(endBoard) && energy < minEnergy {
			if minEnergy > energy {
				minEnergy = energy
			}
		}
	}
	fmt.Println(minEnergy)
}

func checkWinner(board board) bool {
	for amphoidType, room := range destX {
		for _, val := range board.rooms[room] {
			if val != amphoidType {
				return false
			}
		}
	}
	return true
}

func step(currentBoards *map[board]int, endBoards *map[board]int) {
	for selectedBoard, selectedEnergy := range *currentBoards {
		delete(*currentBoards, selectedBoard)
		possibleMoves := getPossibleMoves(selectedBoard)
		if len(possibleMoves) == 0 {
			if (*endBoards)[selectedBoard] == 0 || selectedEnergy < (*endBoards)[selectedBoard] {
				(*endBoards)[selectedBoard] = selectedEnergy
			}
		}
		for start, targets := range possibleMoves {
			for _, target := range targets {
				tmpNewBoard, tmpNewErnergy := useMove(selectedBoard, [2][2]int{start, target}, selectedEnergy)
				if (*currentBoards)[tmpNewBoard] == 0 || tmpNewErnergy < (*currentBoards)[tmpNewBoard] {
					(*currentBoards)[tmpNewBoard] = tmpNewErnergy
				}
			}
		}
	}
	return
}

func useMove(board board, move [2][2]int, energy int) (board, int) {
	//Remove moved Amphoid
	var amphoidType rune
	if move[0][0] == 0 {
		amphoidType = board.corridor[move[0][1]]
		board.corridor[move[0][1]] = '.'
	} else {
		amphoidType = board.rooms[move[0][0]-1][move[0][1]]
		board.rooms[move[0][0]-1][move[0][1]] = '.'
	}

	//Place moved Amphoid
	if move[1][0] == 0 {
		board.corridor[move[1][1]] = amphoidType
	} else {
		board.rooms[move[1][0]-1][move[1][1]] = amphoidType
	}

	//Calculate cost
	traveledDistance := 0
	if move[0][0] == 0 {
		traveledDistance += Abs(move[0][1] - ((move[1][0]-1)*2 + 2))
		traveledDistance += move[1][1] + 1
	} else {
		traveledDistance += Abs(move[1][1] - ((move[0][0]-1)*2 + 2))
		traveledDistance += move[0][1] + 1
	}
	energy += costs[amphoidType] * (traveledDistance)
	return board, energy
}

func getPossibleMoves(board board) map[[2]int][][2]int {
	possibleMoves := make(map[[2]int][][2]int)

	for i, val := range board.corridor {
		if val != '.' {
			tmpPossibleMoves := getPossibleMovesFromPos(board, [2]int{0, i})
			if len(tmpPossibleMoves) > 0 {
				possibleMoves[[2]int{0, i}] = tmpPossibleMoves
			}
		}
	}
	for i, room := range board.rooms {
		for j, val := range room {
			if val != '.' {
				tmpPossibleMoves := getPossibleMovesFromPos(board, [2]int{i + 1, j})
				if len(tmpPossibleMoves) > 0 {
					possibleMoves[[2]int{i + 1, j}] = tmpPossibleMoves
				}
			}
		}
	}
	return possibleMoves
}

func getPossibleMovesFromPos(board board, position [2]int) [][2]int {
	if position[0] == 0 {
		enterableRooms := [][2]int{}
		for i, _ := range board.rooms {
			possiblePos := roomCanEnter(board, i, position[1], board.corridor[position[1]])
			if possiblePos != -1 {
				enterableRooms = append(enterableRooms, [2]int{i + 1, possiblePos})
			}
		}
		return enterableRooms
	} else {
		if isInCorrectRoom(board, position) || cantLeaveRoom(board, position) {
			return [][2]int{}
		}
		enterableCoordinates := [][2]int{}
		for _, pos := range enterableCorridorPos {
			if corridorCoordinateCanEnter(board.corridor, position[0]-1, pos) {
				enterableCoordinates = append(enterableCoordinates, [2]int{0, pos})
			}
		}
		//for i, _ := range board.rooms {
		//	possiblePos := roomCanEnter(board, i, position[1]*2+2, board.rooms[position[0]-1][position[1]])
		//	if possiblePos != -1 {
		//		enterableCoordinates = append(enterableCoordinates, [2]int{i + 1, possiblePos})
		//	}
		//}
		return enterableCoordinates
	}
}

func cantLeaveRoom(board board, position [2]int) bool {
	room := board.rooms[position[0]-1]
	for i := 0; i < position[1]; i++ {
		if room[i] != '.' {
			return true
		}
	}
	return false
}

func isInCorrectRoom(board board, position [2]int) bool {
	amphoidType := board.rooms[position[0]-1][position[1]]
	if !(destX[amphoidType] == position[0]-1) {
		return false
	}
	otherAmphoidTypes := helper.RemoveCharactersFromString("ABCD", string(amphoidType))
	for _, element := range board.rooms[position[0]-1] {
		if strings.ContainsRune(otherAmphoidTypes, element) {
			return false
		}
	}
	return true
}

func roomCanEnter(board board, positionRoom int, positionAmphoid int, amphoidType rune) int {
	room := board.rooms[positionRoom]
	corridor := board.corridor
	if !(destX[amphoidType] == positionRoom) {
		return -1
	}
	otherAmphoidTypes := helper.RemoveCharactersFromString("ABCD", string(amphoidType))
	for _, element := range room {
		if strings.ContainsRune(otherAmphoidTypes, element) {
			return -1
		}
	}
	target := 2 + positionRoom*2
	n := positionAmphoid
	if target < positionAmphoid {
		n--
	} else {
		n++
	}
	for n != target {
		if corridor[n] != '.' {
			return -1
		}
		if target < positionAmphoid {
			n--
		} else {
			n++
		}
	}
	for i := len(room) - 1; i >= 0; i-- {
		if room[i] == '.' {
			return i
		}
	}
	return -1
}

func corridorCoordinateCanEnter(corridor [11]rune, currentRoom int, target int) bool {
	if corridor[target] != '.' {
		return false
	}
	startPos := 2 + currentRoom*2
	i := startPos
	for i != target {
		if corridor[i] != '.' {
			return false
		}
		if target < startPos {
			i--
		} else {
			i++
		}
	}
	return true
}

func Abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}