1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
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))
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())
|
