Spaces:
Running
Running
| from collections import deque | |
| file = "input.txt" | |
| def parse_input(file): | |
| with open(file, 'r') as f: | |
| lines = f.readlines() | |
| return [tuple(map(int, line.strip().split(','))) for line in lines] | |
| def is_within_bounds(x, y, size): | |
| return 0 <= x < size and 0 <= y < size | |
| def bfs(grid, start, end, size): | |
| queue = deque([start]) | |
| visited = set([start]) | |
| steps = 0 | |
| while queue: | |
| for _ in range(len(queue)): | |
| x, y = queue.popleft() | |
| if (x, y) == end: | |
| return steps | |
| for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: | |
| nx, ny = x + dx, y + dy | |
| if is_within_bounds(nx, ny, size) and (nx, ny) not in visited and grid[ny][nx] == '.': | |
| visited.add((nx, ny)) | |
| queue.append((nx, ny)) | |
| steps += 1 | |
| return float('inf') # If no path is found | |
| def simulate_falling_bytes(byte_positions, size, max_bytes): | |
| grid = [['.' for _ in range(size)] for _ in range(size)] | |
| start = (0, 0) | |
| end = (size - 1, size - 1) | |
| # Part 1: Find the minimum steps after 1024 bytes | |
| for i, (x, y) in enumerate(byte_positions[:max_bytes]): | |
| grid[y][x] = '#' | |
| min_steps = bfs(grid, start, end, size) | |
| # Part 2: Find the first byte that blocks the path | |
| for i, (x, y) in enumerate(byte_positions): | |
| grid[y][x] = '#' | |
| if bfs(grid, start, end, size) == float('inf'): | |
| return min_steps, f"{x},{y}" | |
| return min_steps, None | |
| def main(): | |
| byte_positions = parse_input(file) | |
| size = 71 # The grid size is 71x71 | |
| max_bytes = 1024 | |
| min_steps, blocking_byte = simulate_falling_bytes(byte_positions, size, max_bytes) | |
| print(min_steps) | |
| print(blocking_byte) | |
| main() |