-
Notifications
You must be signed in to change notification settings - Fork 94
/
coord.py
223 lines (200 loc) · 10.4 KB
/
coord.py
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
217
218
219
220
221
222
223
# ##### The cube on the coordinate level. It is described by a 3-tuple of natural numbers in phase 1 and phase 2. ######
from os import path
import array as ar
import cubie as cb
import enums
import moves as mv
import pruning as pr
import symmetries as sy
from defs import FOLDER, N_U_EDGES_PHASE2, N_PERM_4, N_CHOOSE_8_4, N_FLIP, N_TWIST, N_UD_EDGES, N_MOVE
from enums import Edge as Ed
SOLVED = 0 # 0 is index of solved state (except for u_edges coordinate)
u_edges_plus_d_edges_to_ud_edges = None # global variable
class CoordCube:
"""Represent a cube on the coordinate level.
In phase 1 a state is uniquely determined by the three coordinates flip, twist and slice = slicesorted // 24.
In phase 2 a state is uniquely determined by the three coordinates corners, ud_edges and slice_sorted % 24.
"""
def __init__(self, cc=None):
"""
Create cube on coordinate level from Id-cube of from CubieCube
:param cc: The CubieCube
"""
if cc is None:
self.twist = SOLVED # twist of corners
self.flip = SOLVED # flip of edges
self.slice_sorted = SOLVED # Position of FR, FL, BL, BR edges. Valid in phase 1 (<11880) and phase 2 (<24)
# The phase 1 slice coordinate is given by slice_sorted // 24
self.u_edges = 1656 # Valid in phase 1 (<11880) and phase 2 (<1680). 1656 is the index of solved u_edges.
self.d_edges = SOLVED # Valid in phase 1 (<11880) and phase 2 (<1680)
self.corners = SOLVED # corner permutation. Valid in phase1 and phase2
self.ud_edges = SOLVED # permutation of the ud-edges. Valid only in phase 2
else:
self.twist = cc.get_twist()
self.flip = cc.get_flip()
self.slice_sorted = cc.get_slice_sorted()
self.u_edges = cc.get_u_edges()
self.d_edges = cc.get_d_edges()
self.corners = cc.get_corners()
if self.slice_sorted < N_PERM_4: # phase 2 cube
self.ud_edges = cc.get_ud_edges()
else:
self.ud_edges = -1 # invalid
# symmetry reduced flipslice coordinate used in phase 1
self.flipslice_classidx = sy.flipslice_classidx[N_FLIP * (self.slice_sorted // N_PERM_4) + self.flip]
self.flipslice_sym = sy.flipslice_sym[N_FLIP * (self.slice_sorted // N_PERM_4) + self.flip]
self.flipslice_rep = sy.flipslice_rep[self.flipslice_classidx]
# symmetry reduced corner permutation coordinate used in phase 2
self.corner_classidx = sy.corner_classidx[self.corners]
self.corner_sym = sy.corner_sym[self.corners]
self.corner_rep = sy.corner_rep[self.corner_classidx]
def __str__(self):
s = '(twist: ' + str(self.twist) + ', flip: ' + str(self.flip) + ', slice: ' + str(self.slice_sorted // 24) + \
', U-edges: ' + str(self.u_edges) + ', D-edges: ' + str(self.d_edges) + ', E-edges: ' \
+ str(self.slice_sorted) + ', Corners: ' + str(self.corners) + ', UD-Edges : ' + str(self.ud_edges) + ')'
s = s + '\n' + str(self.flipslice_classidx) + ' ' + str(self.flipslice_sym) + ' ' + str(self.flipslice_rep)
s = s + '\n' + str(self.corner_classidx) + ' ' + str(self.corner_sym) + ' ' + str(self.corner_rep)
return s
def phase1_move(self, m):
"""
Update phase 1 coordinates when move is applied.
:param m: The move
"""
self.twist = mv.twist_move[N_MOVE * self.twist + m]
self.flip = mv.flip_move[N_MOVE * self.flip + m]
self.slice_sorted = mv.slice_sorted_move[N_MOVE * self.slice_sorted + m]
# optional:
self.u_edges = mv.u_edges_move[N_MOVE * self.u_edges + m] # u_edges and d_edges retrieve ud_edges easily
self.d_edges = mv.d_edges_move[N_MOVE * self.d_edges + m] # if phase 1 is finished and phase 2 starts
self.corners = mv.corners_move[N_MOVE * self.corners + m] # Is needed only in phase 2
self.flipslice_classidx = sy.flipslice_classidx[N_FLIP * (self.slice_sorted // N_PERM_4) + self.flip]
self.flipslice_sym = sy.flipslice_sym[N_FLIP * (self.slice_sorted // N_PERM_4) + self.flip]
self.flipslice_rep = sy.flipslice_rep[self.flipslice_classidx]
self.corner_classidx = self.corner_classidx = sy.corner_classidx[self.corners]
self.corner_sym = sy.corner_sym[self.corners]
self.corner_rep = sy.corner_rep[self.corner_classidx]
def phase2_move(self, m):
"""
Update phase 2 coordinates when move is applied.
:param m: The move
"""
self.slice_sorted = mv.slice_sorted_move[N_MOVE * self.slice_sorted + m]
self.corners = mv.corners_move[N_MOVE * self.corners + m]
self.ud_edges = mv.ud_edges_move[N_MOVE * self.ud_edges + m]
def get_depth_phase1(self):
"""
Compute the distance to the cube subgroup H where flip=slice=twist=0
:return: The distance to H
"""
slice_ = self.slice_sorted // N_PERM_4
flip = self.flip
twist = self.twist
flipslice = N_FLIP * slice_ + flip
classidx = sy.flipslice_classidx[flipslice]
sym = sy.flipslice_sym[flipslice]
depth_mod3 = pr.get_flipslice_twist_depth3(N_TWIST * classidx + sy.twist_conj[(twist << 4) + sym])
depth = 0
while flip != SOLVED or slice_ != SOLVED or twist != SOLVED:
if depth_mod3 == 0:
depth_mod3 = 3
for m in enums.Move:
twist1 = mv.twist_move[N_MOVE * twist + m]
flip1 = mv.flip_move[N_MOVE * flip + m]
slice1 = mv.slice_sorted_move[N_MOVE * slice_ * N_PERM_4 + m] // N_PERM_4
flipslice1 = N_FLIP * slice1 + flip1
classidx1 = sy.flipslice_classidx[flipslice1]
sym = sy.flipslice_sym[flipslice1]
if pr.get_flipslice_twist_depth3(
N_TWIST * classidx1 + sy.twist_conj[(twist1 << 4) + sym]) == depth_mod3 - 1:
depth += 1
twist = twist1
flip = flip1
slice_ = slice1
depth_mod3 -= 1
break
return depth
@staticmethod
def get_depth_phase2(corners, ud_edges):
"""
Get distance to subgroup where only the UD-slice edges may be permuted in their slice (only 24/2 = 12 possible
ways due to overall even parity). This is a lower bound for the number of moves to solve phase 2.
:param corners: Corners coordinate
:param ud_edges: Coordinate of the 8 edges of U and D face.
:return:
"""
classidx = sy.corner_classidx[corners]
sym = sy.corner_sym[corners]
depth_mod3 = pr.get_corners_ud_edges_depth3(N_UD_EDGES * classidx + sy.ud_edges_conj[(ud_edges << 4) + sym])
if depth_mod3 == 3: # unfilled entry, depth >= 11
return 11
depth = 0
while corners != SOLVED or ud_edges != SOLVED:
if depth_mod3 == 0:
depth_mod3 = 3
# only iterate phase 2 moves
for m in (enums.Move.U1, enums.Move.U2, enums.Move.U3, enums.Move.R2, enums.Move.F2, enums.Move.D1,
enums.Move.D2, enums.Move.D3, enums.Move.L2, enums.Move.B2):
corners1 = mv.corners_move[N_MOVE * corners + m]
ud_edges1 = mv.ud_edges_move[N_MOVE * ud_edges + m]
classidx1 = sy.corner_classidx[corners1]
sym = sy.corner_sym[corners1]
if pr.get_corners_ud_edges_depth3(
N_UD_EDGES * classidx1 + sy.ud_edges_conj[(ud_edges1 << 4) + sym]) == depth_mod3 - 1:
depth += 1
corners = corners1
ud_edges = ud_edges1
depth_mod3 -= 1
break
return depth
def create_phase2_edgemerge_table():
"""phase2_edgemerge retrieves the initial phase 2 ud_edges coordinate from the u_edges and d_edges coordinates."""
fname = "phase2_edgemerge"
global u_edges_plus_d_edges_to_ud_edges
c_u = cb.CubieCube()
c_d = cb.CubieCube()
c_ud = cb.CubieCube()
edge_u = [Ed.UR, Ed.UF, Ed.UL, Ed.UB]
edge_d = [Ed.DR, Ed.DF, Ed.DL, Ed.DB]
edge_ud = [Ed.UR, Ed.UF, Ed.UL, Ed.UB, Ed.DR, Ed.DF, Ed.DL, Ed.DB]
if not path.isfile(path.join(FOLDER, fname)):
cnt = 0
print("creating " + fname + " table...")
u_edges_plus_d_edges_to_ud_edges = ar.array('H', [0 for _ in range(N_U_EDGES_PHASE2 * N_PERM_4)])
for i in range(N_U_EDGES_PHASE2):
c_u.set_u_edges(i)
for j in range(N_CHOOSE_8_4):
c_d.set_d_edges(j * N_PERM_4)
invalid = False
for e in edge_ud:
c_ud.ep[e] = -1 # invalidate edges
if c_u.ep[e] in edge_u:
c_ud.ep[e] = c_u.ep[e]
if c_d.ep[e] in edge_d:
c_ud.ep[e] = c_d.ep[e]
if c_ud.ep[e] == -1:
invalid = True # edge collision
break
if not invalid:
for k in range(N_PERM_4):
c_d.set_d_edges(j * N_PERM_4 + k)
for e in edge_ud:
if c_u.ep[e] in edge_u:
c_ud.ep[e] = c_u.ep[e]
if c_d.ep[e] in edge_d:
c_ud.ep[e] = c_d.ep[e]
u_edges_plus_d_edges_to_ud_edges[N_PERM_4 * i + k] = c_ud.get_ud_edges()
cnt += 1
if cnt % 2000 == 0:
print('.', end='', flush=True)
print()
fh = open(path.join(FOLDER, fname), "wb")
u_edges_plus_d_edges_to_ud_edges.tofile(fh)
fh.close()
print()
else:
print("loading " + fname + " table...")
fh = open(path.join(FOLDER, fname), "rb")
u_edges_plus_d_edges_to_ud_edges = ar.array('H')
u_edges_plus_d_edges_to_ud_edges.fromfile(fh, N_U_EDGES_PHASE2 * N_PERM_4)
########################################################################################################################
create_phase2_edgemerge_table()