-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.go
137 lines (127 loc) · 3.11 KB
/
main.go
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
package main
import (
"fmt"
"io/ioutil"
"os"
"regexp"
"strings"
)
type Point struct {
left string
right string
}
func parseInput(content string) (string, map[string]Point) {
lines := strings.Split(string(content), "\n")
instructions := lines[0]
// lines[1] is an empty line, and thus should be ignored
mapping := make(map[string]Point)
for i := 2; i < len(lines); i++ {
pattern := `^([^\s]+) = \(([^\s]+), ([^\s]+)\)$`
re := regexp.MustCompile(pattern)
matches := re.FindStringSubmatch(lines[i])
mapping[matches[1]] = Point{left: matches[2], right: matches[3]}
}
return instructions, mapping
}
func part01(filepath string) (int, error) {
content, err := ioutil.ReadFile(filepath)
if err != nil {
return 0, err
}
instructions, mapping := parseInput(string(content))
currentPos := "AAA"
steps := 0
for currentPos != "ZZZ" {
for _, instruction := range instructions {
steps++
switch instruction {
case 'L':
currentPos = mapping[currentPos].left
case 'R':
currentPos = mapping[currentPos].right
}
if currentPos == "ZZZ" {
break
}
}
}
return steps, nil
}
func findInitialPositions(mapping map[string]Point) []string {
var initialPos []string
for name := range mapping {
if strings.HasSuffix(name, "A") {
initialPos = append(initialPos, name)
}
}
return initialPos
}
func getSteps(currentPos string, instructions string, mapping map[string]Point) int {
steps := 0
for !strings.HasSuffix(currentPos, "Z") {
for _, instruction := range instructions {
steps++
switch instruction {
case 'L':
currentPos = mapping[currentPos].left
case 'R':
currentPos = mapping[currentPos].right
}
if strings.HasSuffix(currentPos, "Z") {
break
}
}
}
return steps
}
func GCD(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
func LCM(periods []int) int {
lcm := periods[0]
for _, period := range periods[1:] {
lcm = lcm * period / GCD(lcm, period)
}
return lcm
}
// Each path is periodic, so we just need to find the period of each path,
// and then the amount of steps will be the least common multiple (LCM)
// between the periods
// This is true because the initial and ending locations have the same signature:
// HVA = (NMF, CTG) NMZ = (CTG, NMF)
// LBA = (TBT, HGC) SJZ = (HGC, TBT)
// FXA = (MQX, NDF) GNZ = (NDF, MQX)
// GHA = (DLD, MBC) TNZ = (MBC, DLD)
// PSA = (MLN, HHG) BNZ = (HHG, MLN)
// AAA = (CLB, XLR) ZZZ = (XLR, CLB)
func part02(filepath string) (int, error) {
content, err := ioutil.ReadFile(filepath)
if err != nil {
return 0, err
}
instructions, mapping := parseInput(string(content))
initialPos := findInitialPositions(mapping)
var periods []int
for i := 0; i < len(initialPos); i++ {
periods = append(periods, getSteps(initialPos[i], instructions, mapping))
}
steps := LCM(periods)
return steps, nil
}
func main() {
result, err := part01("input.txt")
if err != nil {
fmt.Fprintln(os.Stderr, "Error reading file:", err)
return
}
fmt.Println("Part 01:", result)
result, err = part02("input.txt")
if err != nil {
fmt.Fprintln(os.Stderr, "Error reading file:", err)
return
}
fmt.Println("Part 02:", result)
}