aoc

import sys
import re
from copy import deepcopy
from math import gcd
from collections import defaultdict, Counter, deque
import heapq
import math

D = open(sys.argv[1]).read().strip()
L = D.split("\n")
G = [[c for c in row] for row in L]
R = len(G)
C = len(G[0])

sys.setrecursionlimit(10**6)


def solve(part1):
    V = set()
    for r in range(R):
        for c in range(C):
            nbr = 0
            for ch, dr, dc in [["^", -1, 0], ["v", 1, 0], ["<", 0, -1], [">", 0, 1]]:
                if 0 <= r + dr < R and 0 <= c + dc < C and G[r + dr][c + dc] != "#":
                    nbr += 1
            if nbr > 2 and G[r][c] != "#":
                V.add((r, c))

    for c in range(C):
        if G[0][c] == ".":
            V.add((0, c))
            start = (0, c)
        if G[R - 1][c] == ".":
            V.add((R - 1, c))
            end = (R - 1, c)

    E = {}
    for rv, cv in V:
        E[(rv, cv)] = []
        Q = deque([(rv, cv, 0)])
        SEEN = set()
        while Q:
            r, c, d = Q.popleft()
            if (r, c) in SEEN:
                continue
            SEEN.add((r, c))
            if (r, c) in V and (r, c) != (rv, cv):
                E[(rv, cv)].append(((r, c), d))
                continue
            for ch, dr, dc in [["^", -1, 0], ["v", 1, 0], ["<", 0, -1], [">", 0, 1]]:
                if 0 <= r + dr < R and 0 <= c + dc < C and G[r + dr][c + dc] != "#":
                    if part1 and G[r][c] in ["<", ">", "^", "v"] and G[r][c] != ch:
                        continue
                    Q.append((r + dr, c + dc, d + 1))

    count = 0
    ans = 0
    SEEN = [[False for _ in range(C)] for _ in range(R)]
    seen = set()

    def dfs(v, d):
        nonlocal count
        nonlocal ans
        count += 1
        r, c = v
        if SEEN[r][c]:
            return
        SEEN[r][c] = True
        if r == R - 1:
            ans = max(ans, d)
        for y, yd in E[v]:
            dfs(y, d + yd)
        SEEN[r][c] = False

    dfs(start, 0)
    return ans


print(solve(True))
print(solve(False))