diff options
Diffstat (limited to '22.22/part2.py')
| -rw-r--r-- | 22.22/part2.py | 216 |
1 files changed, 216 insertions, 0 deletions
diff --git a/22.22/part2.py b/22.22/part2.py new file mode 100644 index 0000000..d16635f --- /dev/null +++ b/22.22/part2.py @@ -0,0 +1,216 @@ +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)) + +tiny = [a[::sideLen] for a in data[::sideLen]] + +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 + 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 + +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 matmulsc(a, b): + return [[n * b for n in col] for col in a] + +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 matmulsc(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 matmulsc(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()) |