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()