1 files changed, 84 insertions, 0 deletions
diff --git a/2024/aoc2024-d20.py b/2024/aoc2024-d20.py
new file mode 100644
index 0000000..16ed3c4
--- /dev/null
+++ b/2024/aoc2024-d20.py
@@ -0,0 +1,84 @@
+#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();