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
|
#!/usr/bin/env python3
# import numpy as np
from functools import reduce
from re import findall
from copy import deepcopy
import sys
# filename = "in/day18.ref"
filename = "in/day18.pzl"
data = open(filename).read()
lines = [line for line in data.rstrip('\n').split('\n')]
# print(lines)
D = dict()
for line in lines:
x,y,z = [int(i) for i in line.split(',')]
D[(x,y,z)] = 1
# print(D)
side_len = 0
for x,y,z in D.keys():
side_len = max(side_len, x, y, z)
side_len += 1
# print(side_len)
res1 = 0
for x,y,z in D.keys():
for dx,dy,dz in [(1,0,0), (-1,0,0), (0,1,0), (0,-1,0), (0,0,1), (0,0,-1)]:
if (x+dx,y+dy,z+dz) not in D:
res1 += 1
def bfs(visited):
while True:
start_len = len(visited)
new_visited = set()
for x,y,z in visited:
for dx,dy,dz in [(1,0,0), (-1,0,0), (0,1,0), (0,-1,0), (0,0,1), (0,0,-1)]:
if ((x+dx,y+dy,z+dz) not in visited) and \
-1 <= x+dx < side_len+1 and \
-1 <= y+dy < side_len+1 and \
-1 <= z+dz < side_len+1 and \
((x+dx,y+dy,z+dz) not in D):
new_visited.add((x+dx,y+dy,z+dz))
visited = visited.union(new_visited)
if len(visited) == start_len:
return visited
# O(n**3)
E = set()
for x in range(-1, side_len+1):
for y in range(-1, side_len+1):
for z in range(-1, side_len+1):
if max(x,y,z) == side_len or min(x,y,z) == -1:
E.add((x,y,z))
E = bfs(E)
# print(E)
res2 = 0
for x,y,z in D.keys():
for dx,dy,dz in [(1,0,0), (-1,0,0), (0,1,0), (0,-1,0), (0,0,1), (0,0,-1)]:
if (x+dx,y+dy,z+dz) in E:
res2 += 1
print('res1:', res1)
print('res2:', res2)
|
