added 2024 day 16, cleaned and not cleaned versions

2 files changed, 272 insertions, 0 deletions

diff --git a/2024/aoc2024-d16-dangerously_unwashed.py b/2024/aoc2024-d16-dangerously_unwashed.py
new file mode 100644
index 0000000..710a3e5
--- /dev/null
+++ b/2024/aoc2024-d16-dangerously_unwashed.py
@@ -0,0 +1,170 @@
+#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));
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);