Spaces:
Running
Running
File size: 1,786 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 |
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() |