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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
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);
|
