AOC2022/day24/day24.go
Karl Spickermann 217990eb15 Day24
2022-12-25 22:40:43 +01:00

243 lines
6.6 KiB
Go

package main
import (
"AOC2022/helper"
"fmt"
)
type Simulation struct {
ActivePoints [][3]int
reachtimes map[[3]int]int
tornadoTimeline []map[[2]int]bool
endPoint [2]int
startPoint [2]int
fieldSize [2]int
bestTime int
}
func main() {
//args := os.Args[1:]
lines := helper.ReadTextFile("day24/input")
startPoint := [2]int{0, 0}
for i, char := range lines[0] {
if char == '.' {
startPoint[1] = i
}
}
endpoint := [2]int{len(lines) - 1, 0}
for i, char := range lines[len(lines)-1] {
if char == '.' {
endpoint[1] = i
}
}
tornados := [][3]int{}
for i := 1; i < len(lines)-1; i++ {
line := lines[i]
for j := 1; j < len(line)-1; j++ {
if lines[i][j] == '>' {
tornados = append(tornados, [3]int{i, j, 0})
}
if lines[i][j] == 'v' {
tornados = append(tornados, [3]int{i, j, 1})
}
if lines[i][j] == '<' {
tornados = append(tornados, [3]int{i, j, 2})
}
if lines[i][j] == '^' {
tornados = append(tornados, [3]int{i, j, 3})
}
}
}
tornadoTimeline := getTornadoTimeline(tornados, [2]int{len(lines), len(lines[0])}, 1000)
paths := [][3]int{[3]int{startPoint[0], startPoint[1], len(tornadoTimeline) - 1}}
simulation := Simulation{paths, make(map[[3]int]int), tornadoTimeline, endpoint, startPoint, [2]int{len(lines), len(lines[0])}, 999999}
endpoint1, runtime1 := oneRun(simulation)
simulationBack := Simulation{[][3]int{endpoint1}, make(map[[3]int]int), tornadoTimeline, startPoint, endpoint, [2]int{len(lines), len(lines[0])}, 999999}
endpoint2, runtime2 := oneRun(simulationBack)
simulationBackAgain := Simulation{[][3]int{endpoint2}, make(map[[3]int]int), tornadoTimeline, endpoint, startPoint, [2]int{len(lines), len(lines[0])}, 999999}
_, runtime3 := oneRun(simulationBackAgain)
fmt.Println(runtime1 + runtime2 + runtime3)
}
func oneRun(simulation Simulation) ([3]int, int) {
i := 0
for len(simulation.ActivePoints) > 0 {
simulation.step()
i++
}
fmt.Println(simulation.bestTime)
positionEnd := [3]int{}
for key, val := range simulation.reachtimes {
if key[0] == simulation.endPoint[0] && key[1] == simulation.endPoint[1] && val == simulation.bestTime {
positionEnd = key
}
}
fmt.Println(positionEnd)
return positionEnd, simulation.bestTime
}
func getTornadoTimeline(tornados [][3]int, fieldSize [2]int, time int) []map[[2]int]bool {
timeline := make([]map[[2]int]bool, 0)
tornadoCopy := make([][3]int, len(tornados))
copy(tornadoCopy, tornados)
for i := 0; i < time; i++ {
oneMinute := make(map[[2]int]bool)
tornados = stepTornado(tornados, fieldSize)
for _, tornado := range tornados {
oneMinute[[2]int{tornado[0], tornado[1]}] = true
}
timeline = append(timeline, oneMinute)
if Equal(tornados, tornadoCopy) {
break
}
}
return timeline
}
func stepTornado(tornados [][3]int, fieldSize [2]int) [][3]int {
directions := [4][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
newTornados := [][3]int{}
for _, val := range tornados {
dir := directions[val[2]]
newPos := [2]int{val[0] + dir[0], val[1] + dir[1]}
if newPos[0] < 1 || newPos[0] >= fieldSize[0]-1 ||
newPos[1] < 1 || newPos[1] >= fieldSize[1]-1 {
newPos = loop(newPos, dir, fieldSize)
}
newTornados = append(newTornados, [3]int{newPos[0], newPos[1], val[2]})
}
return newTornados
}
func loop(currentPosition [2]int, direction [2]int, fieldSize [2]int) [2]int {
newStartPosition := [2]int{1, 1}
if direction[0] == 0 {
newStartPosition[0] = currentPosition[0]
}
if direction[0] < 0 {
newStartPosition[0] = fieldSize[0] - 2
}
if direction[1] == 0 {
newStartPosition[1] = currentPosition[1]
}
if direction[1] < 0 {
newStartPosition[1] = fieldSize[1] - 2
}
return newStartPosition
}
func (simulation *Simulation) getNextTornado(input int) int {
val := input + 1
if val == len(simulation.tornadoTimeline) {
val = 0
}
return val
}
func (simulation *Simulation) step() {
currentPos := simulation.ActivePoints[len(simulation.ActivePoints)-1]
simulation.ActivePoints = simulation.ActivePoints[:len(simulation.ActivePoints)-1]
newPaths := simulation.getPossibNewPaths(currentPos)
newReachtime := simulation.reachtimes[currentPos] + 1
if newReachtime > simulation.bestTime || newReachtime > 1000 {
return
}
for i := 0; i < len(newPaths); i++ {
path := newPaths[i]
val, ok := simulation.reachtimes[path]
if [2]int{path[0], path[1]} == simulation.endPoint {
if simulation.bestTime > newReachtime {
simulation.bestTime = newReachtime
}
if !ok || val > newReachtime {
simulation.reachtimes[path] = newReachtime
}
} else if !ok || val > newReachtime {
simulation.reachtimes[path] = newReachtime
simulation.ActivePoints = append(simulation.ActivePoints, path)
}
}
}
func (simulation *Simulation) getPossibNewPaths(currentPos [3]int) [][3]int {
directions := [5][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {0, 0}}
currentTonardo := simulation.tornadoTimeline[simulation.getNextTornado(currentPos[2])]
var newPaths [][3]int
for i := 0; i < len(directions); i++ {
direction := directions[i]
newPos := [2]int{currentPos[0] + direction[0], currentPos[1] + direction[1]}
_, exists := currentTonardo[newPos]
if !exists && newPos == simulation.endPoint {
newPaths = append(newPaths, [3]int{newPos[0], newPos[1], simulation.getNextTornado(currentPos[2])})
}
if !exists && newPos == simulation.startPoint {
newPaths = append(newPaths, [3]int{newPos[0], newPos[1], simulation.getNextTornado(currentPos[2])})
}
if !exists &&
newPos[0] > 0 && newPos[0] < simulation.fieldSize[0]-1 &&
newPos[1] > 0 && newPos[1] < simulation.fieldSize[1]-1 {
newPaths = append(newPaths, [3]int{newPos[0], newPos[1], simulation.getNextTornado(currentPos[2])})
}
}
return newPaths
}
func (simulation Simulation) printRuntimes() {
for i := 0; i < simulation.fieldSize[0]; i++ {
line := []int{}
for j := 0; j < simulation.fieldSize[1]; j++ {
bestimte := 9999
for key, val := range simulation.reachtimes {
if key[0] == i && key[1] == j && val < bestimte {
bestimte = val
}
}
if bestimte == 9999 {
bestimte = 0
}
line = append(line, bestimte)
}
fmt.Println(line)
}
fmt.Println()
}
func (simulation Simulation) printTornados(time int) {
for i := 0; i < simulation.fieldSize[0]; i++ {
line := []int{}
for j := 0; j < simulation.fieldSize[1]; j++ {
value := 0
if simulation.tornadoTimeline[time][[2]int{i, j}] {
value++
}
line = append(line, value)
}
fmt.Println(line)
}
fmt.Println()
}
func get_some_key(m map[[2]int][][2]int) [2]int {
for k := range m {
return k
}
return [2]int{}
}
func Equal(a, b [][3]int) bool {
if len(a) != len(b) {
return false
}
for i, v := range a {
if v != b[i] {
return false
}
}
return true
}