-
Notifications
You must be signed in to change notification settings - Fork 0
/
22_SandSlabs.py
91 lines (73 loc) · 2.6 KB
/
22_SandSlabs.py
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
import collections, re
from lib import *
def xy_intersect(c1: "Cube", c2: "Cube"):
return c1.x1 <= c2.x2 and c1.x2 >= c2.x1 and c1.y1 <= c2.y2 and c1.y2 >= c2.y1
class Cube:
def __init__(self, x1,y1,z1,x2,y2,z2) -> None:
self.x1=x1
self.y1=y1
self.z1=z1
self.x2=x2
self.y2=y2
self.z2=z2
def calc_intersects(self, C: list["Cube"]):
self.intersects = set([a for a in C if a != self and xy_intersect(self, a)])
intersects: set["Cube"] = set()
# parse input to cubes
inp = get_input()
C: list[Cube] = [Cube(*[int(a) for a in re.split(r",|~", l)]) for l in inp]
for c in C:
c.calc_intersects(C)
def fall(C: list[Cube]):
while True:
has_fallen = False
for c in C:
f = 0
for c2 in c.intersects:
if c.z1 >= c2.z2+1:
if f < c2.z2:
f = c2.z2
d = c.z1-f-1 # distance this cube can fall down
if d > 0:
c.z1-=d
c.z2-=d
has_fallen = True
if not has_fallen:
break # loop until no brick falls anymore for one complete iteration
# simulate fall, so that support can be calculated more easily in the next step
fall(C)
# Generate support structure graph
G: dict[Cube, set[Cube]] = {} # maps cube -> is supported by
IG = collections.defaultdict[Cube, set[Cube]](set) # maps cube -> is support for
for c in C:
# find all cubes that can possibly support this cube, because they overlap on x,y and are underneath
p = [a for a in c.intersects if a != c and xy_intersect(c, a) and c.z1 > a.z2]
support = set()
if len(p):
max_s = max(p, key=lambda x: x.z2)
for a in p:
if a.z2 == max_s.z2: # filters out only the cubes that directly supports this cube
support.add(a)
# save support structure to graph
G[c] = support
for s in support:
IG[s].add(c)
p1=0
p2=0
# start at each cube in the graph and count how many other cubes are influenced if that cube is disintegrated
for c in C:
Q = collections.deque([c])
F = set() # store all cubes that will fall in this case
cnt = 0
while Q:
current_cube = Q.popleft()
F.add(current_cube)
for cube_is_support_for in IG[current_cube]:
# check if only bricks from the F set support the cube_is_support_for
if all(a in F for a in G[cube_is_support_for]):
Q.append(cube_is_support_for)
cnt += 1
p1+=1 if cnt == 0 else 0
p2+=cnt
print(p1)
print(p2)