Spaces:
Running
Running
File size: 1,240 Bytes
a4da721 |
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 |
import heapq
def solve():
file = "input.txt"
grid_size = 71
start = (0, 0)
end = (grid_size - 1, grid_size - 1)
with open(file) as f:
bytes = []
for line in f:
x, y = map(int, line.strip().split(','))
bytes.append((x, y))
def is_valid(x, y):
return 0 <= x < grid_size and 0 <= y < grid_size
def shortest_path(corrupted):
q = [(0, start)]
visited = set()
while q:
dist, (x, y) = heapq.heappop(q)
if (x, y) == end:
return dist
if (x, y) in visited or (x, y) in corrupted:
continue
visited.add((x, y))
for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nx, ny = x + dx, y + dy
if is_valid(nx, ny):
heapq.heappush(q, (dist + 1, (nx, ny)))
return -1
# Part 1
corrupted1 = set(bytes[:1024])
part1_result = shortest_path(corrupted1)
print(part1_result)
# Part 2
corrupted2 = set()
for i in range(len(bytes)):
corrupted2.add(bytes[i])
if shortest_path(corrupted2) == -1:
print(f"{bytes[i][0]},{bytes[i][1]}")
break
solve() |