147 lines
2.5 KiB
Go
147 lines
2.5 KiB
Go
package main
|
|
|
|
import (
|
|
"bufio"
|
|
_ "embed"
|
|
"fmt"
|
|
|
|
aoc "go.sour.is/advent-of-code"
|
|
)
|
|
|
|
// var log = aoc.Log
|
|
|
|
func main() { aoc.MustResult(aoc.Runner(run)) }
|
|
|
|
type result struct {
|
|
valuePT1 int
|
|
valuePT2 int
|
|
}
|
|
|
|
func (r result) String() string { return fmt.Sprintf("%#v", r) }
|
|
|
|
func run(scan *bufio.Scanner) (*result, error) {
|
|
|
|
var start aoc.Point[int]
|
|
var m [][]rune
|
|
|
|
for scan.Scan() {
|
|
txt := scan.Text()
|
|
|
|
if txt == "" {
|
|
continue
|
|
}
|
|
|
|
m = append(m, []rune(txt))
|
|
|
|
for i, c := range txt {
|
|
if c == '^' {
|
|
start = aoc.Point[int]{len(m) - 1, i}
|
|
}
|
|
}
|
|
}
|
|
|
|
sum, positions, _ := runPT1(m, start)
|
|
|
|
loops := runPT2(m, start, positions)
|
|
|
|
return &result{sum, loops}, nil
|
|
}
|
|
|
|
func isOutOfBounds(p, topRight, bottomLeft aoc.Point[int]) bool {
|
|
return p[0] < topRight[0] ||
|
|
p[0] > bottomLeft[0] ||
|
|
p[1] < topRight[1] ||
|
|
p[1] > bottomLeft[1]
|
|
}
|
|
|
|
func printMap(m [][]rune, o aoc.Point[int]) {
|
|
for i, row := range m {
|
|
if i == o[0] {
|
|
row[o[1]] = 'O'
|
|
}
|
|
println(string(row))
|
|
}
|
|
println()
|
|
}
|
|
|
|
func runPT1(m [][]rune, start aoc.Point[int]) (int, []aoc.Point[int], bool) {
|
|
m = copyMap(m)
|
|
|
|
topRight := aoc.Point[int]{0, 0}
|
|
bottomLeft := aoc.Point[int]{len(m) - 1, len(m[0]) - 1}
|
|
|
|
directions := []aoc.Point[int]{
|
|
{-1, 0}, // up
|
|
{0, 1}, // right
|
|
{1, 0}, // down
|
|
{0, -1}, // left
|
|
}
|
|
|
|
d := 0
|
|
current := start
|
|
var loopStart [3]int
|
|
var paths = aoc.NewSet[[3]int]()
|
|
for !isOutOfBounds(current, topRight, bottomLeft) {
|
|
m[current[0]][current[1]] = 'X'
|
|
next := current.Add(directions[d])
|
|
if isOutOfBounds(next, topRight, bottomLeft) {
|
|
break
|
|
}
|
|
if m[next[0]][next[1]] == '#' {
|
|
d = (d + 1) % 4
|
|
pt := [3]int{current[0], current[1], d}
|
|
if paths.Has(pt) {
|
|
if loopStart == pt {
|
|
return 0, nil, true
|
|
}
|
|
if loopStart == [3]int{} {
|
|
loopStart = pt
|
|
}
|
|
}
|
|
|
|
paths.Add(pt)
|
|
continue
|
|
}
|
|
|
|
current = next
|
|
}
|
|
|
|
var sum int
|
|
var points []aoc.Point[int]
|
|
for y, row := range m {
|
|
for x, v := range row {
|
|
if v == 'X' {
|
|
points = append(points, aoc.Point[int]{x, y})
|
|
sum++
|
|
}
|
|
}
|
|
}
|
|
|
|
return sum, points, false
|
|
}
|
|
|
|
func runPT2(m [][]rune, start aoc.Point[int], points []aoc.Point[int]) int {
|
|
sum := 0
|
|
for _, p := range points {
|
|
cm := copyMap(m)
|
|
cm[p[0]][p[1]] = '#'
|
|
|
|
_, _, isOOB :=runPT1(cm, start)
|
|
|
|
if !isOOB {
|
|
printMap(cm, start)
|
|
sum++
|
|
}
|
|
}
|
|
|
|
return sum
|
|
}
|
|
|
|
func copyMap(m [][]rune) [][]rune {
|
|
newM := make([][]rune, len(m))
|
|
for i, row := range m {
|
|
newM[i] = make([]rune, len(row))
|
|
copy(newM[i], row)
|
|
}
|
|
return newM
|
|
} |