#!/usr/bin/env python3

import random
from collections import defaultdict
import sys

sys.setrecursionlimit(15000)


no_slippery = True


PATH = 1
FOREST = 2
SLOPE_NORTH = 3
SLOPE_EAST = 4
SLOPE_SOUTH = 5
SLOPE_WEST = 6


map = []

with open("input.txt", "r") as f:
    for line in f:
        row = []
        for char in line.strip():
            tile = None
            if char == ".":
                tile = PATH
            if char == "#":
                tile = FOREST
            if char == "^":
                tile = SLOPE_NORTH
            if char == ">":
                tile = SLOPE_EAST
            if char == "v":
                tile = SLOPE_SOUTH
            if char == "<":
                tile = SLOPE_WEST
            row.append(tile)

        map.append(row)


def find_path(row):
    for i, tile in enumerate(row):
        if tile == PATH:
            return i


start = (0, find_path(map[0]))
goal = (len(map) - 1, find_path(map[-1]))


def valid_next_step(destination, illegal_slope):
    global no_slippery
    (y, x) = destination
    try:
        tile = map[y][x]

        if no_slippery:
            return tile not in [FOREST]
        else:
            return tile not in [illegal_slope, FOREST]
    except:
        return False


def possible_directions(coords):
    (y, x) = coords
    tile = map[y][x]

    if tile == FOREST:
        raise Exception("Cannot be in a forest!")

    if not no_slippery:
        if tile == SLOPE_NORTH:
            return [(y - 1, x)]
        if tile == SLOPE_EAST:
            return [(y, x + 1)]
        if tile == SLOPE_SOUTH:
            return [(y + 1, x)]
        if tile == SLOPE_WEST:
            return [(y, x - 1)]

    steps = [
        ((y - 1, x), SLOPE_SOUTH),
        ((y, x + 1), SLOPE_WEST),
        ((y + 1, x), SLOPE_NORTH),
        ((y, x - 1), SLOPE_EAST),
    ]

    valid_destinations = []

    for destination, illegal_slope in steps:
        if valid_next_step(destination, illegal_slope):
            valid_destinations.append(destination)

    return valid_destinations


longest_path = -1

memo = defaultdict(lambda: -1)


def walk(path, length, position):
    global longest_path

    if length < memo[position]:
        return

    if position == goal:
        if length > longest_path:
            longest_path = length
            print("NEW BEST", longest_path)
        return

    cool = possible_directions(position)
    random.shuffle(cool)
    for next_position in cool:
        if next_position not in path:
            next_path = dict(path)
            next_path[position] = True
            walk(next_path, length + 1, next_position)


walk({}, 0, start)

print(longest_path)