/
day17.py
162 lines (124 loc) · 4.17 KB
/
day17.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
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
import re
from collections import deque
from PIL import Image, ImageDraw
def load_grid(filename):
pattern = re.compile(r"(x|y)=(\d+), [x|y]=(\d+)..(\d+)")
grid = dict()
for line in open(filename).readlines():
match = pattern.match(line)
if match[1] == "x":
x = int(match[2])
for y in range(int(match[3]), int(match[4])+1):
grid[(x, y)] = '#'
else:
y = int(match[2])
for x in range(int(match[3]), int(match[4])+1):
grid[(x, y)] = '#'
return grid
def print_grid(clay, water):
min_x = min(clay, key=lambda g: g[0])[0]
max_x = max(clay, key=lambda g: g[0])[0]
min_y = min(clay, key=lambda g: g[1])[1]
max_y = max(clay, key=lambda g: g[1])[1]
print(min_x, max_x, min_y, max_y)
for y in range(min_y-1, max_y+2):
line = ""
for x in range(min_x-1, max_x+2):
if (x, y) in clay:
line += "\033[1;37;47m█\033[0m"
elif (x, y) in water:
w = water[x, y]
if w == '~':
line += "\033[1;34;40m▓\033[0m"
else:
line += "\033[1;34;40m░\033[0m"
else:
line += "."
print(line)
def render_grid(clay, water):
min_x = min(clay, key=lambda g: g[0])[0]
max_x = max(clay, key=lambda g: g[0])[0]
min_y = min(clay, key=lambda g: g[1])[1]
max_y = max(clay, key=lambda g: g[1])[1]
w, h = max_x - min_x, max_y - min_y
img = Image.new('RGBA', (w, h), (255, 255, 255, 255))
draw = ImageDraw.Draw(img)
for y in range(min_y, max_y+1):
for x in range(min_x, max_x+1):
dp = (x-min_x, y-min_y)
if (x, y) in clay:
draw.point(dp, (20, 20, 10, 255))
elif (x, y) in water:
w = water[x, y]
if w == '~':
draw.point(dp, (20, 20, 255, 255))
else:
draw.point(dp, (200, 200, 255, 255))
return img
# there is lot of optimization oportunities here
# flows could be refactored to one function with direction parameter
# using dicts for points should be changed to arrays
def start_flow(clay, water, x, y):
max_y = max(clay, key=lambda g: g[1])[1]
pos = (x, y)
while True:
water[pos] = "|"
nextpos = (pos[0], pos[1]+1)
if nextpos[1] > max_y:
return []
if nextpos in water and water[nextpos] == "|":
return []
if nextpos in clay or nextpos in water and water[nextpos] == "~":
break
pos = nextpos
touchpoint = pos
# flow left
left_edge = None
left_drip = None
while True:
water[pos] = "|"
posleft = (pos[0]-1, pos[1])
posdown = (pos[0], pos[1]+1)
if not(posdown in clay or posdown in water and water[posdown] == "~"):
left_drip = pos
break
if posleft in clay:
left_edge = pos
break
pos = posleft
pos = touchpoint
# flow right
right_edge = None
right_drip = None
while True:
water[pos] = "|"
posright = (pos[0]+1, pos[1])
posdown = (pos[0], pos[1]+1)
if not (posdown in clay or posdown in water and water[posdown] == "~"):
right_drip = pos
break
if posright in clay:
right_edge = pos
break
pos = posright
if left_edge and right_edge:
for x in range(left_edge[0], right_edge[0]+1):
water[x, left_edge[1]] = "~"
return [(touchpoint[0], touchpoint[1]-1)]
return [left_drip, right_drip]
clay = load_grid("day17.txt")
water = dict()
dripstarts = deque()
dripstarts.append((500, 0))
while dripstarts:
curflow = dripstarts.popleft()
if curflow:
overlows = start_flow(clay, water, *curflow)
dripstarts.extend(overlows)
min_y = min(clay, key=lambda g: g[1])[1]
print("solution 1:", len(list(filter(lambda w: w[1] >= min_y, water))))
print("solution 2:", len(
list(filter(lambda key: key[1] >= min_y and water[key] == "~", water))))
image = render_grid(clay, water)
image.show()
image.close()