from sys import stdin from math import lcm from heapq import heappop, heappush def tadd(a, b): return (a[0] + b[0], a[1] + b[1]) # return tuple(map(sum, zip(a, b))) def tmul(a, b): return (a[0] * b, a[1] * b) # return tuple([n*b for n in a]) def tmod(a, b): return (a[0] % b[0], a[1] % b[1]) # return tuple([a%b for (a,b) in zip(a, b)]) def tdist(a, b): return abs(a[0] - b[0]) + abs(a[1] - b[1]) # direction tuple def tdir(f): return ([0, 1, 0, -1][f%4], [-1, 0, 1, 0][f%4]) data = stdin.readlines() start = (data[0].index('.') - 1, -1) end = (data[-1].index('.') - 1, len(data) - 2) data = [l.strip()[1:-1] for l in data[1:-1]] w = len(data[0]) h = len(data) cycle = lcm(w, h) # 0 N 1 E 2 S 3 W blizzards = [set() for _ in range(4)] for y, line in enumerate(data): for x, c in enumerate(line): dirs = "^>v<" if c in dirs: blizzards[dirs.index(c)].add((x, y)) def coll(x, y, t): if (x, y) == start: return False if (x, y) == end: return False if not 0 <= x < w: return True if not 0 <= y < h: return True for d in range(4): v = tmod(tadd((x, y), tmul(tdir(d), -t)), (w, h)) if v in blizzards[d]: return True return False def search(start, end, t): cur = [(0, (start, t))] visited = set(cur[0][1]) def dist(node): bv, t = node return tdist(bv, end) + t while True: _, node = heappop(cur) bv, t, = node vs = [bv] for d in range(4): vs.append(tadd(bv, tdir(d))) for v in vs: if not coll(*v, t+1): if v == end: return t+1 node = (v, t+1) if not node in visited: visited.add(node) heappush(cur, (dist(node), node)) partOne = search(start, end, 0) print(partOne) partTwo = search(start, end, search(end, start, partOne)) print(partTwo)