2021-12-24 13:10:26 +01:00
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 {
2021-12-24 13:31:48 +01:00
[ 11 ] rune { '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' } ,
2021-12-24 14:09:03 +01:00
[ 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
2021-12-24 13:10:26 +01:00
for len ( currentBoards ) > 0 {
step ( & currentBoards , & endBoards )
}
minEnergy := 9999999
2021-12-24 14:09:03 +01:00
for endBoard , energy := range endBoards {
if checkWinner ( endBoard ) && energy < minEnergy {
if minEnergy > energy {
minEnergy = energy
2021-12-24 13:10:26 +01:00
}
}
}
fmt . Println ( minEnergy )
}
func checkWinner ( board board ) bool {
for amphoidType , room := range destX {
for _ , val := range board . rooms [ room ] {
2021-12-24 13:31:48 +01:00
if val != amphoidType {
2021-12-24 13:10:26 +01:00
return false
}
}
}
return true
}
2021-12-24 14:09:03 +01:00
func step ( currentBoards * map [ board ] int , endBoards * map [ board ] int ) {
for selectedBoard , selectedEnergy := range * currentBoards {
delete ( * currentBoards , selectedBoard )
2021-12-24 13:10:26 +01:00
possibleMoves := getPossibleMoves ( selectedBoard )
if len ( possibleMoves ) == 0 {
2021-12-24 14:09:03 +01:00
if ( * endBoards ) [ selectedBoard ] == 0 || selectedEnergy < ( * endBoards ) [ selectedBoard ] {
( * endBoards ) [ selectedBoard ] = selectedEnergy
}
2021-12-24 13:10:26 +01:00
}
for start , targets := range possibleMoves {
for _ , target := range targets {
2021-12-24 14:09:03 +01:00
tmpNewBoard , tmpNewErnergy := useMove ( selectedBoard , [ 2 ] [ 2 ] int { start , target } , selectedEnergy )
if ( * currentBoards ) [ tmpNewBoard ] == 0 || tmpNewErnergy < ( * currentBoards ) [ tmpNewBoard ] {
( * currentBoards ) [ tmpNewBoard ] = tmpNewErnergy
}
2021-12-24 13:10:26 +01:00
}
}
}
return
}
2021-12-24 14:09:03 +01:00
func useMove ( board board , move [ 2 ] [ 2 ] int , energy int ) ( board , int ) {
2021-12-24 13:10:26 +01:00
//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 {
2021-12-24 14:09:03 +01:00
traveledDistance += Abs ( move [ 0 ] [ 1 ] - ( ( move [ 1 ] [ 0 ] - 1 ) * 2 + 2 ) )
2021-12-24 13:10:26 +01:00
traveledDistance += move [ 1 ] [ 1 ] + 1
} else {
2021-12-24 14:09:03 +01:00
traveledDistance += Abs ( move [ 1 ] [ 1 ] - ( ( move [ 0 ] [ 0 ] - 1 ) * 2 + 2 ) )
2021-12-24 13:10:26 +01:00
traveledDistance += move [ 0 ] [ 1 ] + 1
}
2021-12-24 14:09:03 +01:00
energy += costs [ amphoidType ] * ( traveledDistance )
return board , energy
2021-12-24 13:10:26 +01:00
}
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
}