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
|
#advent of code 2024
#day 18
#advent of gridbroot
import heapq
mygrid = {};
FallingBytes = [];
lim = 70 + 1;
bytelim = 1024;
for p in [(X,Y) for Y in range(lim) for X in range(lim)]: mygrid[p] = ".";
#myfile = "18.ex";
myfile = "18.in";
if myfile != "18.in": #if example
lim = 7;
bytelim = 12;
f = open(myfile,"r");
for counter,l in enumerate(f):
bytex,bytey = [int(v) for v in l.strip().split(",")];
FallingBytes.append((bytex,bytey));
if counter < bytelim: mygrid[(bytex,bytey)] = "#";
f.close();
start = (0,0);
end = (lim-1,lim-1);
dirs = [(1,0),(0,1),(-1,0),(0,-1)]; #east, south, west, north
def getAdjacent(grid,coordinates):
adj = [];
xp, yp = coordinates;
for i,d in enumerate(dirs):
dx,dy = d;
if grid.get((xp+dx,yp+dy),"#") != "#":
adj.append((xp+dx,yp+dy));
return adj;
def shortestpath(grid,startpos):
score = 0;
visited = set();
queue = [(0,startpos)];
while queue:
dist, pos = heapq.heappop(queue);
if pos in visited: continue;
visited.add(pos);
if pos == end:
score = dist;
break;
NextPositions = getAdjacent(grid,pos);
for NP in NextPositions:
heapq.heappush(queue,(dist+1,NP));
return score
part1 = shortestpath(mygrid,start);
print("part 1 =",part1);
part2 = None;
for b_ind,b in enumerate(FallingBytes[bytelim:]):
mygrid[b] = "#";
path = shortestpath(mygrid,start);
if path == 0:
part2 = f'{b[0]},{b[1]}';
break;
print("part 2 =",part2);
|
