1 files changed, 102 insertions, 0 deletions
diff --git a/2024/aoc2024-d16-wash_attempt.py b/2024/aoc2024-d16-wash_attempt.py
new file mode 100644
index 0000000..4d70b48
--- /dev/null
+++ b/2024/aoc2024-d16-wash_attempt.py
@@ -0,0 +1,102 @@
+#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);