101 lines
2.5 KiB
Go
101 lines
2.5 KiB
Go
package main
|
|
|
|
import (
|
|
"AOC2021/src/helper"
|
|
"fmt"
|
|
"os"
|
|
)
|
|
|
|
type field struct {
|
|
before [2]int
|
|
cost int
|
|
sumCost int
|
|
}
|
|
|
|
func main() {
|
|
args := os.Args[1:]
|
|
input, err := helper.GetInput(args[0])
|
|
if err != nil {
|
|
fmt.Println(err)
|
|
}
|
|
var caveMap [500][500]field
|
|
createCaveMapPart2(input, &caveMap)
|
|
caveMap[0][0].before = [2]int{-2, -2}
|
|
caveMap[0][0].sumCost = 1
|
|
activePoints := make(map[[2]int]struct{})
|
|
activePoints[[2]int{0, 0}] = struct{}{}
|
|
|
|
getBestRouteLength(activePoints, caveMap)
|
|
}
|
|
|
|
func createCaveMap(input []string, caveMap *[500][500]field) {
|
|
for i, row := range input {
|
|
for j, char := range row {
|
|
caveMap[i][j] = field{[2]int{-1, -1}, int(char - '0'), 0}
|
|
}
|
|
}
|
|
}
|
|
|
|
func createCaveMapPart2(input []string, caveMap *[500][500]field) {
|
|
length := len(input)
|
|
|
|
for i:= 0; i< 5; i++ {
|
|
for j:= 0; j< 5; j++ {
|
|
setPointsWithAdditives(input,caveMap,i*length,j*length,i+j)
|
|
}
|
|
}
|
|
}
|
|
|
|
func setPointsWithAdditives(input []string, caveMap *[500][500]field,additiveColumn int, additiveRow int, n int) {
|
|
for i, row := range input {
|
|
for j, char := range row {
|
|
cost := (int(char-'0') + n)
|
|
if cost > 9 {
|
|
cost -= 9
|
|
}
|
|
caveMap[i+additiveColumn][j+additiveRow] = field{[2]int{-1, -1}, cost, 0}
|
|
}
|
|
}
|
|
}
|
|
|
|
func getBestRouteLength(activePoints map[[2]int]struct{}, caveMap [500][500]field) {
|
|
for len(activePoints) > 0 {
|
|
step(&caveMap, &activePoints)
|
|
}
|
|
caveMapLength := len(caveMap)
|
|
fmt.Println(caveMap[caveMapLength-1][caveMapLength-1].sumCost - 1)
|
|
}
|
|
|
|
func step(caveMap *[500][500]field, activePoints *map[[2]int]struct{}) {
|
|
point := get_some_key(*activePoints)
|
|
delete(*activePoints,point)
|
|
x := point[0]
|
|
y := point[1]
|
|
currentFieldSumCost := caveMap[y][x].sumCost
|
|
currentFieldBefore := caveMap[y][x].before
|
|
directions := [4][2]int{{0, -1}, {+1, 0}, {0, 1}, {-1, 0}}
|
|
for _, direction := range directions {
|
|
px := x + direction[0]
|
|
py := y + direction[1]
|
|
if py < len(caveMap) && py >= 0 && px < len(caveMap[0]) && px >= 0 && (currentFieldBefore[0] != px || currentFieldBefore[1] != py) {
|
|
sumCost := caveMap[py][px].cost + currentFieldSumCost
|
|
fieldBefore := caveMap[py][px].before
|
|
if fieldBefore[0] == -1 || caveMap[py][px].sumCost > sumCost {
|
|
caveMap[py][px].sumCost = sumCost
|
|
caveMap[py][px].before = [2]int{x, y}
|
|
if py != len(caveMap)-1 || px != len(caveMap)-1 {
|
|
(*activePoints)[[2]int{px, py}] = struct{}{}
|
|
}else{
|
|
fmt.Println(sumCost)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
func get_some_key(m map[[2]int]struct{}) [2]int {
|
|
for k := range m {
|
|
return k
|
|
}
|
|
return [2]int{-1,-1}
|
|
} |