day 22 part 2

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())