#advent of code 2024
#day 18
#advent of gridbroot

import heapq

mygrid = {};
FallingBytes = [];
lim = 70 + 1;
bytelim = 1024;
for p in [(X,Y) for Y in range(lim) for X in range(lim)]: mygrid[p] = ".";
#myfile = "18.ex";
myfile = "18.in";
if myfile != "18.in": #if example
	lim = 7;
	bytelim = 12;

f = open(myfile,"r");
for counter,l in enumerate(f):
	bytex,bytey = [int(v) for v in l.strip().split(",")];
	FallingBytes.append((bytex,bytey));
	if counter < bytelim: mygrid[(bytex,bytey)] = "#";
f.close();

start = (0,0); 
end = (lim-1,lim-1);
dirs = [(1,0),(0,1),(-1,0),(0,-1)]; #east, south, west, north

def getAdjacent(grid,coordinates):
	adj = [];
	xp, yp = coordinates;
	for i,d in enumerate(dirs):
		dx,dy = d;
		if grid.get((xp+dx,yp+dy),"#") != "#":
			adj.append((xp+dx,yp+dy));
	return adj;

def shortestpath(grid,startpos):
	score = 0;
	visited = set();
	queue = [(0,startpos)];
	while queue:
		dist, pos = heapq.heappop(queue);
		if pos in visited: continue;
		visited.add(pos);
		if pos == end:
			score = dist;
			break;
		NextPositions = getAdjacent(grid,pos);
		for NP in NextPositions:
			heapq.heappush(queue,(dist+1,NP));
	return score

part1 = shortestpath(mygrid,start);
print("part 1 =",part1);
part2 = None;
for b_ind,b in enumerate(FallingBytes[bytelim:]):
	mygrid[b] = "#";
	path = shortestpath(mygrid,start);
	if path == 0: 
		part2 = f'{b[0]},{b[1]}';
		break;

print("part 2 =",part2);