moves.c (6797B)
1 #define MOVES_C 2 3 #include "moves.h" 4 5 /* Local functions ***********************************************************/ 6 7 static void cleanup_aux(Alg *alg, Alg *ret, bool inv); 8 9 /* Tables and other data *****************************************************/ 10 11 /* Moves are represented as cubes and applied using compose(). Every move is * 12 * translated to a an <U, x, y> alg before filling the transition tables. * 13 * See init_moves(). */ 14 15 static Cube move_array[NMOVES]; 16 17 static char equiv_alg_string[100][NMOVES] = { 18 [NULLMOVE] = "", 19 20 [U] = " U ", 21 [U2] = " UU ", 22 [U3] = " UUU ", 23 [D] = " xx U xx ", 24 [D2] = " xx UU xx ", 25 [D3] = " xx UUU xx ", 26 [R] = " yx U xxxyyy ", 27 [R2] = " yx UU xxxyyy ", 28 [R3] = " yx UUU xxxyyy ", 29 [L] = " yyyx U xxxy ", 30 [L2] = " yyyx UU xxxy ", 31 [L3] = " yyyx UUU xxxy ", 32 [F] = " x U xxx ", 33 [F2] = " x UU xxx ", 34 [F3] = " x UUU xxx ", 35 [B] = " xxx U x ", 36 [B2] = " xxx UU x ", 37 [B3] = " xxx UUU x ", 38 39 [Uw] = " xx U xx y ", 40 [Uw2] = " xx UU xx yy ", 41 [Uw3] = " xx UUU xx yyy ", 42 [Dw] = " U yyy ", 43 [Dw2] = " UU yy ", 44 [Dw3] = " UUU y ", 45 [Rw] = " yyyx U xxxy x ", 46 [Rw2] = " yyyx UU xxxy xx ", 47 [Rw3] = " yyyx UUU xxxy xxx ", 48 [Lw] = " yx U xxxyyy xxx ", 49 [Lw2] = " yx UU xxxyyy xx ", 50 [Lw3] = " yx UUU xxxyyy x ", 51 [Fw] = " xxx U x yxxxyyy ", 52 [Fw2] = " xxx UU x yxxyyy ", 53 [Fw3] = " xxx UUU x yxyyy ", 54 [Bw] = " x U xxx yxyyy ", 55 [Bw2] = " x UU xxx yxxyyy ", 56 [Bw3] = " x UUU xxx yxxxyyy ", 57 58 [M] = " yx U xx UUU yxyyy ", 59 [M2] = " yx UU xx UU xxxy ", 60 [M3] = " yx UUU xx U yxxxy ", 61 [S] = " x UUU xx U yyyx ", 62 [S2] = " x UU xx UU yyx ", 63 [S3] = " x U xx UUU yx ", 64 [E] = " U xx UUU xxyyy ", 65 [E2] = " UU xx UU xxyy ", 66 [E3] = " UUU xx U xxy ", 67 68 [x] = " x ", 69 [x2] = " xx ", 70 [x3] = " xxx ", 71 [y] = " y ", 72 [y2] = " yy ", 73 [y3] = " yyy ", 74 [z] = " yyy x y ", 75 [z2] = " yy xx ", 76 [z3] = " y x yyy " 77 }; 78 79 80 /* Public functions **********************************************************/ 81 82 void 83 apply_alg(Alg *alg, Cube *cube) 84 { 85 Cube aux; 86 int i; 87 88 copy_cube(cube, &aux); 89 make_solved(cube); 90 91 for (i = 0; i < alg->len; i++) 92 if (alg->inv[i]) 93 apply_move(alg->move[i], cube); 94 95 invert_cube(cube); 96 compose(&aux, cube); 97 98 for (i = 0; i < alg->len; i++) 99 if (!alg->inv[i]) 100 apply_move(alg->move[i], cube); 101 } 102 103 void 104 apply_move(Move m, Cube *cube) 105 { 106 compose(&move_array[m], cube); 107 } 108 109 void 110 apply_move_centers(Move m, Cube *cube) 111 { 112 compose_centers(&move_array[m], cube); 113 } 114 115 void 116 apply_move_corners(Move m, Cube *cube) 117 { 118 compose_corners(&move_array[m], cube); 119 } 120 121 void 122 apply_move_edges(Move m, Cube *cube) 123 { 124 compose_edges(&move_array[m], cube); 125 } 126 127 Alg * 128 cleanup(Alg *alg) 129 { 130 int i, j, k, b[2], n, L; 131 Move bb, m; 132 Alg *ret; 133 134 ret = new_alg(""); 135 cleanup_aux(alg, ret, false); 136 cleanup_aux(alg, ret, true); 137 138 do { 139 for (i = 0, j = 0, n = 0; i < ret->len; i = j) { 140 if (ret->move[i] > B3) { 141 ret->move[n] = ret->move[i]; 142 ret->inv[n] = ret->inv[i]; 143 n++; 144 j++; 145 continue; 146 } 147 148 bb = 1 + ((base_move(ret->move[i]) - 1)/6)*6; 149 while (j < ret->len && 150 ret->move[j] <= B3 && 151 ret->inv[j] == ret->inv[i] && 152 1 + ((base_move(ret->move[j]) - 1)/6)*6 == bb) 153 j++; 154 155 for (k = i, b[0] = 0, b[1] = 0; k < j; k++) { 156 m = ret->move[k]; 157 if (base_move(m) == bb) 158 b[0] = (b[0]+1+m-base_move(m)) % 4; 159 else 160 b[1] = (b[1]+1+m-base_move(m)) % 4; 161 } 162 163 for (k = 0; k < 2; k++) { 164 if (b[k] != 0) { 165 ret->move[n] = bb + b[k] - 1 + 3*k; 166 ret->inv[n] = ret->inv[i]; 167 n++; 168 } 169 } 170 } 171 172 L = ret->len; 173 ret->len = n; 174 } while (L != n); 175 176 return ret; 177 } 178 179 static void 180 cleanup_aux(Alg *alg, Alg *ret, bool inv) 181 { 182 int i, j; 183 Cube c, d; 184 Move m; 185 Alg *equiv_alg; 186 187 make_solved(&c); 188 for (i = 0; i < alg->len; i++) { 189 if (alg->inv[i] != inv) 190 continue; 191 192 equiv_alg = new_alg(equiv_alg_string[alg->move[i]]); 193 194 for (j = 0; j < equiv_alg->len; j++) 195 if (equiv_alg->move[j] == U) 196 append_move(ret, 3 * c.xp[U_center] + 1, inv); 197 else 198 apply_move(equiv_alg->move[j], &c); 199 200 free_alg(equiv_alg); 201 } 202 203 m = NULLMOVE; 204 switch (c.xp[F_center]) { 205 case U_center: 206 m = x3; 207 break; 208 case D_center: 209 m = x; 210 break; 211 case R_center: 212 m = y; 213 break; 214 case L_center: 215 m = y3; 216 break; 217 case B_center: 218 if (c.xp[U_center] == U_center) 219 m = y2; 220 else 221 m = x2; 222 break; 223 default: 224 break; 225 } 226 227 make_solved(&d); 228 apply_move(m, &d); 229 if (m != NULLMOVE) 230 append_move(ret, m, inv); 231 232 m = NULLMOVE; 233 if (c.xp[U_center] == d.xp[D_center]) { 234 m = z2; 235 } else if (c.xp[U_center] == d.xp[R_center]) { 236 m = z3; 237 } else if (c.xp[U_center] == d.xp[L_center]) { 238 m = z; 239 } 240 if (m != NULLMOVE) 241 append_move(ret, m, inv); 242 } 243 244 void 245 init_moves() { 246 static bool initialized = false; 247 if (initialized) 248 return; 249 initialized = true; 250 251 Move m; 252 Alg *equiv_alg[NMOVES]; 253 254 static const Cube mcu = { 255 .ep = { UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR }, 256 .cp = { UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR }, 257 }; 258 static const Cube mcx = { 259 .ep = { DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR }, 260 .eo = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 }, 261 .cp = { DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR }, 262 .co = { [UFR] = 2, [UBR] = 1, [UFL] = 1, [UBL] = 2, 263 [DBR] = 2, [DFR] = 1, [DBL] = 1, [DFL] = 2 }, 264 .xp = { F_center, B_center, R_center, 265 L_center, D_center, U_center }, 266 }; 267 static const Cube mcy = { 268 .ep = { UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL }, 269 .eo = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 }, 270 .cp = { UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL }, 271 .xp = { U_center, D_center, B_center, 272 F_center, R_center, L_center }, 273 }; 274 275 move_array[U] = mcu; 276 move_array[x] = mcx; 277 move_array[y] = mcy; 278 279 for (m = 0; m < NMOVES; m++) 280 equiv_alg[m] = new_alg(equiv_alg_string[m]); 281 282 for (m = 0; m < NMOVES; m++) { 283 switch (m) { 284 case NULLMOVE: 285 make_solved(&move_array[m]); 286 break; 287 case U: 288 case x: 289 case y: 290 break; 291 default: 292 make_solved(&move_array[m]); 293 apply_alg(equiv_alg[m], &move_array[m]); 294 break; 295 } 296 } 297 298 for (m = 0; m < NMOVES; m++) 299 free_alg(equiv_alg[m]); 300 } 301