moves.c (13719B)
1 #include "moves.h" 2 3 /* Local functions ***********************************************************/ 4 5 static Cube apply_move_cubearray(Move m, Cube cube, PieceFilter f); 6 static void cleanup_aux(Alg *alg, Alg *ret, bool inv); 7 static bool read_mtables_file(void); 8 static bool write_mtables_file(void); 9 10 /* Tables and other data *****************************************************/ 11 12 /* Every move is translated to a an <U, x, y> alg before filling the 13 transition tables, see init_moves() */ 14 15 static int edge_cycle[NMOVES][12] = 16 { 17 [U] = { UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR }, 18 [x] = { DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR }, 19 [y] = { UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL } 20 }; 21 22 static int corner_cycle[NMOVES][8] = 23 { 24 [U] = { UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR }, 25 [x] = { DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR }, 26 [y] = { UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL } 27 }; 28 29 static int center_cycle[NMOVES][6] = 30 { 31 [x] = { F_center, B_center, R_center, L_center, D_center, U_center }, 32 [y] = { U_center, D_center, B_center, F_center, R_center, L_center } 33 }; 34 35 static int eofb_flipped[NMOVES][12] = { 36 [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 }, 37 [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 } 38 }; 39 40 static int eorl_flipped[NMOVES][12] = { 41 [x] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, 42 [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 } 43 }; 44 45 static int eoud_flipped[NMOVES][12] = { 46 [U] = { [UF] = 1, [UL] = 1, [UB] = 1, [UR] = 1 }, 47 [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 }, 48 [y] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } 49 }; 50 51 static int coud_flipped[NMOVES][8] = { 52 [x] = { 53 [UFR] = 2, [UBR] = 1, [UFL] = 1, [UBL] = 2, 54 [DBR] = 2, [DFR] = 1, [DBL] = 1, [DFL] = 2 55 } 56 }; 57 58 static int corl_flipped[NMOVES][8] = { 59 [U] = { [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2 }, 60 [y] = { 61 [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2, 62 [DFR] = 2, [DBR] = 1, [DBL] = 2, [DFL] = 1 63 } 64 }; 65 66 static int cofb_flipped[NMOVES][8] = { 67 [U] = { [UFR] = 2, [UBR] = 1, [UBL] = 2, [UFL] = 1 }, 68 [x] = { 69 [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2, 70 [DFR] = 2, [DBR] = 1, [DBL] = 2, [DFL] = 1 71 }, 72 [y] = { 73 [UFR] = 2, [UBR] = 1, [UBL] = 2, [UFL] = 1, 74 [DFR] = 1, [DBR] = 2, [DBL] = 1, [DFL] = 2 75 } 76 }; 77 78 static char equiv_alg_string[100][NMOVES] = { 79 [NULLMOVE] = "", 80 81 [U] = " U ", 82 [U2] = " UU ", 83 [U3] = " UUU ", 84 [D] = " xx U xx ", 85 [D2] = " xx UU xx ", 86 [D3] = " xx UUU xx ", 87 [R] = " yx U xxxyyy ", 88 [R2] = " yx UU xxxyyy ", 89 [R3] = " yx UUU xxxyyy ", 90 [L] = " yyyx U xxxy ", 91 [L2] = " yyyx UU xxxy ", 92 [L3] = " yyyx UUU xxxy ", 93 [F] = " x U xxx ", 94 [F2] = " x UU xxx ", 95 [F3] = " x UUU xxx ", 96 [B] = " xxx U x ", 97 [B2] = " xxx UU x ", 98 [B3] = " xxx UUU x ", 99 100 [Uw] = " xx U xx y ", 101 [Uw2] = " xx UU xx yy ", 102 [Uw3] = " xx UUU xx yyy ", 103 [Dw] = " U yyy ", 104 [Dw2] = " UU yy ", 105 [Dw3] = " UUU y ", 106 [Rw] = " yyyx U xxxy x ", 107 [Rw2] = " yyyx UU xxxy xx ", 108 [Rw3] = " yyyx UUU xxxy xxx ", 109 [Lw] = " yx U xxxyyy xxx ", 110 [Lw2] = " yx UU xxxyyy xx ", 111 [Lw3] = " yx UUU xxxyyy x ", 112 [Fw] = " xxx U x yxxxyyy ", 113 [Fw2] = " xxx UU x yxxyyy ", 114 [Fw3] = " xxx UUU x yxyyy ", 115 [Bw] = " x U xxx yxyyy ", 116 [Bw2] = " x UU xxx yxxyyy ", 117 [Bw3] = " x UUU xxx yxxxyyy ", 118 119 [M] = " yx U xx UUU yxyyy ", 120 [M2] = " yx UU xx UU xxxy ", 121 [M3] = " yx UUU xx U yxxxy ", 122 [S] = " x UUU xx U yyyx ", 123 [S2] = " x UU xx UU yyx ", 124 [S3] = " x U xx UUU yx ", 125 [E] = " U xx UUU xxyyy ", 126 [E2] = " UU xx UU xxyy ", 127 [E3] = " UUU xx U xxy ", 128 129 [x] = " x ", 130 [x2] = " xx ", 131 [x3] = " xxx ", 132 [y] = " y ", 133 [y2] = " yy ", 134 [y3] = " yyy ", 135 [z] = " yyy x y ", 136 [z2] = " yy xx ", 137 [z3] = " y x yyy " 138 }; 139 140 /* Transition tables, to be loaded up at the beginning */ 141 int epose_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; 142 int eposs_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; 143 int eposm_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; 144 int eofb_mtable[NMOVES][POW2TO11]; 145 int eorl_mtable[NMOVES][POW2TO11]; 146 int eoud_mtable[NMOVES][POW2TO11]; 147 int cp_mtable[NMOVES][FACTORIAL8]; 148 int coud_mtable[NMOVES][POW3TO7]; 149 int cofb_mtable[NMOVES][POW3TO7]; 150 int corl_mtable[NMOVES][POW3TO7]; 151 int cpos_mtable[NMOVES][FACTORIAL6]; 152 153 154 /* Local functions implementation ********************************************/ 155 156 static Cube 157 apply_move_cubearray(Move m, Cube cube, PieceFilter f) 158 { 159 /*init_moves();*/ 160 161 CubeArray m_arr = { 162 edge_cycle[m], 163 eofb_flipped[m], 164 eorl_flipped[m], 165 eoud_flipped[m], 166 corner_cycle[m], 167 coud_flipped[m], 168 corl_flipped[m], 169 cofb_flipped[m], 170 center_cycle[m] 171 }; 172 173 return move_via_arrays(&m_arr, cube, f); 174 } 175 176 /* Public functions **********************************************************/ 177 178 Cube 179 apply_alg_generic(Alg *alg, Cube c, PieceFilter f, bool a) 180 { 181 Cube ret = {0}; 182 int i; 183 184 for (i = 0; i < alg->len; i++) 185 if (alg->inv[i]) 186 ret = a ? apply_move(alg->move[i], ret) : 187 apply_move_cubearray(alg->move[i], ret, f); 188 189 ret = compose_filtered(c, inverse_cube(ret), f); 190 191 for (i = 0; i < alg->len; i++) 192 if (!alg->inv[i]) 193 ret = a ? apply_move(alg->move[i], ret) : 194 apply_move_cubearray(alg->move[i], ret, f); 195 196 return ret; 197 } 198 199 Cube 200 apply_alg(Alg *alg, Cube cube) 201 { 202 return apply_alg_generic(alg, cube, pf_all, true); 203 } 204 205 Cube 206 apply_move(Move m, Cube cube) 207 { 208 /*init_moves();*/ 209 210 return (Cube) { 211 .epose = epose_mtable[m][cube.epose], 212 .eposs = eposs_mtable[m][cube.eposs], 213 .eposm = eposm_mtable[m][cube.eposm], 214 .eofb = eofb_mtable[m][cube.eofb], 215 .eorl = eorl_mtable[m][cube.eorl], 216 .eoud = eoud_mtable[m][cube.eoud], 217 .coud = coud_mtable[m][cube.coud], 218 .cofb = cofb_mtable[m][cube.cofb], 219 .corl = corl_mtable[m][cube.corl], 220 .cp = cp_mtable[m][cube.cp], 221 .cpos = cpos_mtable[m][cube.cpos] 222 }; 223 } 224 225 Alg * 226 cleanup(Alg *alg) 227 { 228 int i, j, k, b[2], n, L; 229 Move bb, m; 230 Alg *ret; 231 232 ret = new_alg(""); 233 cleanup_aux(alg, ret, false); 234 cleanup_aux(alg, ret, true); 235 236 do { 237 for (i = 0, j = 0, n = 0; i < ret->len; i = j) { 238 if (ret->move[i] > B3) { 239 ret->move[n] = ret->move[i]; 240 ret->inv[n] = ret->inv[i]; 241 n++; 242 j++; 243 continue; 244 } 245 246 bb = 1 + ((base_move(ret->move[i]) - 1)/6)*6; 247 while (j < ret->len && 248 ret->move[j] <= B3 && 249 ret->inv[j] == ret->inv[i] && 250 1 + ((base_move(ret->move[j]) - 1)/6)*6 == bb) 251 j++; 252 253 for (k = i, b[0] = 0, b[1] = 0; k < j; k++) { 254 m = ret->move[k]; 255 if (base_move(m) == bb) 256 b[0] = (b[0]+1+m-base_move(m)) % 4; 257 else 258 b[1] = (b[1]+1+m-base_move(m)) % 4; 259 } 260 261 for (k = 0; k < 2; k++) { 262 if (b[k] != 0) { 263 ret->move[n] = bb + b[k] - 1 + 3*k; 264 ret->inv[n] = ret->inv[i]; 265 n++; 266 } 267 } 268 } 269 270 L = ret->len; 271 ret->len = n; 272 } while (L != n); 273 274 return ret; 275 } 276 277 static void 278 cleanup_aux(Alg *alg, Alg *ret, bool inv) 279 { 280 int i, j; 281 Cube c, d; 282 Move m, mm; 283 Alg *equiv_alg; 284 285 c = (Cube){0}; 286 for (i = 0; i < alg->len; i++) { 287 if (alg->inv[i] != inv) 288 continue; 289 290 equiv_alg = new_alg(equiv_alg_string[alg->move[i]]); 291 292 for (j = 0; j < equiv_alg->len; j++) { 293 m = equiv_alg->move[j]; 294 if (m == U) { 295 mm = 3*what_center_at(c, U_center) + 1; 296 append_move(ret, mm, inv); 297 } else { 298 c = apply_move(m, c); 299 } 300 } 301 302 free_alg(equiv_alg); 303 } 304 305 m = NULLMOVE; 306 switch (what_center_at(c, F_center)) { 307 case U_center: 308 m = x3; 309 break; 310 case D_center: 311 m = x; 312 break; 313 case R_center: 314 m = y; 315 break; 316 case L_center: 317 m = y3; 318 break; 319 case B_center: 320 if (what_center_at(c, U_center) == U_center) 321 m = y2; 322 else 323 m = x2; 324 break; 325 default: 326 break; 327 } 328 d = apply_move(m, (Cube){0}); 329 if (m != NULLMOVE) 330 append_move(ret, m, inv); 331 332 m = NULLMOVE; 333 if (what_center_at(c, U_center) == what_center_at(d, D_center)) { 334 m = z2; 335 } else if (what_center_at(c, U_center) == what_center_at(d, R_center)) { 336 m = z3; 337 } else if (what_center_at(c, U_center) == what_center_at(d, L_center)) { 338 m = z; 339 } 340 if (m != NULLMOVE) 341 append_move(ret, m, inv); 342 } 343 344 static bool 345 read_mtables_file(void) 346 { 347 init_env(); 348 349 FILE *f; 350 char fname[strlen(tabledir)+20]; 351 int m, b = sizeof(int); 352 bool r = true; 353 354 /* Table sizes, used for reading and writing files */ 355 uint64_t me[11] = { 356 [0] = FACTORIAL12/FACTORIAL8, 357 [1] = FACTORIAL12/FACTORIAL8, 358 [2] = FACTORIAL12/FACTORIAL8, 359 [3] = POW2TO11, 360 [4] = POW2TO11, 361 [5] = POW2TO11, 362 [6] = FACTORIAL8, 363 [7] = POW3TO7, 364 [8] = POW3TO7, 365 [9] = POW3TO7, 366 [10] = FACTORIAL6 367 }; 368 369 strcpy(fname, tabledir); 370 strcat(fname, "/mtables"); 371 372 if ((f = fopen(fname, "rb")) == NULL) 373 return false; 374 375 for (m = 0; m < NMOVES; m++) { 376 r = r && fread(epose_mtable[m], b, me[0], f) == me[0]; 377 r = r && fread(eposs_mtable[m], b, me[1], f) == me[1]; 378 r = r && fread(eposm_mtable[m], b, me[2], f) == me[2]; 379 r = r && fread(eofb_mtable[m], b, me[3], f) == me[3]; 380 r = r && fread(eorl_mtable[m], b, me[4], f) == me[4]; 381 r = r && fread(eoud_mtable[m], b, me[5], f) == me[5]; 382 r = r && fread(cp_mtable[m], b, me[6], f) == me[6]; 383 r = r && fread(coud_mtable[m], b, me[7], f) == me[7]; 384 r = r && fread(corl_mtable[m], b, me[8], f) == me[8]; 385 r = r && fread(cofb_mtable[m], b, me[9], f) == me[9]; 386 r = r && fread(cpos_mtable[m], b, me[10], f) == me[10]; 387 } 388 389 fclose(f); 390 return r; 391 } 392 393 static bool 394 write_mtables_file(void) 395 { 396 init_env(); 397 398 FILE *f; 399 char fname[strlen(tabledir)+20]; 400 int m, b = sizeof(int); 401 bool r = true; 402 403 /* Table sizes, used for reading and writing files */ 404 uint64_t me[11] = { 405 [0] = FACTORIAL12/FACTORIAL8, 406 [1] = FACTORIAL12/FACTORIAL8, 407 [2] = FACTORIAL12/FACTORIAL8, 408 [3] = POW2TO11, 409 [4] = POW2TO11, 410 [5] = POW2TO11, 411 [6] = FACTORIAL8, 412 [7] = POW3TO7, 413 [8] = POW3TO7, 414 [9] = POW3TO7, 415 [10] = FACTORIAL6 416 }; 417 418 strcpy(fname, tabledir); 419 strcat(fname, "/mtables"); 420 421 if ((f = fopen(fname, "wb")) == NULL) 422 return false; 423 424 for (m = 0; m < NMOVES; m++) { 425 r = r && fwrite(epose_mtable[m], b, me[0], f) == me[0]; 426 r = r && fwrite(eposs_mtable[m], b, me[1], f) == me[1]; 427 r = r && fwrite(eposm_mtable[m], b, me[2], f) == me[2]; 428 r = r && fwrite(eofb_mtable[m], b, me[3], f) == me[3]; 429 r = r && fwrite(eorl_mtable[m], b, me[4], f) == me[4]; 430 r = r && fwrite(eoud_mtable[m], b, me[5], f) == me[5]; 431 r = r && fwrite(cp_mtable[m], b, me[6], f) == me[6]; 432 r = r && fwrite(coud_mtable[m], b, me[7], f) == me[7]; 433 r = r && fwrite(corl_mtable[m], b, me[8], f) == me[8]; 434 r = r && fwrite(cofb_mtable[m], b, me[9], f) == me[9]; 435 r = r && fwrite(cpos_mtable[m], b, me[10], f) == me[10]; 436 } 437 438 fclose(f); 439 return r; 440 } 441 442 void 443 init_moves(void) 444 { 445 static bool initialized = false; 446 if (initialized) 447 return; 448 initialized = true; 449 450 Cube c; 451 CubeArray arrs; 452 int i; 453 unsigned int ui; 454 Move m; 455 Alg *equiv_alg[NMOVES]; 456 457 init_cube(); 458 459 for (i = 0; i < NMOVES; i++) 460 equiv_alg[i] = new_alg(equiv_alg_string[i]); 461 462 /* Generate all move cycles and flips; I do this regardless */ 463 for (i = 0; i < NMOVES; i++) { 464 if (i == U || i == x || i == y) 465 continue; 466 467 c = apply_alg_generic(equiv_alg[i], (Cube){0}, pf_all, false); 468 469 arrs = (CubeArray) { 470 edge_cycle[i], 471 eofb_flipped[i], 472 eorl_flipped[i], 473 eoud_flipped[i], 474 corner_cycle[i], 475 coud_flipped[i], 476 corl_flipped[i], 477 cofb_flipped[i], 478 center_cycle[i] 479 }; 480 cube_to_arrays(c, &arrs, pf_all); 481 } 482 483 if (read_mtables_file()) 484 goto init_moves_end; 485 486 fprintf(stderr, "Cannot load %s, generating it\n", "mtables"); 487 488 /* Initialize transition tables */ 489 for (m = 0; m < NMOVES; m++) { 490 for (ui = 0; ui < FACTORIAL12/FACTORIAL8; ui++) { 491 c = (Cube){ .epose = ui }; 492 c = apply_move_cubearray(m, c, pf_e); 493 epose_mtable[m][ui] = c.epose; 494 495 c = (Cube){ .eposs = ui }; 496 c = apply_move_cubearray(m, c, pf_s); 497 eposs_mtable[m][ui] = c.eposs; 498 499 c = (Cube){ .eposm = ui }; 500 c = apply_move_cubearray(m, c, pf_m); 501 eposm_mtable[m][ui] = c.eposm; 502 } 503 for (ui = 0; ui < POW2TO11; ui++ ) { 504 c = (Cube){ .eofb = ui }; 505 c = apply_move_cubearray(m, c, pf_eo); 506 eofb_mtable[m][ui] = c.eofb; 507 508 c = (Cube){ .eorl = ui }; 509 c = apply_move_cubearray(m, c, pf_eo); 510 eorl_mtable[m][ui] = c.eorl; 511 512 c = (Cube){ .eoud = ui }; 513 c = apply_move_cubearray(m, c, pf_eo); 514 eoud_mtable[m][ui] = c.eoud; 515 } 516 for (ui = 0; ui < POW3TO7; ui++) { 517 c = (Cube){ .coud = ui }; 518 c = apply_move_cubearray(m, c, pf_co); 519 coud_mtable[m][ui] = c.coud; 520 521 c = (Cube){ .corl = ui }; 522 c = apply_move_cubearray(m, c, pf_co); 523 corl_mtable[m][ui] = c.corl; 524 525 c = (Cube){ .cofb = ui }; 526 c = apply_move_cubearray(m, c, pf_co); 527 cofb_mtable[m][ui] = c.cofb; 528 } 529 for (ui = 0; ui < FACTORIAL8; ui++) { 530 c = (Cube){ .cp = ui }; 531 c = apply_move_cubearray(m, c, pf_cp); 532 cp_mtable[m][ui] = c.cp; 533 } 534 for (ui = 0; ui < FACTORIAL6; ui++) { 535 c = (Cube){ .cpos = ui }; 536 c = apply_move_cubearray(m, c, pf_cpos); 537 cpos_mtable[m][ui] = c.cpos; 538 } 539 } 540 541 if (!write_mtables_file()) 542 fprintf(stderr, "Error writing mtables\n"); 543 544 init_moves_end: 545 for (i = 0; i < NMOVES; i++) 546 free_alg(equiv_alg[i]); 547 } 548