Spaces:
Running
Running
| 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)) |