243 lines
6.6 KiB
Go
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
|
|
}
|