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