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
|
package main
import (
"fmt"
"os"
"strings"
)
func FileRead(path string) string {
file, err := os.ReadFile(path)
if err != nil {
fmt.Println("Couldn't Read file: ", err)
}
return string(file)
}
type Point struct {
x int
y int
}
func (p Point) inBounds(w, h int) bool {
return p.x >= 0 && p.x < w && p.y >= 0 && p.y < h
}
type Grid = [][]byte
func bfs(grid Grid, start Point, uniq bool) int {
cnt := 0
w, h := len(grid), len(grid[0])
var queue []Point
visited := make(map[Point]bool)
visited[start] = true
queue = append(queue, start)
dx := []int{1, -1, 0, 0} // down, up, right, left
dy := []int{0, 0, 1, -1}
for len(queue) > 0 {
curPoint := queue[0]
queue = queue[1:] // pop from front
for i := 0; i < 4; i++ {
nx := curPoint.x + dx[i]
ny := curPoint.y + dy[i]
newPoint := Point{x: nx, y: ny}
if uniq {
if newPoint.inBounds(w, h) && !visited[newPoint] && int(grid[newPoint.x][newPoint.y]) == int(grid[curPoint.x][curPoint.y])+1 {
visited[newPoint] = true
queue = append(queue, newPoint)
if grid[newPoint.x][newPoint.y] == byte('9') {
cnt++
}
}
} else {
if newPoint.inBounds(w, h) && int(grid[newPoint.x][newPoint.y]) == int(grid[curPoint.x][curPoint.y])+1 {
queue = append(queue, newPoint)
if grid[newPoint.x][newPoint.y] == byte('9') {
cnt++
}
}
}
}
}
return cnt
}
// String returns a string representation of the grid
func printGrid(g Grid) {
for _, row := range g {
for _, r := range row {
fmt.Printf("%v ", string(r))
}
fmt.Println()
}
}
func parseInput(data string) Grid {
var grid Grid
for _, line := range strings.Split(data, "\n") {
if len(line) > 0 {
row := []byte(line)
grid = append(grid, row)
}
}
return grid
}
func solve_part_one(data string) int {
grid := parseInput(data)
ans := 0
for i, row := range grid {
for j, byte := range row {
if byte == '0' {
ans += bfs(grid, Point{i, j}, true)
}
}
}
return ans
}
func solve_part_two(data string) int {
grid := parseInput(data)
ans := 0
for i, row := range grid {
for j, byte := range row {
if byte == '0' {
ans += bfs(grid, Point{i, j}, false)
}
}
}
return ans
}
func main() {
test := FileRead("../input/day10.test")
prod := FileRead("../input/day10.prod")
fmt.Println("Part_1 test: ", solve_part_one(test))
fmt.Println("Part_1 prod: ", solve_part_one(prod))
fmt.Println("Part_2 test: ", solve_part_two(test))
fmt.Println("Part_2 prod: ", solve_part_two(prod))
}
|
