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
|
function getind(x,y,z)
return x + 30*y + 900*z
end
function getinds(s) return getind(s.x,s.y,s.z) end
function getxyz(ind)
local x, y, z
z = math.floor(ind / 900)
y = math.floor((ind - z*900)/30)
x = (ind - z*900 - y*30)
return x, y, z
end
function forall_neighbours(x,y,z, lambda)
lambda(x+1,y,z)
lambda(x-1,y,z)
lambda(x,y+1,z)
lambda(x,y-1,z)
lambda(x,y,z+1)
lambda(x,y,z-1)
end
function count(grid)
local cntr = 0
for i in pairs(grid) do
local s = 6
local x, y, z = getxyz(i)
forall_neighbours(x,y,z, function (x,y,z)
s = s - (grid[getind(x,y,z)] or 0)
end)
cntr = cntr + s
end
return cntr
end
function outside(n, min,max)
local x,y,z = n.x, n.y, n.z
if (x < min or x > max) and
(y < min or y > max) and
(z < min or z > max) then
return true
else return false end
end
local escapable = {}
function escape_bfs(grid, x,y,z, min,max)
local cnt = 0
local visited = {}
local queue = {}
table.insert(queue, {x=x,y=y,z=z, cnt=0})
while true do
local n = table.remove(queue, 1)
-- taxicab metric: max steps from corner to corner is sum of edge length
-- so anything that takes longer than that won't get out
if (n == nil) or n.cnt > 3*(max-min) then cnt = 0; break end
if (escapable[getinds(n)]) then
cnt = escapable[getinds(n)]
break
end
if (visited[getinds(n)]) or (grid[getinds(n)]) then
-- skip if visited or if not air
goto continue
end
visited[getinds(n)] = true
n.cnt = n.cnt + 1
-- not actually concerned with the exact number of steps
-- only care if cnt == 0 or not
-- ie. if there is a path to escape or not.
-- so adding works just to change a 0 to non zero if necessary.
cnt = cnt + n.cnt
if outside(n, min,max) then
break
end
forall_neighbours(n.x,n.y,n.z, function (x,y,z)
if not grid[getind(x,y,z)] and not visited[getind(x,y,z)] then -- only insert air
table.insert(queue, {x=x, y=y, z=z, cnt=n.cnt})
end
end)
::continue::
end
-- memoize
for k in pairs(visited) do
escapable[k] = cnt
end
return cnt ~= 0 and true or false
end
function escape(grid, min, max)
-- all points in the sphere are in [min,max] for x,y,z
-- do BFS for every point in the cube defined by [min,max]
-- if there is no way to get outside of [min,max], the air bubble
-- is unreachable.
for x=min,max do
for y=min,max do
for z=min,max do
if not grid[getind(x,y,z)] then
if not escape_bfs(grid, x,y,z, min,max) then
grid[getind(x,y,z)] = 1
end
end
end
end
end
-- now do count() again, but if a face borders an unreachable block, don't count it.
return count(grid)
end
local grid = {}
local f = assert(io.open(arg[1], "r"))
local min = math.huge
local max = -math.huge
for line in f:lines() do
for x,y,z in line:gmatch("(%d+),(%d+),(%d+)") do
x = tonumber(x)
y = tonumber(y)
z = tonumber(z)
grid[getind(x,y,z)] = 1
min = math.min(min, x, y, z)
max = math.max(max, x, y, z)
end
end
print("Part A:", count(grid))
print("Part B:", escape(grid, min, max))
|
