#advent of code 2024
#day 20
#shamelessly copypasted previous pathfinding and input parsing
#except it needed much adjustments because it's not really pathfinding
#basically: calculate map of distances between each point with djikstra
#since the path never branches, you can use these distances 
#instead of recalculating the path after each cheat
#cheat 

grid = {}; 
xMin, yMin, xMax, yMax = 0,0,0,0; #could get rid of it but w/e
dirs = [(1,0),(0,1),(-1,0),(0,-1)]; #east, south, west, north

f = open("20.in","r");
for y,l in enumerate(f):
	yMax = max(y,yMax);
	for x,c in enumerate(l.strip()):
		if c == "S": 
			start = (x,y);
			c = "."
		elif c == "E": 
			end = (x,y);
			c = "."
		grid[(x,y)]=c;
		xMax = max(xMax,x);
f.close();

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

def djikstra(startpos,endpos):
	queue = [];
	DistanceMap = {};
	queue = [(startpos,0)];
	while queue:
		coords,dist = queue.pop();
		if coords in DistanceMap: continue;
		DistanceMap[coords] = min(DistanceMap.get(coords,float('inf')),dist);
		for NextPos in getAdjacent(coords):
			queue.append((NextPos,dist+1));
	return DistanceMap;

def cheatAdjacent(coordinates,secs):
	adj = set();
	px,py = coordinates;
	for X in range(secs+1):
		for Y in range(secs+1-X):
			adj.add((px+X*1,py+Y*1));
			adj.add((px+X*(-1),py+Y*(-1)));
			adj.add((px+X*(1),py+Y*(-1)));
			adj.add((px+X*(-1),py+Y*(1)));
	return adj;

PathDistances = djikstra(start,end);
part1 = 0;
part2 = 0;
for position in PathDistances:
	d1 = PathDistances.get(position,-1); #negative value if there's no match
	CheatedSteps = cheatAdjacent(position,20);
	for ch in CheatedSteps:
		d2 = PathDistances.get(ch,-1); #negative value if there's no match
		if d2 == -1: continue; #if the step isn't in the PathDistances, then it's not valid
		manhattan = abs(ch[0]-position[0]) + abs(ch[1]-position[1])
		ScoreDifference = d2-d1 - manhattan
		if ScoreDifference >= 100: #from description, doesn't work for example
			part2 += 1;
			part1 += 1*(manhattan <= 2);

print("part 1 =", part1);
print("part 2 =", part2); 
#grid print for reference/debugging
#for y in range(yMax+1):
#	for x in range(xMax+1):
#		c = grid[(x,y)];
#		if (x,y) == start: c = "S";
#		elif (x,y) == end: c = "E";		
#		print(c, end="");
#	print();