from sys import stdin from math import * import re data = stdin.readlines() path = data[-1] data = [list(line.strip('\n')) for line in data[:-2]] area = len([c for c in sum(data, start=[]) if not c.isspace()]) sideLen = int(sqrt(area / 6)) def dot(a, b): assert len(a) == len(b) return sum([i*j for i,j in zip(a, b)]) def matmul(a, b): # matrix storage is flipped # that is - [[1,2,3]] is a column vector if type(b) == list: # matrix * matrix assert len(a) == len(b[0]) m = [[0] * len(a[0]) for _ in b] for i in range(len(m[0])): for j in range(len(m)): m[j][i] = dot(b[j], [col[i] for col in a]) return m else: # matrix * scalar return [[n * b for n in col] for col in a] def matadd(a, b): assert len(a) == len(b) assert len(a[0]) == len(b[0]) m = [[0] * len(a[0]) for _ in a] for i in range(len(m[0])): for j in range(len(m)): m[j][i] = a[j][i] + b[j][i] return m def only(a): assert len(a) == 1 return a[0] def gen3Drots(): # base, 3 axis rots = [[[0, 1, 0], [-1, 0, 0], [0, 0, 1]], [[0, 0, 1], [0, 1, 0], [-1, 0, 0]], [[1, 0, 0], [0, 0, 1], [0, -1, 0]]] # gen flipped rots2 = [] for rot in rots: rots2.append(rot) rots2.append(matmul(matmul(rot, rot), rot)) # ensure they're proper rotations for rot in rots2: rot2 = rot for _ in range(4): rot2 = matmul(rot, rot2) assert rot == rot2 return rots2 rots = gen3Drots() # vertexes of each face's corners # the edge (wall[f]; wall[f+1]) is the edge towards facing f wall = [[[ 1, -1, 1]], [[ 1, 1, 1]], [[-1, 1, 1]], [[-1, -1, 1]]] def step(wall, f): def edge(f): v1 = wall[f%4] v2 = wall[(f+1)%4] return matmul(matadd(v1, v2), 0.5) shared = edge(f) # the shared edge prev = edge(f+2) # the edge opposite to shared; will become shared after rot rot = only([rot for rot in rots if matmul(rot, prev) == shared]) wall = [matmul(rot, v) for v in wall] return rot, wall # generate projections from face of 3d cube to 2d square def genProjs(): from itertools import permutations projs = [] for a in [-1, 1]: for b in [-1, 1]: base = [[a, 0], [0, b], [0, 0]] for p in permutations(base): p = list(p) projs.append(p) return projs projs = genProjs() def planestep(x, y, f): x += [1, 0, -1, 0][f] y += [0, 1, 0, -1][f] if not 0 <= y < len(data): return None if not 0 <= x < len(data[y]): return None if data[y][x].isspace(): return None return (x, y, f) def cubestep(x, y, f): if planestep(x, y, f) != None: return planestep(x, y, f) bwall = [[[ 1, -1, 1]], [[ 1, 1, 1]], [[-1, 1, 1]], [[-1, -1, 1]]] def edge(wall, f): v1 = wall[f%4] v2 = wall[(f+1)%4] return matmul(matadd(v1, v2), 0.5) shared = edge(bwall, f) visited = set() def rec(bx, by, bwall): nonlocal visited visited.add((bx, by)) for f in range(4): wx = bx + [1, 0, -1, 0][f] * sideLen wy = by + [0, 1, 0, -1][f] * sideLen if (wx, wy) in visited: continue if not 0 <= wy < len(data): continue if not 0 <= wx < len(data[wy]): continue if data[wy][wx].isspace(): continue visited.add((wx, wy)) _, wall = step(bwall, f) for f in range(4): e = edge(wall, f) if e == shared: return (wx, wy, wall) r = rec(wx, wy, wall) if r != None: return r wx, wy, wall = rec(x, y, bwall) # bwall is the base face, wall is the face we move to # wx, wy are some coordinates inside of the face - convert to upleft corner wx = wx // sideLen * sideLen wy = wy // sideLen * sideLen # find the correct projection from cube space to input space def isGoodProj(p): for vid in range(4): v1 = matmul(p, wall[vid]) v2 = [bwall[vid][0][:2]] if v1 != v2: return False return True proj = only([p for p in projs if isGoodProj(p)]) # coordinates in the wall before rotation bx = (x + [1, 0, -1, 0][f]) % sideLen by = (y + [0, 1, 0, -1][f]) % sideLen # vertex on starting face of cube v = [[bx - (sideLen-1)/2, by - (sideLen-1)/2, 1]] # rotate to new face rot, _ = step(bwall, f) v = matmul(rot, v) # project to input space v = matmul(proj, v) v = [[int(f + (sideLen+1)/2) - 1 for f in v[0]]] # wall coords # find new facing # shared - old facing relative to original wall dv = matmul(proj, matmul(rot, shared)) def dvToFacing(dv): for f in range(4): dx = [1, 0, -1, 0][f] dy = [0, 1, 0, -1][f] if dv[0][0] == dx and dv[0][1] == dy: return f raise "fuck" return wx + v[0][0], wy + v[0][1], dvToFacing(dv) def vis(): for line in data: print(''.join(line)) def move(x, y, f, d): for _ in range(d): nx, ny, nf = cubestep(x, y, f) if data[ny][nx] == '#': break data[y][x] = ">v<^"[f] x, y, f = nx, ny, nf return x, y, f def partTwo(): x = data[0].index('.') y = 0 f = 0 for c in re.findall("\d+|[A-Z]", path): if c == 'L': f = (f - 1) % 4 elif c == 'R': f = (f + 1) % 4 else: x, y, f = move(x, y, f, int(c)) return (y+1) * 1000 + (x+1) * 4 + f print(partTwo())