with open("24.txt") as f:
    data = f.read()

def get_board(data):
    return [
        list(line) for line in data.splitlines()
    ]

def get_blizzards(board):
    blizzards = dict()
    for row in range(len(board)):
        for col in range(len(board[0])):
            if board[row][col] in (">", "v", "<", "^"):
                blizzards[(row, col)] = {board[row][col]}
    return blizzards

def get_walls(board):
    return [
        (row, col)
        for row in range(len(board))
        for col in range(len(board[0]))
        if board[row][col] == "#"
    ]

blizzard_movement = {
    ">": (0, 1),
    "v": (1, 0),
    "<": (0, -1),
    "^": (-1, 0),
    " ": (0, 0),
}

def add_movement(x, y):
    a, b = x
    c, d = y
    return (a+c, b+d)

def get_answer(board, blizzards, walls):
    def is_within_board(pos):
        row, col = pos
        if row < 0 or row >= len(board):
            return False
        elif col < 0 or col >= len(board[0]):
            return False
        return True

    def within_board(pos):
        row, col = pos
        if row < 0 or row >= len(board):
            return (row % len(board), col)
        elif col < 0 or col >= len(board[0]):
            return (row, col % len(board[0]))
        return pos

    def move_blizzard(pos, blizzard):
        new_pos = within_board(add_movement(pos, blizzard_movement[blizzard]))
        if new_pos in walls:
            return move_blizzard(new_pos, blizzard)
        return new_pos

    def move_blizzards(blizzard_positions):
        new_blizzards = dict()
        for pos, blizzards in blizzard_positions.items():
            for blizzard in blizzards:
                new_pos = move_blizzard(pos, blizzard)
                if new_pos in new_blizzards:
                    new_blizzards[new_pos].add(blizzard)
                else:
                    new_blizzards[new_pos] = {blizzard}
        return new_blizzards

    def valid_moves(pos):
        for move in ">v<^ ":
            to = add_movement(pos, blizzard_movement[move])
            if (
                    is_within_board(to) and
                    pos not in walls and
                    pos not in blizzards
            ):
                yield to

    def get_paths(paths):
        new_paths = set()
        for pos in paths:
            for new_pos in valid_moves(pos):
                new_paths.add(new_pos)
        return new_paths

    start = (0, 1)
    end = (len(board)-1, len(board[0])-2)
    time = 1

    paths = {(start)}
    going = True
    while going:
        time += 1
        blizzards = move_blizzards(blizzards)
        paths = get_paths(paths)
        going = not any(path == end for path in paths)
    # # Uncomment this for part 2
    # paths = {(end)}
    # returning = True
    # while returning:
    #     time += 1
    #     blizzards = move_blizzards(blizzards)
    #     paths = get_paths(paths)
    #     returning = not any(path == start for path in paths)
    # paths = {(start)}
    # going_back = True
    # while going_back:
    #     time += 1
    #     blizzards = move_blizzards(blizzards)
    #     paths = get_paths(paths)
    #     going_back = not any(path == end for path in paths)
    return time

board = get_board(data)
blizzards = get_blizzards(board)
walls = get_walls(board)

print(get_answer(board, blizzards, walls))