1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
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();
|
