puzzle_input = """#.####################################################################################################
#>.^>^v<^v>>>v<.>v><vv<<<.^^>>^v.^^v^vv<<><>v><v>v^>^<<>vvv<<>v>>.^>>^.^>..<<v<v<^.>.>^^<><><><^^.^<>#
#>vv<<v<<<<v>v<v^.<.v<<><v<<.<>>^^.>.^v>^^.^^.><v>><<^^^^<^>>.v.><v.v.<<<<<v>v<^>v^<>^v<^.<^^>^>vv>^>#
#>^.^>^^^v<>v><>v^vv>v>>v<v<<..><><<>v<>v>v^v>vv<v.<.v^vv<v>.>v<^>v>>v..v<>^v.>v.><^><<v<vvv<^>v>.^<>#
#<.v.v^<>^v<<^>v^>v^<.<>>^<><>v.<v>^^><><v>^^>^>.^.v>.<vv>^.>.vv^v^^<^>^.<>.^>^>^><.>>>>^<<v>^^><^v<>#
#<<v<^^v^><.v<v.^>^^<..^^.>v^<^^^^.<><v<^^><^>><^>^v^>.vvvvv^<^>^v<^>^<^>><<>^v<>^^^v<<^>vvv>v^^^<.<<#
#<v^v><<>^^.<v^.v><<>>v^vv<^<^^.v<.v><>><<<.v<.<<<<v>.<><^<v^<>vv^>v<v>^^><^^^v>.^^^<><>>v>v<>^v>>v^<#
#<..^vv>^vv^>v<^<>..^<^v<^><<<>>.vvv^v^>>v>^^>.<<vvv<v.>^>><vv<^^.v^v.v>>><^<<<>^v.>><v>^^>^v<v>^vv>>#
#<^^>v^v^v^>.>v<<>>>^^>vvvvv<>^.v>><>^<>>v^^^^^v<>>>^^>>>^.>><.>v>v^><.^vv^<<<<^v<><^^>vv..^^v^<<^<v>#
#>.v<v^.<v.^vvv^>>^<v^^<<^><><v>>^^>.^v<vv<>><^<.v.v<.<.^vvv^.^v^v><v<<.<>^<v>>v<^^>^vv<.vvv<<^<vv<v<#
#<<v<>>v<<^>v><v.><<.<>^^vvvv^<>.v>v^v.^^>.^^^>^>^>^^><v>.v^>v^vv><<>><^<<vvvv^v<>v^<<.^^v>.>>>><^>^<#
#<>>>>vv>^^<^<^^^^^><v^^<>vvv<><<>v^.vvv^>^v^>v<^<^v>>vvvv^vv<<>.vv<.<vv^^>>>v>>^>v><<v<><v.><v^vvv<>#
#><vv^v<vv<<v^>^.^^>>v>v.^<^v<^v>.vv.^>><><>^<^v>>v<.^.<^.>.^v<.<.>^>^.^>>>>v<^>v>^..^.v<^.><.<<.<^>>#
#<>>^<^v<.<v^v>^^>^>.v^<v>v<^<>^>>.^v><^>vv<<>v>>v>.v<>>^^v>>v<<^^v^v...^.^><^^^.^vvv>vv><<>^<<><<.^>#
#>v^<^^^v^>><.>.v<v>^.v^^.<^^v^.<v<<.>v<.^v>^^...^^^<^>^^vv>v>v>v^v<>vv>>vv^>>>><>^vv^v^<<vv^.><^v<^<#
#<><><><v><><<^^v.^v<>v^<v>>v^v<<^^.^>.<<<>.><^^vv>v<<<<>>v^^^>^<<^^<^.<>>><^^v.<>v>.<.<>>v>>v>>>>v^.#
#>^v>>>>.^<^.v>>><^<<v.<<^vv.^<.>><>v.><>vv>v<.^v.<<^<v<^.v<<^^<<^^<^<v.v>vv^v<vv.^v.<^^>^>^..vv^^>>>#
#..<.><.v<>^>>v<>.>^v.>^vv>>...<.>><<v^v<<>>vv>>v^><<^^>^^.>v.>>>v^^^<.<<v>>^<v<^^<v<v<>>^.<^v>.^^<<<#
#<.<v.><vv<v<^<v<.vv^.v>v^v<.<>v^>>^<^vv>.<^<>.^><<>>.<.<<<><<<^v<^^<><>^^<v.<v>>>>vv.>v^><>v.><^<v.>#
#>^>^>^<<<^v^<<^v>^<.^vvv<>>^>>v>>>^><v<>..>v>>>^^vvv><v^^>^v^.^<v><v.>.<<^vv>^^.<^^v>^><^<^^v<>>>.<>#
#<v^<v><.>v>vv.^>v^^.vv^><^>^^^v^<v^^vvv>><.<..v^v^>^<<^>>^>^>^.>>vv.^>>.v>>><<<>>^<<.>v.v>.<><v<>v>>#
#>^.<<>>vv^<v^v<<>>>>^><vv<^v>>>^v><>v<><v>.>v>^v>><vv><.><<<^^v<>.^<v><><v^>>><<vv.v>^vv>v<<>^<^v^v<#
#<<.vv.<v^vv><>^<^^v^<<<<^>>^><^vv>^^<^.v^>^.v<^^<v<<.<v<^^.<^v^.<^.v>v<v><.>^vv.vv^vv^<<<>.>v^v.v.><#
#<>>>>>v>v.v^>><>v^<^<<<^<vv>>v<<<><v<>.^^<^vvv^.>>><v<<.^v<v<v.^v.v<>v<v<v>v^>>>v>^v<<>>.<>vvv^>>>v<#
#<^.<<^<v>v<^^v<^<<>v.<<^^<.<>><<><>v<><.<<<^>v.^>v<<>.^><vv^>>>vvvv^<^v^>v<^v<>.<vv>^v><v<v^>.v<<v>>#
#<.<v><>^>>.>v^vv>^^<^><.>>^v^<><>v^^v<>>.v.>v>.^^vvvv<><>v^>v>v<<.^v^^<v^^v>v^^v>v><>v>vvv<^>^>^<v<>#
#<v<.<>^^^<vv.^^>v>^.>>>.<<><vvv^>vvv.<v<.v>v<.<<v<^<^^><^^^.>^<.v>><<^^.^.<^v^.<>v.v^><<<^.<.^^vvv^>#
#<v.v><.>>><.><<>>.^>.<<v>>^>.>^>v>v>>..v^^><v.><<^vv>^v^>.>>><>^.vvv^.<<>vv>><<>>vv>v<<<^<>v>><>vv<<#
#>v^^v<><>^^>v^><^^<>.^vv>vv^^^<<.^^vv^<^^^v>.v^^<^><^<<v>>^..^<<<<^vv>><v<^<>^>v>^>.>.<<<>.^^>vv^^>>#
#>.>^<^>.v^>>>vv<>>^>><<>v^.^>.>>><^^^<><>^v>^vv><vv>.>v^<^^v>vv^vv<v.<>vv.>.<^^<><v>v>^^<.<vv<<^vv^>#
#>.>>^<^.^><<v.^<^^v<^^<v<<><v^><^.>^><>v>>>^.^^>>><><^>>>><>^^.v^>><.>.^>.<^.v^<<<>>>>><.^vv<>>vv<^>#
#>v>^^<v.<>^v.<v>v^v>^^.>>>.>.<<^<<>^v>><.v>v^<>>vv^>v<.<^^v<>vv^^<v>>v>^v>^<^v<>^v^<.^>^.<>>><.^v>..#
#>.^^.<>.>v^^>>^>^^<.<<>..>>^><><<v<^><<^v^<>v><v>^>><><<v^<^<v<v.v<.>.>>>>^^^v<.v><><><v<^<vv.>>><.>#
#<>^>.v>v>v<v<v>v.>^<v^vv<vvv>^v<^>^v><>.<><vv>v<<.<v>>^^v>^<vv.><>v.^^.>.^<^v<.><^^>><<>.^^v.>v><<.<#
#>>v.v>^^.>>>.<>>^v<^>.<>^^<<><.v><v.>>>^^<>>>^>v>>^>^v>><><^.^^><^^^><v^><v><v^>^.>v>>>v<><vv<v^.>.>#
#>>>>>^<<^v^v<<^>.vv.vv^^v^<vv.>>>v^.<..^v^^v<><v>^<<^.^.v<^.<<<>vv>..^v>>><>^<v<>><^^.^^>^.^^>v>><v>#
####################################################################################################.#"""

puzzle_input_example = """#.######
#>>.<^<#
#.<..<<#
#>v.><>#
#<^v^^>#
######.#"""

import numpy as np

DIRECTION_CODE = {">" : (1,0), "<" : (-1,0), "v" : (0,1), "^" : (0,-1)}
MOVES = [(0,1),(1,0),(0,0),(-1,0),(0,-1),]

class Blizzard():
    def __init__(self,offset,direction):
        self.offset = offset
        self.direction = direction

# Read map

lines = puzzle_input.split("\n")

blizzards = []
entrance_x = lines[0].index(".")
exit_x = lines[-1].index(".")

field_width = len(lines[0])
field_height = len(lines)

for y, line in enumerate(lines):
    for x in range(len(line)):
        if (line[x] != "#") and (line[x] != "."):
            blizzards.append(Blizzard((x-1,y-1),DIRECTION_CODE[line[x]]))

def state_at_timepoint(time_point):
    global field_width
    global field_height
    global entrance_x
    global exit_x
    global blizzard
    result = np.zeros((field_width,field_height))
    result[0,:] = 1 # Wall on top
    result[-1,:] = 1 # Wall on bottom
    result[:,0] = 1 # Wall on left
    result[:,-1] = 1 # Wall on right
    result[entrance_x,0] = 0
    result[exit_x,-1] = 0
    for blizzard in blizzards:
        blizzard_x = 1 + (blizzard.offset[0] + blizzard.direction[0] * time_point) % (field_width - 2)
        blizzard_y = 1 + (blizzard.offset[1] + blizzard.direction[1] * time_point) % (field_height - 2)
        result[blizzard_x,blizzard_y] = 2
    return result


def display_state(state):
    for y in range(state.shape[1]):
        line = ""
        for x in range(state.shape[0]):
            line += str(int(state[x,y]))
        print(line)


timepoint = 0

# First pass forward

reachable = np.zeros((field_width,field_height))
reachable[entrance_x,0] = 1

while not reachable[exit_x,field_height-1] == 1:
    timepoint += 1
    next_state = state_at_timepoint(timepoint)
    reachable_next_state = np.zeros((field_width,field_height))
    for y in range(field_height):
        for x in range(field_width):
            for move in MOVES:
                if reachable[x,y] == 1:
                    if (y+move[1] >= 0 and y+move[1] < field_height):
                        if next_state[x+move[0],y+move[1]] == 0:
                            reachable_next_state[x+move[0],y+move[1]] = 1
    reachable = reachable_next_state

print("Made it to the exit in",timepoint,"steps")