#advent of code 2024
#day 16
#version 1 - not 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

import heapq

grid = {}; 
xMin, yMin, xMax, yMax = 0,0,0,0; #just for printout
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);
			c = "."
		grid[(x,y)]=c;
		xMax = max(xMax,x);
f.close();

'''
for y in range(yMax+1):
	for x in range(xMax+1):
		print(grid[(x,y)], end="");
	print(); #'''
	
#print(start);

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;

BigNumber = xMax*yMax*100000000000;

def pathfinding(startingpos):
	ends = set();
	visited = set();
	x0,y0 = startingpos;
	queue = [];
	heapq.heappush(queue,(0,(x0,y0,0)));
	ShortestPath = BigNumber;
	pathmap = {};
	pathdis = {};
	pathmap[(x0,y0,0)] = set();
	
	while queue:
		distance, coords = heapq.heappop(queue);
		#if coords in visited: continue;
		if distance > ShortestPath: continue;
		visited.add(coords);
		px,py,pd = coords;
		
		#pathmap[(coords,prevs)] = min(distance, pathmap.get((coords,prevs),float('inf'))); 
		CurrentTile = grid.get((px,py),"#");
		if CurrentTile == "E":
			ShortestPath = min(ShortestPath,distance);
			if distance == ShortestPath:
				ends.add(coords);
				
		#else:
		NextValid = getAdjacent((px,py,pd));
		for NV in NextValid:
			#print("NV", distance+1+1000*(NV[2]!=pd),NV);
			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();
				pathdis[NV] = next_dist;
			pathmap[NV].add(coords);
			#if NV[2] == (pd+2)%4: continue;
			heapq.heappush(queue,(distance+1+1000*(NV[2]!=pd),NV));
				
	return ShortestPath, pathmap, pathdis, ends;


part1, PathMap,PathDis, PathEnds = pathfinding(start);
part2 = len(PathMap);
newtotal = set();
#for shit in tv:
#	shit1,shit2,shit2
print("part 1 =", part1);

#print(PathMap);
for pm in PathMap:
	if len(PathMap[pm]) > 1:
		print(pm, PathMap[pm]);
#input();

#print(PathDis);
#input();
#print(PathEnds);

def FindSpots(startpos,end,pathmap,pathdis,prevpaths):
	#sx,sy,_ = 
	validpaths = set();
	print(end);
	#for end in endpos:
	#queue = [end];
	#scorereversed = 0 + pathdis[end];
	CurrentPosition = end;
	validpaths.add(CurrentPosition);
	#while queue:
	#	x,y,d = queue.pop();
	if end == startpos:
		return validpaths;
	#x,y,d = end;
	NextPositions = pathmap[end];
	for np in NextPositions:
		validpaths.update(FindSpots(startpos,np,pathmap,pathdis,validpaths.copy()));
	
	return validpaths;
	
print("FINSPOTS");
FirstEnd = PathEnds.pop();
testing = FindSpots(start,FirstEnd,PathMap,PathDis,set());
print("testing");
print(testing);
print(len(testing));



storeshit = set();

for t in testing:
	tx,ty,td = t;
	storeshit.add((tx,ty));


for y in range(yMax+1):
	for x in range(xMax+1):
		c = grid[(x,y)];
		#if (x,y) in tv: 
		#	c = "O";
		counter = 0;
		for ind in range(4):
			if (x,y,ind) in testing: counter += 1;
		if counter != 0: c = str(counter);	
				##c = "O";
				#break;#'''
		print(c, end="");
	print();

print("part 1 =", part1);
print("part 2 =", len(storeshit));