Spaces:
Running
Running
File size: 2,309 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 |
def parse_input(file):
with open(file, 'r') as f:
return [list(line.strip()) for line in f.readlines()]
def get_start_position(grid):
for y in range(len(grid)):
for x in range(len(grid[0])):
if grid[y][x] == '^':
return (x, y, 0) # x, y, direction (0=up, 1=right, 2=down, 3=left)
return None
def is_valid_position(x, y, grid):
return 0 <= y < len(grid) and 0 <= x < len(grid[0])
def get_next_position(x, y, direction):
if direction == 0: # up
return (x, y-1)
elif direction == 1: # right
return (x+1, y)
elif direction == 2: # down
return (x, y+1)
else: # left
return (x-1, y)
def simulate_path(grid, start_pos=None, added_obstacle=None):
if start_pos is None:
start_pos = get_start_position(grid)
x, y, direction = start_pos
visited = set([(x, y)])
while True:
next_x, next_y = get_next_position(x, y, direction)
# Check if out of bounds
if not is_valid_position(next_x, next_y, grid):
return visited, False
# Check if obstacle ahead (including added obstacle)
if (grid[next_y][next_x] == '#' or (next_x, next_y) == added_obstacle):
direction = (direction + 1) % 4
else:
x, y = next_x, next_y
visited.add((x, y))
# Check for loop
if len(visited) > len(grid) * len(grid[0]) * 4:
return visited, True
def solve_part1(grid):
visited, _ = simulate_path(grid)
return len(visited)
def solve_part2(grid):
start_pos = get_start_position(grid)
loop_positions = 0
for y in range(len(grid)):
for x in range(len(grid[0])):
# Skip if not empty space or start position
if grid[y][x] != '.' or (x, y) == (start_pos[0], start_pos[1]):
continue
# Try adding obstacle here
_, creates_loop = simulate_path(grid, start_pos, (x, y))
if creates_loop:
loop_positions += 1
return loop_positions
def main():
grid = parse_input("input.txt")
print(str(solve_part1(grid)))
print(str(solve_part2(grid)))
if __name__ == "__main__":
main() |