#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);