Eigencube.xtl

1⍝# Eigencube: a Rubik's cube as rotation matrices, turned by matrix
2⍝# products and solved by search. A port of Steffen Smolka's
3⍝# eigencube.py (github.com/smolkaj/eigencube, MIT). Each of the 26
4⍝# cubelets is the integer point c of {-1, 0, 1}^3 where it sits in the
5⍝# solved cube and carries a rotation matrix R: it sits now at R c. A
6⍝# quarter turn of the face with outward normal v moves the cubelets
7⍝# with v . (R c) > 0, multiplying R by one rotation matrix. A batch of
8⍝# cubes is one array, n by 26 by 3 by 3, so all twelve turns of every
9⍝# cube in a search are two matrix products.
10⍝# Import it with an alias of your choice: "ec:" u_se< "Eigencube".
11⍝# Put libs/Eigencube/src on XETAL_PATH ("just path"); the reference is libs/Eigencube/docs.
12⍝# Names with l: are exported; those under h: are private to this file.
13⍝#
14⍝# Moves are numbered 1 to 12: move 2f-1 turns face f clockwise as seen
15⍝# facing it, move 2f counterclockwise, the faces in the order of
16⍝# ec:faces, "UDFBRL" (up +z, front +x, right +y); ec:n_ame writes them
17⍝# in the usual notation (U, U', D, ...) and ec:p_arse reads it.
18
19⍝## The cube
20
21⍝# The 27 integer points of {-1, 0, 1}^3, one per row (x slowest).
22pts ← (o̲\ 3 3 3 e̲ncode o̲ffsets 27) − 1
23⍝# The 26 cubelets, each named by its place in the solved cube: every
24⍝# point but the hidden center.
25C ← (0 < '+ r̲/₂ a̲bs pts) r̲eplicate pts
26⍝# Each cubelet's 1-norm, its number of stickers: 1 center, 2 edge,
27⍝# 3 corner.
28kind ← '+ r̲/₂ a̲bs C
29⍝# Each cubelet's layer in the solved cube: 1 top, 0 middle, -1 bottom.
30z ← 3 s̲elect₂ C
31⍝# The 3-by-3 identity.
32I ← 3 3 r̲eshape 1 0 0 0 1 0 0 0 1
33⍝# The solved cube: every cubelet unrotated, a batch of one, 1 26 3 3.
34ˡsolved ← 1 26 3 3 r̲eshape I
35
36⍝## The twelve quarter turns
37
38⍝# The six faces' outward normals, named U D F B R L: up is +z, front
39⍝# +x, right +y. Faces 2a-1 and 2a share axis a.
40N ← 6 3 r̲eshape 0 0 1  0 0 -1  1 0 0  -1 0 0  0 1 0  0 -1 0
41⍝# The face names, in the order of N.
42ˡfaces ← "UDFBRL"
43⍝# The move vectors: move 2f-1 turns face f clockwise as seen facing
44⍝# it, move 2f counterclockwise.
45V ← 2 r̲eplicate N
46⍝# Each move's direction: 1 clockwise, -1 counterclockwise.
47dir ← 12 r̲eshape 1 -1
48⍝# The cross-product matrices, flattened: row k holds minus the
49⍝# Levi-Civita symbol eps(i, j, k) over (i, j), so that row v of
50⍝# V '+ '× i̲nner E is [v]x, the matrix with [v]x u = v x u.
51E ← 3 9 r̲eshape 0 0 0  0 0 -1  0 1 0  0 0 1  0 0 0  -1 0 0  0 -1 0  1 0 0  0 0 0
52⍝# The twelve rotation matrices, flattened, one per row: a quarter
53⍝# turn clockwise about v (seen from v) is v v^T - [v]x, Rodrigues'
54⍝# formula at -90 degrees; counterclockwise flips the sign of [v]x.
55Mf ← (((3 r̲eplicate 1 2 3) s̲elect₂ V) × (9 r̲eshape 1 2 3) s̲elect₂ V) − (12 9 r̲eshape 9 r̲eplicate dir) × V '+ '× i̲nner E
56⍝# The twelve matrices stacked into one 36 by 3 matrix: rows 3m-2 to
57⍝# 3m are move m's. One product with it turns a batch every way at once.
58M ← 36 3 r̲eshape Mf
59
60⍝# h:t_urns R: every quarter turn applied to every 3-by-3 matrix of R,
61⍝# a batch of n (n 3 3); the result is 12 n 3 3, turn first. The batch
62⍝# is laid out 3 n 3, so one matrix product with M turns them all.
63ʰt̲urns ← { R →
64  n ← t̲ally R
65  1 3 2 4 t̲ranspose (12 3 c̲at n c̲at 3) r̲eshape M '+ '× i̲nner 2 1 3 t̲ranspose R
66}
67
68⍝# h:p_os S: where each cubelet of each cube of the batch S (n 26 3 3)
69⍝# sits, R c; the result is n 26 3.
70ʰp̲os ← { S → '+ r̲/₄ S × (s̲hape S) r̲eshape 2 1 3 t̲ranspose 3 26 3 r̲eshape C }
71
72⍝# h:c_hildren S: all twelve turns of every cube of the batch S, 12n
73⍝# cubes, move-major: cube r is move 1 + (r - 1) div n of cube
74⍝# 1 + (r - 1) mod n. A cubelet moves when the move vector's dot
75⍝# product with where it sits is positive (one matrix product for
76⍝# every move and cubelet); a moved cubelet's matrix is the turn's
77⍝# matrix times its own (the other product, in h:t_urns).
78ʰc̲hildren ← { S →
79  n ← t̲ally S
80  sh ← 12 c̲at n c̲at 26 3 3
81  sel ← 0 < V '+ '× i̲nner o̲\ ((n × 26) c̲at 3) r̲eshape ʰp̲os S
82  T ← sh r̲eshape ʰt̲urns ((n × 26) c̲at 3 3) r̲eshape S
83  S12 ← sh r̲eshape S
84  ((12 × n) c̲at 26 3 3) r̲eshape S12 + (sh r̲eshape 9 r̲eplicate r̲avel sel) × T − S12
85}
86
87⍝# l:t_urn m S: move m (1 to 12) applied to every cube of the batch S.
88⍝# >> "ec:" u_se< "Eigencube"
89⍝# >> ec:solved m_atch 4 '{ S -> 5 ec:t_urn S } p_ower ec:solved
90⍝# 1
91ˡt̲urn ← { m S → (((m − 1) × t̲ally S) + r̲ange t̲ally S) s̲elect ʰc̲hildren S }
92
93⍝# l:d_o ms S: the moves ms (a vector of 1 to 12) applied in order to
94⍝# every cube of the batch S.
95⍝# >> "ec:" u_se< "Eigencube"
96⍝# >> ec:solved m_atch 12 11 10 9 ec:d_o 9 10 11 12 ec:d_o ec:solved
97⍝# 1
98ˡd̲o ← { ms S →
99  0 = t̲ally ms ? S
100  (1 d̲rop ms) ˡd̲o (f̲irst ms) ˡt̲urn S
101}
102
103⍝## Stickers: the cube as six faces of nine colors
104
105⍝# Each face's two directions across the page, as a cube net draws
106⍝# it: rightward, then downward, seen from outside the face (U with F
107⍝# below it, D with F above it, the side faces with U above them).
108across ← 6 3 r̲eshape 0 1 0  0 1 0  0 1 0  0 -1 0  -1 0 0  1 0 0
109down ← 6 3 r̲eshape 1 0 0  -1 0 0  0 0 -1  0 0 -1  0 0 -1  0 0 -1
110
111⍝# l:s_tickers S: the colors of the cube S (a batch of one) as a 6 by 9
112⍝# matrix, a row per face (U D F B R L), its cells row by row as the
113⍝# face is seen; a color is the face of the solved cube it belongs to
114⍝# (1 to 6, the order of N). Cubelet k shows a sticker on face v when
115⍝# v . (R c) = 1; the sticker's color is the direction it faced in the
116⍝# solved cube, R^T v, so the colors are one more matrix product.
117ˡs̲tickers ← { S →
118  P ← 26 3 r̲eshape ʰp̲os S
119  on ← r̲avel 1 = N '+ '× i̲nner o̲\ P
120  cell ← (3 × 1 + down '+ '× i̲nner o̲\ P) + 2 + across '+ '× i̲nner o̲\ P
121  key ← r̲avel (10 × 6 26 r̲eshape 26 r̲eplicate r̲ange 6) + cell
122  home ← N '+ '× i̲nner 2 1 3 t̲ranspose 26 3 3 r̲eshape S
123  color ← N i̲ndexOf 156 3 r̲eshape home
124  6 9 r̲eshape (g̲rade on r̲eplicate key) s̲elect on r̲eplicate color
125}
126
127⍝## The 24 orientations, and how far each cubelet is from home
128
129⍝# h:g_row G: the rotations G (flattened rows of 9) and every turn of
130⍝# them, without repeats.
131ʰg̲row ← { G → u̲nique G c̲at ((12 × t̲ally G) c̲at 9) r̲eshape ʰt̲urns ((t̲ally G) c̲at 3 3) r̲eshape G }
132⍝# The cube's 24 rotations, flattened, one per row: what the twelve
133⍝# turns reach from the identity (three rounds reach them all).
134G ← 3 'ʰg̲row p̲ower 1 9 r̲eshape I
135⍝# The turns' Cayley table: row m, column g is the index in G of the
136⍝# rotation that move m makes of rotation g.
137Tm ← 12 24 r̲eshape G i̲ndexOf 288 9 r̲eshape ʰt̲urns 24 3 3 r̲eshape G
138
139⍝# h:o_rient S: the index in G of each cubelet's rotation, n 26.
140ʰo̲rient ← { S → ((t̲ally S) c̲at 26) r̲eshape G i̲ndexOf ((26 × t̲ally S) c̲at 9) r̲eshape S }
141
142⍝# Where each cubelet sits in each rotation, 26 24: the index in pts
143⍝# of G c, from one matrix product of every rotation with every name.
144at ← 26 24 r̲eshape pts i̲ndexOf 624 3 r̲eshape 2 3 1 t̲ranspose 24 3 26 r̲eshape (72 3 r̲eshape G) '+ '× i̲nner o̲\ C
145⍝# Which points each move turns, 12 27: the dot product of the move
146⍝# vector with the point is positive.
147layer ← 1 × 0 < V '+ '× i̲nner o̲\ pts
148
149⍝# h:n_ext O: h:c_hildren for cubes given by their orientations O (n 26),
150⍝# as orientations (12n 26): the same turns, read from the two tables
151⍝# the matrices made (at, layer and the Cayley table Tm), so the search
152⍝# moves 26 small integers per cube instead of 26 matrices.
153ʰn̲ext ← { O →
154  n ← t̲ally O
155  m ← (n × 26) r̲eplicate o̲ffsets 12
156  o ← (12 × n × 26) r̲eshape r̲avel O
157  P ← ((r̲avel O) + 24 × (n × 26) r̲eshape o̲ffsets 26) s̲elect r̲avel at
158  sel ← ((27 × m) + (12 × n × 26) r̲eshape P) s̲elect r̲avel layer
159  ((12 × n) c̲at 26) r̲eshape o + sel × (((24 × m) + o) s̲elect r̲avel Tm) − o
160}
161
162⍝# h:r_elax d: a table of distances (cubelet by rotation) relaxed along
163⍝# every turn until it stops changing, so d[k; g] becomes the fewest
164⍝# quarter turns that take rotation g to one where cubelet k is done.
165ʰr̲elax ← { d →
166  e ← d m̲in 1 + 'm̲in r̲/₂ 26 12 24 r̲eshape (r̲avel Tm) s̲elect₂ d
167  e m̲atch d ? d
168  ʰr̲elax e
169}
170⍝# h:d_istances done: the distance table from a 26 by 24 table of 1s
171⍝# where the cubelet counts as done in that rotation.
172ʰd̲istances ← { done → ʰr̲elax 99 × 1 − done }
173
174⍝# How far column j of each rotation is from e_j, 24 3.
175colDev ← '+ r̲/₂ a̲bs (24 3 3 r̲eshape G) − 24 3 3 r̲eshape I
176⍝# Solved distances, 26 24 (eigencube.py's min_moves_to_solved): a
177⍝# cubelet is solved when its rotation fixes each axis it has stickers
178⍝# on, the nonzero coordinates of its name.
179Dsolved ← ʰd̲istances 0 = (a̲bs C) '+ '× i̲nner o̲\ colDev
180⍝# l:s_olved? S: whether every cubelet of the cube S (a batch of one) is
181⍝# solved (eigencube.py's is_cube_solved): a center may still be turned
182⍝# about its own axis, which no sticker shows.
183⍝# >> "ec:" u_se< "Eigencube"
184⍝# >> (ec:s_olved? ec:solved) c_at ec:s_olved? 1 ec:t_urn ec:solved
185⍝# 1 0
186ˡs̲olved? ← { S → 0 = '+ r̲/ ((r̲avel ʰo̲rient S) + 24 × o̲ffsets 26) s̲elect r̲avel Dsolved }
187⍝# How far each rotation moves each home point, 24 26.
188posDev ← '+ r̲/₂ a̲bs (24 3 26 r̲eshape (72 3 r̲eshape G) '+ '× i̲nner o̲\ C) − 24 3 26 r̲eshape o̲\ C
189⍝# Place distances, 26 24 (eigencube.py's min_moves_to_position): a
190⍝# cubelet is in place when R c = c, its stickers perhaps twisted.
191Dplace ← ʰd̲istances 0 = o̲\ posDev
192⍝# Whether each rotation keeps the bottom face (yellow) down: R fixes z.
193yellowDown ← 1 × 0 = 3 s̲elect₂ colDev
194
195⍝## The stages: goals and heuristics as matrix products
196
197⍝# The cubelet sets the stages count over, one per row: 1 none, 2 top
198⍝# edges, 3 top layer, 4 top and middle layers, 5 bottom edges,
199⍝# 6 bottom corners, 7 middle layer, 8 bottom layer but its corners,
200⍝# 9 all but the bottom corners.
201sets ← 9 26 r̲eshape (26 r̲eshape 0) c̲at ((z = 1) ∧ kind = 2) c̲at (z = 1) c̲at (z ≥ 0) c̲at ((z = -1) ∧ kind = 2) c̲at ((z = -1) ∧ kind = 3) c̲at (z = 0) c̲at ((z = -1) ∧ kind < 3) c̲at n̲ot (z = -1) ∧ kind = 3
202
203⍝# h:s_pec s: stage s (1 to 29) as 7 rows of 3. A goal is three counts
204⍝# at least their thresholds: count c is how many cubelets of set
205⍝# row1[c] are solved, plus of set row2[c] have yellow down, plus of
206⍝# set row3[c] are in place; row 6 holds the thresholds. The heuristic
207⍝# is a sum of three terms, term t (sum of sqrt d)^2 / row7[t], the
208⍝# sum over set row4[t] of solved distances and over set row5[t] of
209⍝# place distances (eigencube.py's p-norms with p = 1/2).
210⍝# Stages 1-17 solve the top and middle layers a cubelet at a time,
211⍝# 18-25 the bottom edges (yellow down, then solved), 26-29 put the
212⍝# bottom corners in place.
213ʰs̲pec ← { s →
214  s ≤ 9 ? 7 3 r̲eshape (2 3 4 1 1 1 1 1 1 3 1 1 1 1 1) c̲at (4 m̲in s) c̲at s c̲at s c̲at 8 1 1
215  s ≤ 17 ? 7 3 r̲eshape (2 3 4 1 1 1 1 1 1 4 1 1 1 1 1 4 9) c̲at s c̲at 4 1 1
216  s ≤ 25 ? 7 3 r̲eshape (4 1 5 1 5 1 1 1 1 9 1 1 1 1 1 17) c̲at (4 m̲in s − 17) c̲at (s − 21) c̲at 3 1 1
217  7 3 r̲eshape (4 5 1 1 1 1 1 1 6 3 7 8 1 1 6 17 4) c̲at (s − 25) c̲at 5 3 8
218}
219
220⍝# h:o_f r spec: the cubelet sets named by row r of a stage's spec, as
221⍝# the columns of a 26 by 3 matrix of 1s and 0s.
222ʰo̲f ← { r spec → o̲\ (r s̲elect spec) s̲elect sets }
223
224⍝# h:r_elevant spec: the cubelets a stage looks at, 1s and 0s over the
225⍝# 26: those of every set its goal and heuristic name (rows 1 to 5).
226ʰr̲elevant ← { spec → 0 < '+ r̲/ (r̲avel 5 t̲ake spec) s̲elect sets }
227⍝# h:p_roject rel O: the orientations O with every cubelet the stage
228⍝# does not look at (rel 0) set to 1, the identity. A turn moves each
229⍝# cubelet by its own position and rotation alone, never by the others,
230⍝# so cubes that differ only there are one state to the stage's search.
231ʰp̲roject ← { rel O → 1 + (O − 1) × (s̲hape O) r̲eshape rel }
232
233⍝# h:s_core spec O: each cube's search score, from its cubelets'
234⍝# orientations O (n 26, h:o_rient): -1 for a cube that meets the
235⍝# stage's goal, else its heuristic, a Float per cube.
236ʰs̲core ← { spec O →
237  n ← t̲ally O
238  o ← r̲avel O
239  ix ← o + 24 × (n × 26) r̲eshape o̲ffsets 26
240  ds ← (n c̲at 26) r̲eshape ix s̲elect r̲avel Dsolved
241  dp ← (n c̲at 26) r̲eshape ix s̲elect r̲avel Dplace
242  yd ← (n c̲at 26) r̲eshape o s̲elect yellowDown
243  cnt ← ((ds = 0) '+ '× i̲nner (1 ʰo̲f spec)) + (yd '+ '× i̲nner (2 ʰo̲f spec)) + (dp = 0) '+ '× i̲nner (3 ʰo̲f spec)
244  goal ← '∧ r̲/₂ cnt ≥ (n c̲at 3) r̲eshape 6 s̲elect spec
245  q ← (((f̲loat ds) ^ 0.5) '+ '× i̲nner f̲loat 4 ʰo̲f spec) + ((f̲loat dp) ^ 0.5) '+ '× i̲nner f̲loat 5 ʰo̲f spec
246  h ← (q × q) '+ '× i̲nner 1 ÷ 7 s̲elect spec
247  ((f̲loat n̲ot goal) × h + 1.0) − 1.0
248}
249
250⍝## Search: A*, a batch of cubes at a time
251
252⍝# How many of the best open cubes each step of the search expands.
253batch ← 256
254⍝# How much more the heuristic weighs than the moves made (weighted A*).
255greed ← 1.0
256
257⍝# l:i_nverse m: the move that undoes move m (0, no move, has none).
258ˡi̲nverse ← { m → m + (2 × m m̲od 2) − 1 }
259⍝# h:f_ace m: the face move m turns, 1 to 6 (0 for no move).
260ʰf̲ace ← { m → (m + 1) d̲iv 2 }
261
262⍝# h:c_ubes O: the cubes whose cubelets' orientations are O (n 26), their
263⍝# rotation matrices looked up in G, n 26 3 3.
264ʰc̲ubes ← { O → ((t̲ally O) c̲at 26 3 3) r̲eshape (r̲avel O) s̲elect G }
265⍝# h:k_ey O: each cube's key, n 2: its 26 orientations (1 to 24) as two
266⍝# 13-digit numbers in base 24, so one i_ndexOf finds a cube.
267ʰk̲ey ← { O → o̲\ (2 c̲at t̲ally O) r̲eshape (24 d̲ecode o̲\ 13 t̲ake₂ O − 1) c̲at 24 d̲ecode o̲\ -13 t̲ake₂ O − 1 }
268
269⍝# The macros: the solver's moves for the middle and bottom layers,
270⍝# each a fixed sequence of turns. 1 to 3: D, D' and D2. 4 to 8: the
271⍝# classic sequences for the last layer, mirrored from the top to the
272⍝# bottom (U and D swap, R and L swap): F L D L' D' F' flips two bottom
273⍝# edges, Sune (L D L' D L D2 L') and its mirror cycle edges and twist
274⍝# corners, D L D' R' D L' D' R and its inverse cycle three bottom
275⍝# corners. 9 to 16: a middle edge brought up from the bottom into each
276⍝# of the four slots, from either side (U R U' R' U' F' U F and its
277⍝# mirror, mirrored the same way and turned about the vertical axis).
278⍝# Each keeps the top layer whole, and each of 1 to 8 the top two
279⍝# layers, so a search over them builds on what is solved (as the
280⍝# endgame's twist does in eigencube.py).
281macros ← (e̲nclose 1 r̲eshape 3) c̲at (e̲nclose 1 r̲eshape 4) c̲at (e̲nclose 3 3) c̲at (e̲nclose 5 11 3 12 4 6) c̲at (e̲nclose 11 3 12 3 11 3 3 12) c̲at (e̲nclose 11 3 3 12 4 11 4 12) c̲at (e̲nclose 3 11 4 10 3 12 4 9) c̲at (e̲nclose 10 3 11 4 9 3 12 4) c̲at (e̲nclose 3 11 4 12 4 6 3 5) c̲at (e̲nclose 3 5 4 6 4 10 3 9) c̲at (e̲nclose 3 9 4 10 4 8 3 7) c̲at (e̲nclose 3 7 4 8 4 12 3 11) c̲at (e̲nclose 4 10 3 9 3 5 4 6) c̲at (e̲nclose 4 8 3 7 3 9 4 10) c̲at (e̲nclose 4 12 3 11 3 7 4 8) c̲at e̲nclose 4 6 3 5 3 11 4 12
282⍝# The macros the middle layer's stages search over: D turns and the
283⍝# insertions.
284middle ← 1 2 3 9 10 11 12 13 14 15 16
285⍝# The macros the bottom layer's stages search over: D turns and the
286⍝# last-layer sequences.
287bottom ← 1 2 3 4 5 6 7 8
288
289⍝# h:a_ctions hybrid s: what stage s searches over: none for the twelve
290⍝# turns (all stages when hybrid is 0, eigencube.py's search alone; the
291⍝# top layer always), else the middle or the bottom layer's macros.
292ʰa̲ctions ← { hybrid s →
293  (hybrid = 0) ∨ s ≤ 9 ? o̲ffsets 0
294  s ≤ 17 ? middle
295  bottom
296}
297
298⍝# h:a_long ms O: the moves ms applied in order to the cubes O (n 26),
299⍝# as orientations.
300ʰa̲long ← { ms O →
301  0 = t̲ally ms ? O
302  (1 d̲rop ms) ʰa̲long ((((f̲irst ms) − 1) × t̲ally O) + r̲ange t̲ally O) s̲elect ʰn̲ext O
303}
304⍝# h:m_acros set O: every macro of the set (indices into macros)
305⍝# applied to every cube of O, macro-major as h:n_ext orders the turns.
306ʰm̲acros ← { set O →
307  0 = t̲ally set ? 0 26 r̲eshape 0
308  ((d̲isclose (f̲irst set) s̲elect macros) ʰa̲long O) c̲at (1 d̲rop set) ʰm̲acros O
309}
310⍝# h:e_xpand set O: the cubes one action from O: the twelve turns for an
311⍝# empty set, else the set's macros.
312ʰe̲xpand ← { set O →
313  0 = t̲ally set ? ʰn̲ext O
314  set ʰm̲acros O
315}
316⍝# h:f_latten acts: macros (indices into macros) as the moves they make.
317ʰf̲latten ← { acts →
318  0 = t̲ally acts ? o̲ffsets 0
319  (d̲isclose (f̲irst acts) s̲elect macros) c̲at ʰf̲latten 1 d̲rop acts
320}
321
322⍝# h:s_tep spec table: one step of the search. The table holds every cube
323⍝# found, a row each: its key, its orientations, the cube it was reached
324⍝# from, the move, its moves from the start g and its priority
325⍝# g + greed * h; then the open cubes, best first. A step takes the best
326⍝# batch open cubes, turns each every way at once, drops a move that
327⍝# undoes the last one or turns two opposite faces out of order (they
328⍝# commute; eigencube.py prunes the same two), and adds the cubes not
329⍝# found before. It stops on a cube that meets the goal, giving the
330⍝# moves to it.
331ʰs̲tep ← { (spec, set) (keys, O, par, mv, g, f, open) →
332  0 = t̲ally open ? "stuck" ⎕S̲IGNAL "the search ran out of cubes"
333  pick ← (batch m̲in t̲ally open) t̲ake open
334  n ← t̲ally pick
335  r ← o̲ffsets n × (t̲ally set) + 12 × 0 = t̲ally set
336  cm ← 1 + r d̲iv n
337  cp ← (1 + r m̲od n) s̲elect pick
338  last ← cp s̲elect mv
339  ok ← w̲here (0 < t̲ally set) ∨ n̲ot (cm = ˡi̲nverse last) ∨ (ʰf̲ace last) = 1 + (ʰf̲ace cm) × 1 = 2 m̲od ʰf̲ace cm
340  KO ← (ʰr̲elevant spec) ʰp̲roject ok s̲elect set ʰe̲xpand pick s̲elect O
341  cp ← ok s̲elect cp
342  cm ← ok s̲elect cm
343  sc ← spec ʰs̲core KO
344  hit ← w̲here sc < 0
345  0 < t̲ally hit ? ((par, mv) ʰt̲race f̲irst hit s̲elect cp) c̲at f̲irst hit s̲elect cm
346  KK ← ʰk̲ey KO
347  new ← w̲here ((KK i̲ndexOf KK) = r̲ange t̲ally KK) ∧ (keys i̲ndexOf KK) > t̲ally keys
348  ng ← 1 + new s̲elect cp s̲elect g
349  f2 ← f c̲at (f̲loat ng) + greed × new s̲elect sc
350  rest ← (batch d̲rop open) c̲at (t̲ally keys) + r̲ange t̲ally new
351  (spec, set) ʰs̲tep (keys c̲at new s̲elect KK, O c̲at new s̲elect KO, par c̲at new s̲elect cp, mv c̲at new s̲elect cm, g c̲at ng, f2, (g̲rade rest s̲elect f2) s̲elect rest)
352}
353
354⍝# h:t_race (par, mv) i: the moves from the start (cube 1) to cube i, by
355⍝# following each cube back to the one it was reached from.
356ʰt̲race ← { (par, mv) i →
357  1 = i ? o̲ffsets 0
358  ((par, mv) ʰt̲race i s̲elect par) c̲at i s̲elect mv
359}
360
361⍝# h:s_earch (spec, set) S: the moves taking the cube S (a batch of one)
362⍝# to the stage's goal, found by h:s_tep from a table holding S alone,
363⍝# over the twelve turns or the set's macros.
364ʰs̲earch ← { (spec, set) S →
365  O ← (ʰr̲elevant spec) ʰp̲roject ʰo̲rient S
366  0 > f̲irst spec ʰs̲core O ? o̲ffsets 0
367  acts ← (spec, set) ʰs̲tep (ʰk̲ey O, O, 1 r̲eshape 0, 1 r̲eshape 0, 1 r̲eshape 0, 1 r̲eshape 0.0, 1 r̲eshape 1)
368  0 = t̲ally set ? acts
369  ʰf̲latten acts s̲elect set
370}
371
372⍝## Solving
373
374⍝# h:s_tage hybrid (S, ms, lens): the next search stage run on the cube
375⍝# S, its moves added to the moves so far ms and its length to the
376⍝# stage lengths (h:a_ctions says what it searches over).
377ʰs̲tage ← { hybrid (S, ms, lens) →
378  s ← 1 + t̲ally lens
379  next ← ((ʰs̲pec s), hybrid ʰa̲ctions s) ʰs̲earch S
380  (next ˡd̲o S, ms c̲at next, lens c̲at t̲ally next)
381}
382
383⍝# The endgame's twist: L' U' L U, twice (eigencube.py's routine).
384twist ← 12 2 11 1 12 2 11 1
385⍝# The bottom turn eigencube.py makes between corners, D' here.
386bottomTurn ← 1 r̲eshape 4
387
388⍝# h:o_riented? S: whether the corner at front-left-bottom, (1 -1 -1),
389⍝# has its yellow sticker down, so that turns of the bottom alone solve
390⍝# it (eigencube.py's is_corner_oriented): its rotation fixes z.
391ʰo̲riented? ← { S →
392  k ← (26 3 r̲eshape ʰp̲os S) i̲ndexOf 1 -1 -1
393  (k s̲elect r̲avel ʰo̲rient S) s̲elect yellowDown
394}
395
396⍝# h:c_orner (S, ms): twist the front-left-bottom corner until it is
397⍝# oriented, then turn the bottom to bring the next corner there.
398ʰc̲orner ← { (S, ms) →
399  ʰo̲riented? S ? (bottomTurn ˡd̲o S, ms c̲at bottomTurn)
400  ʰc̲orner (twist ˡd̲o S, ms c̲at twist)
401}
402
403⍝# h:f_inish (S, ms): turn the bottom until the cube is solved.
404ʰf̲inish ← { (S, ms) →
405  ˡs̲olved? S ? (S, ms)
406  ʰf̲inish (bottomTurn ˡd̲o S, ms c̲at bottomTurn)
407}
408
409⍝# l:s_olve hybrid S: a solution of the cube S (a batch of one), after
410⍝# eigencube.py's solve: 29 search stages (the top and middle layers a
411⍝# cubelet at a time, then the bottom edges and the bottom corners'
412⍝# places), then the endgame's corner twists. With hybrid 1 the middle
413⍝# and bottom stages search over macros, as a person solving by hand
414⍝# uses known sequences (seconds); with 0 every stage searches the
415⍝# twelve turns, eigencube.py's search alone (minutes in X_eTaL). The
416⍝# moves, each stage's length, and the endgame's length.
417ˡs̲olve ← { hybrid S →
418  (S1, ms, lens) ← 29 '{ st → hybrid ʰs̲tage st } p̲ower (S, o̲ffsets 0, o̲ffsets 0)
419  (_, all) ← ʰf̲inish 4 'ʰc̲orner p̲ower (S1, ms)
420  (all, lens, (t̲ally all) − t̲ally ms)
421}
422
423⍝## Notation
424
425⍝# l:n_ame ms: moves as text in the usual notation, U for the top face
426⍝# clockwise, U' counterclockwise, separated by spaces.
427ˡn̲ame ← { ms →
428  n ← t̲ally ms
429  marks ← (1 + ms m̲od 2) s̲elect "' "
430  txt ← r̲avel o̲\ (3 c̲at n) r̲eshape ((ʰf̲ace ms) s̲elect ˡfaces) c̲at marks c̲at n r̲eshape " "
431  -1 d̲rop (r̲avel o̲\ (3 c̲at n) r̲eshape (n r̲eshape 1) c̲at (marks = f̲irst "'") c̲at n r̲eshape 1) r̲eplicate txt
432}
433
434⍝# ec:p_arse t: moves written in the usual notation as numbers: each
435⍝# letter of ec:faces is a move, counterclockwise when a ' follows it;
436⍝# anything else between moves is ignored. The inverse of ec:n_ame.
437⍝# >> "ec:" u_se< "Eigencube"
438⍝# >> ec:p_arse "U R' F B'"
439⍝# 1 10 5 8
440⍝# >> (ec:p_arse ec:n_ame 3 12 7) m_atch 3 12 7
441⍝# 1
442ˡp̲arse ← { t →
443  at ← w̲here t m̲ember? ˡfaces
444  f ← ˡfaces i̲ndexOf at s̲elect t
445  (2 × f) − n̲ot ((1 + at) s̲elect t c̲at " ") = f̲irst "'"
446}