| 1234567891011121314151617181920212223242526272829303132333435363738394041 |
- #!/usr/bin/env python3
- import sys
- DXDY = {'^': [(0, -1)], 'v': [(0, 1)], '<': [(-1, 0)], '>': [(1, 0)],
- '.': [(0, -1), (0, 1), (-1, 0), (1, 0)]}
- def parse(inp):
- graph = {}
- lines = inp.split()
- for y, line in enumerate(lines):
- for x, char in enumerate(line):
- if char != '#':
- graph[(x, y)] = nbs = {}
- for dx, dy in DXDY[lines[y][x]]:
- nx, ny = nb = x + dx, y + dy
- if 0 <= ny < len(lines) and lines[ny][nx] != '#':
- nbs[nb] = 1
- for xy in [xy for xy, nbs in graph.items() if len(nbs) == 2]:
- (left, left_dist), (right, right_dist) = graph.pop(xy).items()
- left_nbs = graph[left]
- if xy in left_nbs:
- left_nbs[right] = left_nbs.pop(xy) + right_dist
- right_nbs = graph[right]
- if xy in right_nbs:
- right_nbs[left] = right_nbs.pop(xy) + left_dist
- return graph
- def longest_path(graph):
- start = next(iter(graph)) # python 3.8 guarantees insertion order
- end = next(reversed(graph))
- def dfs(xy, dist, vis):
- if xy == end:
- yield dist
- for nb, nbdist in graph[xy].items():
- if nb not in vis:
- yield from dfs(nb, dist + nbdist, vis | {nb})
- return max(dfs(start, 0, {start}))
- inp = sys.stdin.read()
- print(longest_path(parse(inp)))
- print(longest_path(parse(inp.translate(str.maketrans('<>^v', '....')))))
|
