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
|
#advent of code 2018
#day 17
#part 1 and part 2
#for me this is one of the most time consuming puzzles for this year
#I got too cocky because I remembered a similar puzzle during 2022 edition
#unfortunately 2018 day 17 was more tricky
#I made 3 attempts, each time starting from scratch
#first time I just scrambled something, but there was no way to calculate when to stop the algo
#so the water was extremely overflowing
#for second attempt I wrote 2 functions, one for flowing downwards, second for spreading
#I spent a whole day "improving" the spreading function so it behaves correctly, to no avail
#I figured out the logic of the puzzle, but I kept getting weird errors
#such as water bursting through walls or flowing upwards
#I was adding more and more if-elses, but they weren't fixing these bugs:
#they were merely delaying them - after filling in the water correctly, the bugs were popping up again
#third and final attempt was successful - I already learned the logic of the algorithm,
#I just needed to implement it in bug-free way
#on the other hand, I managed to get a pretty good runtime.
#Every now and then I was looking up a solution for clues from others
#one of which Michael Fogleman, probably my most common resource for learning AoC 2018
#while his code runs for almost a minute, mine just needs less than 0.05 secs
#it's really funny to "outperform" (in a way) someone whom you were constantly consulting for help
#one last thing I want to mention is that during the third attempt I kept getting wrong answer
#since I was only off by 3 and at the end there are only 3 waterfalls connecting to lowest point,
#I was convinced that I was calculating the solution for wrong range
#turns out I misunderstood the puzzle - you're supposed to calculate the amount of still
#and flowing water in range of highest wall point and the lowest wall point,
#while I kept calculating it in range from zero to lowest
#at least this time part2 was a freebee
import time;
f = open("input.txt",'r');
Testing = False;
#Testing = True;
if Testing:
f.close();
f = open("testinput.txt",'r');
def parse_input(line):
line = line.replace("x=","");
line = line.replace("y=","");
line = line.replace("..",",");
line = "[" + line + "]";
cords = eval(line);
return cords; #line coordinates: [x, y1, y2] or [y, x1, x2]
Xmax = 500; #rightmost X coordinate, just for printing the area
Xmin = 500; #leftmost X coordinate, just for printing the area
Ymax = 0; #lowest Y coordinate, needed for solution
Ymin2 = 2000; #highest Y coordinate, needed for solution
LinesX = [];
LinesY = [];
for l in f:
d = l[0]; #direction x or y
Cords = parse_input(l);
if d == "x":
Xmax = max(Cords[0], Xmax);
Xmin = min(Cords[0], Xmin);
Ymax = max(Cords[2], Ymax);
Ymin2 = min(Cords[1], Ymin2);
LinesX.append(Cords);
else:
Xmax = max(Cords[2], Xmax);
Xmin = min(Cords[1], Xmin);
Ymax = max(Cords[0], Ymax);
Ymin2 = min(Cords[0], Ymin2);
LinesY.append(Cords);
Xmax += 1;
Xmin -= 1;
Ymin = 0;
area = {};
#initialize input into the area
for l in LinesX:
x = l[0];
for y in range(l[1],l[2]+1):
area.update({(x,y):"#"});
for l in LinesY:
y = l[0];
for x in range(l[1],l[2]+1):
area.update({(x,y):"#"});
def wspread(cords, q):
r1 = 0;
r2 = 0;
x,y = cords;
while (area.get((x,y+1)," ") == "#" or area.get((x,y+1)," ") == "=") and area.get((x-1,y)," ") != "#":
r1 += 1;
x -= 1;
x,y = cords;
while (area.get((x,y+1)," ") == "#" or area.get((x,y+1)," ") == "=") and area.get((x+1,y)," ") != "#":
r2 += 1;
x += 1;
x,y = cords;
if area.get((x-r1-1,y)," ") == "#" and area.get((x+r2+1,y)," ") == "#":
for r in range(x-r1,x+r2+1):
area[(r,y)] = "=";
q.append((cords[0],cords[1]-1));
else:
for r in range(x-r1,x+r2+1):
area[(r,y)] = "|";
if area[(x-r1,y)] != "#" and area.get((x-r1,y+1)," ") == " ":
q.append((x-r1,y));
if area[(x+r2,y)] != "#" and area.get((x+r2,y+1)," ") == " ":
q.append((x+r2,y));
def wfall(cords, q):
x,y = cords;
while area.get((x,y+1)," ")==" " and y < Ymax:
area[(x,y+1)] = "|";
y += 1;
if area.get((x,y)," ")=="#" or area.get((x,y)," ")=="=":
q.append((x,y-1));
elif y < Ymax:
q.append((x,y));
t1 = time.time();
water = [(500,0)];
area.update({(500,0):"|"});
while water:
w = water.pop();
if area.get((w[0],w[1]+1)," ")==" ":
wfall(w, water);
else:
wspread(w, water);
part1 = 0;
part2 = 0;
for a in area:
part1 += 1*(area[a]=="|" or area[a]=="=")*(a[1] >= Ymin2);
part2 += 1*(area[a]=="=");
t2 = time.time();
print("part1 = ", part1);
print("part2 = ", part2);
print("runtime ", t2-t1);
|
