Spaces:
Running
Running
File size: 2,461 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 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 |
from collections import deque
import copy
def read_input(file_path):
coordinates = []
with open(file_path, 'r') as f:
for line in f:
x, y = map(int, line.strip().split(','))
coordinates.append((x, y))
return coordinates
def create_grid(size):
return [[False for _ in range(size)] for _ in range(size)]
def is_valid(x, y, size):
return 0 <= x < size and 0 <= y < size
def get_neighbors(x, y, grid):
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
size = len(grid)
neighbors = []
for dx, dy in directions:
new_x, new_y = x + dx, y + dy
if is_valid(new_x, new_y, size) and not grid[new_y][new_x]:
neighbors.append((new_x, new_y))
return neighbors
def shortest_path(grid, start, end):
if grid[start[1]][start[0]] or grid[end[1]][end[0]]:
return float('inf')
queue = deque([(start[0], start[1], 0)])
visited = {start}
while queue:
x, y, dist = queue.popleft()
if (x, y) == end:
return dist
for next_x, next_y in get_neighbors(x, y, grid):
if (next_x, next_y) not in visited:
visited.add((next_x, next_y))
queue.append((next_x, next_y, dist + 1))
return float('inf')
def path_exists(grid, start, end):
if grid[start[1]][start[0]] or grid[end[1]][end[0]]:
return False
queue = deque([start])
visited = {start}
while queue:
x, y = queue.popleft()
if (x, y) == end:
return True
for next_x, next_y in get_neighbors(x, y, grid):
if (next_x, next_y) not in visited:
visited.add((next_x, next_y))
queue.append((next_x, next_y))
return False
def solve_part1(coordinates, size=71):
grid = create_grid(size)
for i in range(1024):
if i >= len(coordinates):
break
x, y = coordinates[i]
grid[y][x] = True
result = shortest_path(grid, (0, 0), (size-1, size-1))
return str(result)
def solve_part2(coordinates, size=71):
grid = create_grid(size)
for i, (x, y) in enumerate(coordinates):
grid[y][x] = True
if not path_exists(grid, (0, 0), (size-1, size-1)):
return f"{x},{y}"
return "No solution found"
coordinates = read_input("./input.txt")
print(solve_part1(coordinates))
print(solve_part2(coordinates)) |