Skip to content

Commit 00458eb

Browse files
NathanjmsNathanjms
committed
day 20 2024
With some hints from reddit, not sure I'd have got this one without, but it makes more sense than day 17ptb
1 parent 1bc12dc commit 00458eb

File tree

1 file changed

+98
-60
lines changed

1 file changed

+98
-60
lines changed

‎2024/go/day20/main.go

Lines changed: 98 additions & 60 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@ import (
44
"aoc-shared/pkg/sharedcode"
55
"aoc-shared/pkg/sharedstruct"
66
"fmt"
7+
"math"
78
"os"
89
"path/filepath"
910
"runtime"
@@ -34,70 +35,123 @@ func main() {
3435

3536
func partOne(contents []string) {
3637
grid := parseToGrid(contents)
38+
distancesToPoint := make([][]int, len(grid))
39+
for i := 0; i < len(grid); i++ {
40+
distancesToPoint[i] = make([]int, len(grid[i]))
41+
for j := 0; j < len(grid[i]); j++ {
42+
distancesToPoint[i][j] = -1
43+
}
44+
}
45+
3746
start, end := findStartAndEnd(contents)
38-
numSeconds := bfs(grid, start, end)
39-
savedSecondsCount := make(map[int]int, 0)
47+
distancesToPoint[start[0]][start[1]] = 0
48+
bfsDetermineDistances(grid, start, end, &distancesToPoint)
4049

41-
displayGrid(grid)
50+
count := 0
4251

43-
// We'll go through all options of removals. If they can remove just 1, or 1&2 or 2, is this 3 options??
44-
// We might need to avoid wasting time and duplicating, 1,2 != 2,1?? Will try without first
45-
for i := 1; i < len(grid)-2; i++ {
46-
for j := 1; j < len(grid[i])-1; j++ {
47-
nextMustBeHash := false
48-
if grid[i][j] == 'E' || grid[i][j] == 'S' {
49-
continue
50-
}
51-
if grid[i][j] != '#' {
52+
// To avoid double counting, we only look at half the points per space;
53+
halfDistances := [4][2]int{
54+
{2, 0},
55+
{1, 1},
56+
{0, 2},
57+
{-1, 1},
58+
}
59+
60+
picoSecondsToSave := 100
61+
if isUsingExample {
62+
picoSecondsToSave = 40 // Expect 2 as the output
63+
}
64+
65+
for i := 0; i < len(grid); i++ {
66+
for j := 0; j < len(grid[i]); j++ {
67+
if distancesToPoint[i][j] == -1 {
5268
continue
53-
// // Go 4 directions and only valid if it is a #
54-
// nextMustBeHash = true
5569
}
5670

57-
for _, dir := range directions {
71+
for _, dir := range halfDistances {
5872
newI := i + dir[0]
5973
newJ := j + dir[1]
6074

6175
// Out of bounds checks
62-
if newI < 0 || newJ < 0 || newI > len(grid)-1 || newJ > len(grid[i])-1 {
76+
if newI < 0 || newJ < 0 || newI > len(grid)-1 || newJ > len(grid[0])-1 {
6377
continue
6478
}
6579

66-
// Can't finish on an out of bounds tile!
6780
if grid[newI][newJ] == '#' {
6881
continue
6982
}
7083

71-
if nextMustBeHash && grid[newI][newJ] != '#' {
72-
// Would not be a cheat, so skip!
73-
continue
84+
if int(math.Abs(float64(distancesToPoint[i][j]-distancesToPoint[newI][newJ]))) >= picoSecondsToSave+2 {
85+
count++
7486
}
87+
}
7588

76-
newGrid := cloneGrid(grid)
77-
newGrid[i][j] = '.'
78-
if grid[newI][newJ] != 'E' && grid[newI][newJ] != 'S' {
79-
newGrid[newI][newJ] = '.'
80-
}
89+
}
90+
}
91+
92+
sharedstruct.PrintOutput(sharedstruct.Output{
93+
Day: 20,
94+
Part: 1,
95+
Value: count,
96+
})
97+
}
98+
99+
func partTwo(contents []string) {
100+
grid := parseToGrid(contents)
101+
distancesToPoint := make([][]int, len(grid))
102+
for i := 0; i < len(grid); i++ {
103+
distancesToPoint[i] = make([]int, len(grid[i]))
104+
for j := 0; j < len(grid[i]); j++ {
105+
distancesToPoint[i][j] = -1
106+
}
107+
}
108+
109+
start, end := findStartAndEnd(contents)
110+
distancesToPoint[start[0]][start[1]] = 0
111+
bfsDetermineDistances(grid, start, end, &distancesToPoint)
81112

82-
seconds := bfs(newGrid, start, end)
83-
// Took 100s, now takes 55s. So saved 100-55=45 seconds
84-
savedSeconds := numSeconds - seconds
85-
if savedSeconds > 0 {
86-
if savedSeconds == 64 {
87-
fmt.Println()
88-
displayGrid(newGrid)
89-
fmt.Println("debug")
113+
count := 0
114+
115+
picoSecondsToSave := 100
116+
117+
visited := make(map[[2][2]int]bool, 0) // start and end
118+
119+
for i := 0; i < len(grid); i++ {
120+
for j := 0; j < len(grid[i]); j++ {
121+
for radius := 2; radius < 21; radius++ {
122+
for di := 0; di < radius+1; di++ {
123+
dj := radius - di
124+
for _, dir := range [4][2]int{{i + di, j + dj}, {i + di, j - dj}, {i - di, j + dj}, {i - di, j - dj}} {
125+
newI := dir[0]
126+
newJ := dir[1]
127+
if _, ok := visited[[2][2]int{{i, j}, {newI, newJ}}]; ok {
128+
continue
129+
}
130+
131+
visited[[2][2]int{{i, j}, {newI, newJ}}] = true
132+
133+
// Out of bounds checks
134+
if newI < 0 || newJ < 0 || newI > len(grid)-1 || newJ > len(grid[0])-1 {
135+
continue
136+
}
137+
138+
if grid[newI][newJ] == '#' {
139+
continue
140+
}
141+
142+
if distancesToPoint[i][j]-distancesToPoint[newI][newJ] >= picoSecondsToSave+radius {
143+
count++
144+
}
90145
}
91-
savedSecondsCount[savedSeconds]++
92146
}
93147
}
148+
94149
}
95150
}
96-
97151
sharedstruct.PrintOutput(sharedstruct.Output{
98152
Day: 20,
99-
Part: 1,
100-
Value: savedSecondsCount,
153+
Part: 2,
154+
Value: count,
101155
})
102156
}
103157

@@ -113,10 +167,8 @@ type queueStruct struct {
113167
steps int
114168
}
115169

116-
func bfs(grid [][]byte, start [2]int, end [2]int) int {
117-
// BFS now!
170+
func bfsDetermineDistances(grid [][]byte, start [2]int, end [2]int, distancesToPoint *[][]int) int {
118171
queue := make([]queueStruct, 0)
119-
visited := make(map[[2]int]bool)
120172

121173
queue = append(queue, queueStruct{
122174
pos: start,
@@ -132,18 +184,6 @@ func bfs(grid [][]byte, start [2]int, end [2]int) int {
132184
// Grab the next element in queue
133185
element, queue = queue[0], queue[1:]
134186

135-
// if visited, skip
136-
_, ok := visited[element.pos]
137-
if ok {
138-
continue
139-
}
140-
141-
if element.pos == end {
142-
return element.steps
143-
}
144-
145-
visited[element.pos] = true
146-
147187
for _, dir := range directions {
148188
newI := element.pos[0] + dir[0]
149189
newJ := element.pos[1] + dir[1]
@@ -157,6 +197,12 @@ func bfs(grid [][]byte, start [2]int, end [2]int) int {
157197
continue
158198
}
159199

200+
if (*distancesToPoint)[newI][newJ] != -1 {
201+
continue
202+
}
203+
204+
(*distancesToPoint)[newI][newJ] = (*distancesToPoint)[element.pos[0]][element.pos[1]] + 1
205+
160206
queue = append(queue, queueStruct{
161207
pos: [2]int{newI, newJ},
162208
steps: element.steps + 1,
@@ -167,14 +213,6 @@ func bfs(grid [][]byte, start [2]int, end [2]int) int {
167213
return -1
168214
}
169215

170-
func partTwo(contents []string) {
171-
sharedstruct.PrintOutput(sharedstruct.Output{
172-
Day: 20,
173-
Part: 2,
174-
Value: "TODO",
175-
})
176-
}
177-
178216
func findStartAndEnd(contents []string) ([2]int, [2]int) {
179217
var start, end [2]int
180218
foundCount := 0

0 commit comments

Comments
 (0)