-
Notifications
You must be signed in to change notification settings - Fork 0
/
day18_2.groovy
123 lines (108 loc) · 2.5 KB
/
day18_2.groovy
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
def sampleInput = '''5,4
4,2
4,5
3,0
2,1
6,3
2,4
1,5
0,6
3,3
2,6
5,1
1,2
5,5
2,5
6,5
1,4
0,4
6,4
1,1
6,1
1,0
0,5
1,6
2,0'''
static def neighbours(int grid, def node) {
[
getNext(node, [0, 1]),
getNext(node, [1, 0]),
getNext(node, [0, -1]),
getNext(node, [-1, 0]),
].findAll { inMap(grid, it) }
}
static def getNext(def pos, def dir) {
[pos[0] + dir[0], pos[1] + dir[1]]
}
static boolean inMap(int grid, def pos) {
pos[0] >= 0 && pos[0] < grid &&
pos[1] >= 0 && pos[1] < grid
}
static def find(sets, x) {
while (sets[x][1] != x) {
def parent = sets[x][1]
sets[x][1] = sets[sets[x][1]][1]
x = parent
}
x
}
static void union(sets, x, y) {
x = find(sets, x)
y = find(sets, y)
if (x == y) return
if (sets[x][0] < sets[y][0]) {
def t = y
y = x
x = t
}
sets[y][1] = x
if (sets[x][0] == sets[y][0]) {
sets[x][0]++
}
}
static def createInitialDisjointSet(List<List<Integer>> points, int grid) {
def sets = [:]
grid.times { i ->
grid.times { j ->
def p = [i, j]
if (!points.contains(p) && !sets.containsKey(p)) {
def visited = bfs(points, grid, p)
visited.each {
sets[it] = [0, it]
}
visited.inject(visited[0]) { prev, e ->
union(sets, prev, e)
e
}
}
}
}
sets
}
static def bfs(List<List<Integer>> points, int grid, def start) {
def queue = [start] as Queue
def visited = [start]
while (!queue.isEmpty()) {
def el = queue.poll()
neighbours(grid, el).findAll { !points.contains(it) && !visited.contains(it) }.each {
visited.add(it)
queue.add(it)
}
}
visited
}
static String solve(List<String> input, int steps = 1024, int grid = 71) {
def points = input.collect { it.split(',').collect { it as int } }
def sets = createInitialDisjointSet(points, grid)
def pointsSoFar = points as Set
points.reversed().find {
sets[it] = [0, it]
neighbours(grid, it).findAll { n -> !pointsSoFar.contains(n) }.each { n ->
union(sets, it, n)
}
pointsSoFar.removeElement(it)
find(sets, [0,0]) == find(sets, [grid-1, grid-1])
}.join(',')
}
assert '6,1' == solve(sampleInput.split('\n') as List, 12, 7)
println solve(new File('input/day18.txt').readLines())