75 lines
1.5 KiB
Go
75 lines
1.5 KiB
Go
package day17
|
|
|
|
import (
|
|
"crypto/md5"
|
|
"fmt"
|
|
"math"
|
|
"tools"
|
|
)
|
|
|
|
func getMD5Sum(s string) string {
|
|
return fmt.Sprintf("%x", md5.Sum([]byte(s)))
|
|
}
|
|
|
|
type DirDelta struct {
|
|
x int
|
|
y int
|
|
}
|
|
|
|
var dirDeltas = []DirDelta{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}
|
|
var dirs = []string{"U", "D", "L", "R"}
|
|
var pathLen = math.MaxInt32
|
|
var foundPath = ""
|
|
|
|
func findPath(passcode, path string, x, y int, findLongest bool) {
|
|
doors := getMD5Sum(passcode + path)[:4]
|
|
if !findLongest && len(path) >= pathLen {
|
|
return
|
|
}
|
|
if x == 3 && y == 3 {
|
|
if findLongest {
|
|
if len(path) > pathLen {
|
|
foundPath = path
|
|
pathLen = len(path)
|
|
}
|
|
} else {
|
|
if len(path) < pathLen {
|
|
foundPath = path
|
|
pathLen = len(path)
|
|
}
|
|
}
|
|
return
|
|
}
|
|
|
|
for i, c := range doors {
|
|
if x+dirDeltas[i].x < 0 || x+dirDeltas[i].x > 3 || y+dirDeltas[i].y < 0 || y+dirDeltas[i].y > 3 {
|
|
// border case
|
|
continue
|
|
}
|
|
|
|
if c > 97 { // door open
|
|
findPath(passcode, path+dirs[i], x+dirDeltas[i].x, y+dirDeltas[i].y, findLongest)
|
|
}
|
|
}
|
|
}
|
|
|
|
func Part1(puzzle tools.AoCPuzzle) interface{} {
|
|
for _, passcode := range puzzle.GetInputArray() {
|
|
pathLen = math.MaxInt32
|
|
findPath(passcode, "", 0, 0, false)
|
|
// fmt.Println("Passcode:", passcode, "Path:", foundPath)
|
|
}
|
|
|
|
return foundPath
|
|
}
|
|
|
|
func Part2(puzzle tools.AoCPuzzle) interface{} {
|
|
for _, passcode := range puzzle.GetInputArray() {
|
|
pathLen = 0
|
|
findPath(passcode, "", 0, 0, true)
|
|
// fmt.Println("Passcode:", passcode, "Len:", len(foundPath), "Path:", foundPath)
|
|
}
|
|
|
|
return len(foundPath)
|
|
}
|