Spaces:
Running
Running
File size: 2,641 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 88 89 90 |
from collections import defaultdict
from heapq import heappush, heappop
def parse_maze(filename):
with open(filename) as f:
maze = [list(line.strip()) for line in f]
# Find start and end
start = end = None
for y in range(len(maze)):
for x in range(len(maze[0])):
if maze[y][x] == 'S':
start = (x, y)
elif maze[y][x] == 'E':
end = (x, y)
return maze, start, end
def get_neighbors(pos, direction, maze):
x, y = pos
moves = []
# Forward
dx, dy = direction
new_x, new_y = x + dx, y + dy
if 0 <= new_x < len(maze[0]) and 0 <= new_y < len(maze) and maze[new_y][new_x] != '#':
moves.append(((new_x, new_y), direction, 1))
# Turn left
new_dir = (-dy, dx)
moves.append((pos, new_dir, 1000))
# Turn right
new_dir = (dy, -dx)
moves.append((pos, new_dir, 1000))
return moves
def find_min_score(maze, start, end):
# Direction: (dx, dy)
# Start facing east
initial_dir = (1, 0)
# Priority queue: (score, position, direction)
queue = [(0, start, initial_dir)]
seen = set()
scores = defaultdict(lambda: float('inf'))
scores[(start, initial_dir)] = 0
while queue:
score, pos, direction = heappop(queue)
if pos == end:
return score
if (pos, direction) in seen:
continue
seen.add((pos, direction))
for new_pos, new_dir, cost in get_neighbors(pos, direction, maze):
new_score = score + cost
if new_score < scores[(new_pos, new_dir)]:
scores[(new_pos, new_dir)] = new_score
heappush(queue, (new_score, new_pos, new_dir))
return float('inf')
def find_optimal_paths(maze, start, end, min_score):
optimal_tiles = set()
initial_dir = (1, 0)
def dfs(pos, direction, score, path):
if score > min_score:
return
if pos == end and score == min_score:
optimal_tiles.update(path)
return
for new_pos, new_dir, cost in get_neighbors(pos, direction, maze):
if new_pos not in path or new_pos == end: # Allow revisiting end
dfs(new_pos, new_dir, score + cost, path | {new_pos})
dfs(start, initial_dir, 0, {start})
return len(optimal_tiles)
# Solve both parts
maze, start, end = parse_maze("input.txt")
min_score = find_min_score(maze, start, end)
print(str(min_score))
optimal_tiles = find_optimal_paths(maze, start, end, min_score)
print(str(optimal_tiles)) |