#advent of code 2024
#day 16
#version 2 - slightly cleaned up
#don't know anymore, can't explain - keeping the unrevised version because it's hilariously dogshit
#part 1: simple shortest path search
#part 2: keep the path searching function running until all paths with distance equal to the shortest path are registered
#keep track of distance for each node, kinda like djikstra, distance to each node is stored in a dictionary
#with only exception that it stores all of the possible 
#in short: linked list, in format: node_1:set_of_previous_nodes, previous nodes have shortest possible path to that node
#keep a map of previous steps, that is Position_now:set of positions that could be used to reach 
#I also commented out a check to prevent going backwards (take step north, then take step south) 
#but I guess that was taken care of during other checks like how big is the distance so it didnt matter
#the entries in queues with distance greater than registered shortest path are discarded
#the check is repeated (probably unnecessarily) before queuepush
#my other issue: there could be more than 1 directions from which I could reach the E
#while I registered all of them, durign testing I used only one of them
#turns out there weren't multiple ends (all valid paths reach E from the same direction)
#sidenote: i think i solved that earlier, because I was getting similar values, but I didn't bother to check

#assumptions: 
#only 1 starting position
#i think the code will work for multiple ends (E) as well, as long as the puzzle wants the shortest path to the closest end

import heapq

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("16.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,0);
			c = "."
		grid[(x,y)]=c;
		xMax = max(xMax,x);
f.close();

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

def pathfinding(startingpos):
	ends = set(); #max 4, coordinates of E but coming from each direction
	BigNumber = xMax*yMax*100000000000; #used to initialize Shortest Path to have something to compare with
	ShortestPath = BigNumber;
	pathmap,pathdis = {},{};
	queue = [];
	heapq.heappush(queue,(0,startingpos));
	pathmap[startingpos] = set();
	while queue:
		distance, coords = heapq.heappop(queue);
		if distance > ShortestPath: continue;
		px,py,pd = coords;
		if grid.get((px,py),"#") == "E":
			ShortestPath = min(ShortestPath,distance); #this should be updated only once
			if distance == ShortestPath: 
				ends.add(coords); #always the same E, just from different direction
		NextValid = getAdjacent((px,py,pd));
		for NV in NextValid: #for each valid adjacent node (valid here means it's not a wall)
			next_dist = distance+1+1000*(NV[2]!=pd);
			prev_dist = pathdis.get(NV,BigNumber);
			if next_dist > prev_dist: 
				continue;
			if next_dist < prev_dist: 
				pathmap[NV] = set(); #reset the set of positions with shortest path to it
				pathdis[NV] = next_dist; #update the shortest path to node NV
			pathmap[NV].add(coords);
			heapq.heappush(queue,(next_dist,NV));
	return ShortestPath, pathmap, ends;

def FindSpots(startpos,CurrentNode,pathmap):
	validpaths = set();
	validpaths.add((CurrentNode[0],CurrentNode[1]));
	if CurrentNode == startpos:
		return validpaths;
	NextPositions = pathmap[CurrentNode]; #read the set of nodes that connected to this node
	for np in NextPositions:
		validpaths.update(FindSpots(startpos,np,pathmap));
	return validpaths;

ValidTiles = set(); #tiles that are on one of the best paths through the maze
part1, PathMap, PathEnds = pathfinding(start); 
for EndPosition in PathEnds:
	ValidTiles.update(FindSpots(start,EndPosition,PathMap));
part2 = len(ValidTiles);
''' #map print
for y in range(yMax+1):
	for x in range(xMax+1):
		c = grid[(x,y)];
		if (x,y) in ValidTiles: c = str("O");
		print(c, end="");
	print(); #'''
print("part 1 =", part1);
print("part 2 =", part2);