from collections import defaultdict from sys import stdin inp = [line.rstrip("\n") for line in stdin] start = (inp[0].index("."), 0) end = (inp[-1].index("."), len(inp) - 1) def neighbours( maze: list[str], prev: tuple[int, int], position: tuple[int, int] ) -> list[tuple[int, int]]: ret = [] for dx in (-1, 1): nx = position[0] + dx if nx < 0 or nx >= len(maze[0]): continue if (nx, position[1]) == prev: continue c = maze[position[1]][nx] if c == "#": continue if dx < 0 and c == ">" or dx > 0 and c == "<": continue ret.append((nx, position[1])) for dy in (-1, 1): ny = position[1] + dy if ny < 0 or ny >= len(maze): continue if (position[0], ny) == prev: continue c = maze[ny][position[0]] if c == "#": continue if dy < 0 and c == "v" or dy > 0 and c == "^": continue ret.append((position[0], ny)) return ret to_explore: list[tuple[tuple[int, int], tuple[int, int]]] = [(start, (start[0], 1))] edges: defaultdict[tuple[int, int], set[tuple[int, tuple[int, int]]]] = defaultdict(set) while to_explore: root, pos = to_explore.pop() prev = root dist = 1 while True: neighs = neighbours(inp, prev, pos) if len(neighs) != 1 or inp[neighs[0][1]][neighs[0][0]] in "^>v<": edges[root].add((dist, pos)) for n in neighs: to_explore.append((pos, n)) break dist += 1 prev = pos pos = neighs[0] def longest( start: tuple[int, int], goal: tuple[int, int], seen: frozenset[tuple[int, int]], edges: dict[tuple[int, int], set[tuple[int, tuple[int, int]]]], ) -> int | None: if start == goal: return 0 maximum = 0 new_seen = seen | {start} for dist, n in edges[start]: if n in seen: continue d = longest(n, goal, new_seen, edges) if d is None: continue if d + dist > maximum: maximum = d + dist return maximum if maximum > 0 else None print(longest(start, end, frozenset(), edges)) fullgraph: defaultdict[tuple[int, int], set[tuple[int, tuple[int, int]]]] = defaultdict( set, ((k, v.copy()) for k, v in edges.items()) ) for k, v in edges.items(): for dist, pos in v: fullgraph[pos].add((dist, k)) print(longest(start, end, frozenset(), fullgraph))