1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
package main
import (
"bufio"
"fmt"
"os"
"strings"
)
func main() {
fmt.Println(find(readData("example.txt")))
fmt.Println(36, 81)
fmt.Println(find(readData("data.txt")))
}
type Candidate struct {
X, Y int
Alt byte
Head *TrailHead
}
func (c Candidate) Identity() int {
return (c.X << 16) | c.Y
}
type TrailHead struct {
Reaches map[int]bool
}
func findNextCandidates(x, y int, targetAlt byte, head *TrailHead, topo [][]byte) (result []Candidate) {
if x > 0 && topo[y][x-1] == targetAlt {
result = append(result, Candidate{x - 1, y, targetAlt, head})
}
if x < len(topo[y])-1 && topo[y][x+1] == targetAlt {
result = append(result, Candidate{x + 1, y, targetAlt, head})
}
if y > 0 && topo[y-1][x] == targetAlt {
result = append(result, Candidate{x, y - 1, targetAlt, head})
}
if y < len(topo)-1 && topo[y+1][x] == targetAlt {
result = append(result, Candidate{x, y + 1, targetAlt, head})
}
return
}
func find(topo [][]byte) (resultPart1, resultPart2 int) {
candidates := make([]Candidate, 0)
for y, line := range topo {
for x, alt := range line {
if alt == 0 {
trailhead := &TrailHead{make(map[int]bool)}
candidate := Candidate{x, y, alt, trailhead}
candidates = append(candidates, candidate)
}
}
}
for len(candidates) > 0 {
current := candidates[len(candidates)-1]
candidates = candidates[:len(candidates)-1]
nextCandidates := findNextCandidates(current.X, current.Y, current.Alt+1, current.Head, topo)
if current.Alt == 8 {
for _, summit := range nextCandidates {
id := summit.Identity()
_, alreadyIn := summit.Head.Reaches[id]
if !alreadyIn {
summit.Head.Reaches[id] = true
resultPart1++
}
}
resultPart2 += len(nextCandidates)
} else {
candidates = append(candidates, nextCandidates...)
}
}
return
}
func readData(fileName string) (topo [][]byte) {
fp, err := os.Open(fileName)
if err != nil {
panic(err)
}
scanner := bufio.NewScanner(fp)
for scanner.Scan() {
line := []byte(strings.TrimSpace(scanner.Text()))
if len(line) == 0 {
continue
}
for i := range line {
line[i] = line[i] - '0'
}
topo = append(topo, line)
}
return
}
|
