alg.c (13673B)
1 #include "alg.h" 2 3 /* Local functions ***********************************************************/ 4 5 static bool allowed_HTM(Move m); 6 static bool allowed_URF(Move m); 7 static bool allowed_eofb(Move m); 8 static bool allowed_drud(Move m); 9 static bool allowed_drud_noD(Move m); 10 static bool allowed_htr(Move m); 11 static bool allowed_next_HTM(Move l2, Move l1, Move m); 12 static int axis(Move m); 13 14 static void free_alglistnode(AlgListNode *aln); 15 static void realloc_alg(Alg *alg, int n); 16 17 static int niss_type(Alg *a); 18 static void find_last_moves(Alg *a, bool inv, int *, int *, int *); 19 static int64_t last_move_pair(Alg *a, bool inv); 20 static int compare_algs_firstmoves(Alg * a, Alg *b, bool inv); 21 static int compare_algs(const void * a, const void *b); 22 23 /* Movesets ******************************************************************/ 24 25 Moveset 26 moveset_HTM = { 27 .allowed = allowed_HTM, 28 .allowed_next = allowed_next_HTM, 29 }; 30 31 Moveset 32 moveset_URF = { 33 .allowed = allowed_URF, 34 .allowed_next = allowed_next_HTM, 35 }; 36 37 Moveset 38 moveset_eofb = { 39 .allowed = allowed_eofb, 40 .allowed_next = allowed_next_HTM, 41 }; 42 43 Moveset 44 moveset_drud = { 45 .allowed = allowed_drud, 46 .allowed_next = allowed_next_HTM, 47 }; 48 49 Moveset 50 moveset_drud_noD = { 51 .allowed = allowed_drud_noD, 52 .allowed_next = allowed_next_HTM, 53 }; 54 55 Moveset 56 moveset_htr = { 57 .allowed = allowed_htr, 58 .allowed_next = allowed_next_HTM, 59 }; 60 61 static Moveset * all_ms[] = { 62 &moveset_HTM, 63 &moveset_URF, 64 &moveset_eofb, 65 &moveset_drud, 66 &moveset_drud_noD, 67 &moveset_htr, 68 NULL 69 }; 70 71 /* Functions *****************************************************************/ 72 73 static bool 74 allowed_HTM(Move m) 75 { 76 return m >= U && m <= B3; 77 } 78 79 static bool 80 allowed_URF(Move m) 81 { 82 Move b = base_move(m); 83 84 return b == U || b == R || b == F; 85 } 86 87 static bool 88 allowed_eofb(Move m) 89 { 90 Move b = base_move(m); 91 92 return b == U || b == D || b == R || b == L || 93 ((b == F || b == B) && m == b+1); 94 } 95 96 static bool 97 allowed_drud(Move m) 98 { 99 Move b = base_move(m); 100 101 return b == U || b == D || 102 ((b == R || b == L || b == F || b == B) && m == b + 1); 103 } 104 105 static bool 106 allowed_drud_noD(Move m) 107 { 108 Move b = base_move(m); 109 110 return b == U || 111 ((b == R || b == L || b == F || b == B) && m == b + 1); 112 } 113 114 static bool 115 allowed_htr(Move m) 116 { 117 Move b = base_move(m); 118 119 return moveset_HTM.allowed(m) && m == b + 1; 120 } 121 122 static bool 123 allowed_next_HTM(Move l2, Move l1, Move m) 124 { 125 bool p, q; 126 127 p = l1 != NULLMOVE && base_move(l1) == base_move(m); 128 q = l2 != NULLMOVE && base_move(l2) == base_move(m); 129 130 return !(p || (commute(l1, l2) && q)); 131 } 132 133 void 134 append_alg(AlgList *l, Alg *alg) 135 { 136 AlgListNode *node = malloc(sizeof(AlgListNode)); 137 int i; 138 139 node->alg = new_alg(""); 140 for (i = 0; i < alg->len; i++) 141 append_move(node->alg, alg->move[i], alg->inv[i]); 142 node->next = NULL; 143 144 if (++l->len == 1) 145 l->first = node; 146 else 147 l->last->next = node; 148 l->last = node; 149 } 150 151 void 152 append_move(Alg *alg, Move m, bool inverse) 153 { 154 if (alg->len == alg->allocated) 155 realloc_alg(alg, 2*alg->len); 156 157 alg->move[alg->len] = m; 158 alg->inv [alg->len] = inverse; 159 alg->len++; 160 } 161 162 static int 163 axis(Move m) 164 { 165 if (m == NULLMOVE) 166 return 0; 167 168 if (m >= U && m <= B3) 169 return (m-1)/6 + 1; 170 171 if (m >= Uw && m <= Bw3) 172 return (m-1)/6 - 2; 173 174 if (base_move(m) == E || base_move(m) == y) 175 return 1; 176 177 if (base_move(m) == M || base_move(m) == x) 178 return 2; 179 180 if (base_move(m) == S || base_move(m) == z) 181 return 3; 182 183 return -1; 184 } 185 186 Move 187 base_move(Move m) 188 { 189 if (m == NULLMOVE) 190 return NULLMOVE; 191 else 192 return m - (m-1)%3; 193 } 194 195 bool 196 commute(Move m1, Move m2) 197 { 198 return axis(m1) == axis(m2); 199 } 200 201 void 202 compose_alg(Alg *alg1, Alg *alg2) 203 { 204 int i; 205 206 for (i = 0; i < alg2->len; i++) 207 append_move(alg1, alg2->move[i], alg2->inv[i]); 208 } 209 210 void 211 copy_alg(Alg *src, Alg *dst) 212 { 213 dst->len = 0; /* Overwrites */ 214 compose_alg(dst, src); 215 } 216 217 void 218 free_alg(Alg *alg) 219 { 220 free(alg->move); 221 free(alg->inv); 222 free(alg); 223 } 224 225 void 226 free_alglist(AlgList *l) 227 { 228 AlgListNode *aux, *i = l->first; 229 230 while (i != NULL) { 231 aux = i->next; 232 free_alglistnode(i); 233 i = aux; 234 } 235 free(l); 236 } 237 238 static void 239 free_alglistnode(AlgListNode *aln) 240 { 241 free_alg(aln->alg); 242 free(aln); 243 } 244 245 void 246 inplace(Alg * (*f)(Alg *), Alg *alg) 247 { 248 Alg *aux; 249 250 aux = f(alg); 251 copy_alg(aux, alg); 252 free(aux); 253 } 254 255 Alg * 256 inverse_alg(Alg *alg) 257 { 258 Alg *ret = new_alg(""); 259 int i; 260 261 for (i = alg->len-1; i >= 0; i--) 262 append_move(ret, inverse_move(alg->move[i]), alg->inv[i]); 263 264 return ret; 265 } 266 267 Move 268 inverse_move(Move m) 269 { 270 return m == NULLMOVE ? NULLMOVE : m + 2 - 2*((m-1) % 3); 271 } 272 273 char * 274 move_string(Move m) 275 { 276 static char move_string_aux[NMOVES][7] = { 277 [NULLMOVE] = "-", 278 [U] = "U", [U2] = "U2", [U3] = "U\'", 279 [D] = "D", [D2] = "D2", [D3] = "D\'", 280 [R] = "R", [R2] = "R2", [R3] = "R\'", 281 [L] = "L", [L2] = "L2", [L3] = "L\'", 282 [F] = "F", [F2] = "F2", [F3] = "F\'", 283 [B] = "B", [B2] = "B2", [B3] = "B\'", 284 [Uw] = "Uw", [Uw2] = "Uw2", [Uw3] = "Uw\'", 285 [Dw] = "Dw", [Dw2] = "Dw2", [Dw3] = "Dw\'", 286 [Rw] = "Rw", [Rw2] = "Rw2", [Rw3] = "Rw\'", 287 [Lw] = "Lw", [Lw2] = "Lw2", [Lw3] = "Lw\'", 288 [Fw] = "Fw", [Fw2] = "Fw2", [Fw3] = "Fw\'", 289 [Bw] = "Bw", [Bw2] = "Bw2", [Bw3] = "Bw\'", 290 [M] = "M", [M2] = "M2", [M3] = "M\'", 291 [E] = "E", [E2] = "E2", [E3] = "E\'", 292 [S] = "S", [S2] = "S2", [S3] = "S\'", 293 [x] = "x", [x2] = "x2", [x3] = "x\'", 294 [y] = "y", [y2] = "y2", [y3] = "y\'", 295 [z] = "z", [z2] = "z2", [z3] = "z\'", 296 }; 297 298 return move_string_aux[m]; 299 } 300 301 Alg * 302 new_alg(char *str) 303 { 304 Alg *alg; 305 int i; 306 bool niss, move_read; 307 Move j, m; 308 309 alg = malloc(sizeof(Alg)); 310 alg->move = malloc(30 * sizeof(Move)); 311 alg->inv = malloc(30 * sizeof(bool)); 312 alg->allocated = 30; 313 alg->len = 0; 314 315 niss = false; 316 for (i = 0; str[i]; i++) { 317 if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n') 318 continue; 319 320 if (str[i] == '(' && niss) { 321 fprintf(stderr, "Error reading moves: nested ( )\n"); 322 alg->len = 0; 323 return alg; 324 } 325 326 if (str[i] == ')' && !niss) { 327 fprintf(stderr, "Error reading moves: unmatched )\n"); 328 alg->len = 0; 329 return alg; 330 } 331 332 if (str[i] == '(' || str[i] == ')') { 333 niss = !niss; 334 continue; 335 } 336 337 /* Single slash for comments */ 338 if (str[i] == '/') { 339 while (str[i] && str[i] != '\n') 340 i++; 341 342 if (!str[i]) 343 i--; 344 345 continue; 346 } 347 348 move_read = false; 349 for (j = U; j < NMOVES; j++) { 350 if (str[i] == move_string(j)[0] || 351 (str[i] >= 'a' && str[i] <= 'z' && 352 str[i] == move_string(j)[0]-('A'-'a') && j<=B)) { 353 m = j; 354 if (str[i] >= 'a' && str[i] <= 'z' && j<=B) { 355 m += Uw - U; 356 } 357 if (m <= B && str[i+1]=='w') { 358 m += Uw - U; 359 i++; 360 } 361 if (str[i+1]=='2') { 362 m += 1; 363 i++; 364 } else if (str[i+1] == '\'' || 365 str[i+1] == '3' || 366 str[i+1] == '`' ) { 367 m += 2; 368 i++; 369 } else if ((int)str[i+1] == -62 && 370 (int)str[i+2] == -76) { 371 /* Weird apostrophe */ 372 m += 2; 373 i += 2; 374 } else if ((int)str[i+1] == -30 && 375 (int)str[i+2] == -128 && 376 (int)str[i+3] == -103) { 377 /* MacOS apostrophe */ 378 m += 2; 379 i += 3; 380 } 381 append_move(alg, m, niss); 382 move_read = true; 383 break; 384 } 385 } 386 387 if (!move_read) { 388 free(alg); 389 return new_alg(""); 390 } 391 } 392 393 if (niss) { 394 fprintf(stderr, "Error reading moves: unmatched (\n"); 395 alg->len = 0; 396 } 397 398 return alg; 399 } 400 401 AlgList * 402 new_alglist(void) 403 { 404 AlgList *ret = malloc(sizeof(AlgList)); 405 406 ret->len = 0; 407 ret->first = NULL; 408 ret->last = NULL; 409 410 return ret; 411 } 412 413 Alg * 414 on_inverse(Alg *alg) 415 { 416 Alg *ret = new_alg(""); 417 int i; 418 419 for (i = 0; i < alg->len; i++) 420 append_move(ret, alg->move[i], !alg->inv[i]); 421 422 return ret; 423 } 424 425 void 426 print_alg(FILE *out, Alg *alg, bool l) 427 { 428 char fill[4]; 429 int i; 430 bool niss = false; 431 432 for (i = 0; i < alg->len; i++) { 433 if (!niss && alg->inv[i]) 434 strcpy(fill, i == 0 ? "(" : " ("); 435 if (niss && !alg->inv[i]) 436 strcpy(fill, ") "); 437 if (niss == alg->inv[i]) 438 strcpy(fill, i == 0 ? "" : " "); 439 440 fprintf(out, "%s%s", fill, move_string(alg->move[i])); 441 niss = alg->inv[i]; 442 } 443 444 if (niss) 445 fprintf(out, ")"); 446 if (l) 447 fprintf(out, " (%d)", alg->len); 448 449 fprintf(out, "\n"); 450 } 451 452 void 453 print_alglist(FILE *out, AlgList *al, bool l) 454 { 455 AlgListNode *i; 456 457 for (i = al->first; i != NULL; i = i->next) 458 print_alg(out, i->alg, l); 459 } 460 461 static void 462 realloc_alg(Alg *alg, int n) 463 { 464 if (alg == NULL) { 465 fprintf(stderr, "Error: trying to reallocate NULL alg.\n"); 466 return; 467 } 468 469 if (n < alg->len) { 470 fprintf(stderr, "Error: alg too long for reallocation "); 471 fprintf(stderr, "(%d vs %d)\n", alg->len, n); 472 return; 473 } 474 475 if (n > 1000000) { 476 fprintf(stderr, "Warning: very long alg,"); 477 fprintf(stderr, "something might go wrong.\n"); 478 } 479 480 alg->move = realloc(alg->move, n * sizeof(int)); 481 alg->inv = realloc(alg->inv, n * sizeof(int)); 482 alg->allocated = n; 483 } 484 485 static int 486 niss_type(Alg *a) 487 { 488 /* 0 if all moves are on normal, 1 if all on inverse, 2 otherwise */ 489 490 int i; 491 bool found_normal = false, found_inverse = false; 492 493 for (i = 0; i < a->len; i++) { 494 found_normal = found_normal || !a->inv[i]; 495 found_inverse = found_inverse || a->inv[i]; 496 } 497 498 if (found_normal && !found_inverse) 499 return 0; 500 if (!found_normal && found_inverse) 501 return 1; 502 return 2; 503 } 504 505 static void 506 find_last_moves(Alg *a, bool inv, int *n, int *nlast, int *nslast) 507 { 508 int i; 509 510 for (i = 0, *n = 0, *nlast = -1, *nslast = -1; i < a->len; i++) { 511 if (inv == a->inv[i]) { 512 (*n)++; 513 *nslast = *nlast; 514 *nlast = i; 515 } 516 } 517 } 518 519 static int64_t 520 last_move_pair(Alg *a, bool inv) 521 { 522 /* Order: _ F*, _ B*, F* B*, ... U* D* */ 523 524 static int bit[] = { 525 [F] = 16, [B] = 16, 526 [R] = 18, [L] = 18, 527 [U] = 20, [D] = 20 528 }; 529 int n, nlast, nslast, last, slast; 530 531 find_last_moves(a, inv, &n, &nlast, &nslast); 532 533 if (n == 0) 534 return -1; 535 536 last = a->move[nlast]; 537 slast = (nslast != -1 && commute(a->move[nlast], a->move[nslast])) ? 538 a->move[nslast] : 0; 539 540 return (slast * NMOVES + last) + (1LL << bit[base_move(last)]); 541 } 542 543 static int 544 compare_algs_firstmoves(Alg *a, Alg *b, bool inv) 545 { 546 /* Compare algs up to the last or the last two moves if parallel */ 547 548 int i, j, na, nlasta, nslasta, nb, nlastb, nslastb, ma, mb, m1, m2; 549 550 find_last_moves(a, inv, &na, &nlasta, &nslasta); 551 find_last_moves(b, inv, &nb, &nlastb, &nslastb); 552 553 ma = na > 0 ? ((na > 1 ? nslasta : nlasta) + 1) : 0; 554 mb = nb > 0 ? ((nb > 1 ? nslastb : nlastb) + 1) : 0; 555 556 if (ma == 0 && mb == 0) 557 return 0; 558 if (ma == 0) 559 return -1; 560 if (mb == 0) 561 return 1; 562 563 for (i = 0, j = 0; i < ma && j < mb; i++, j++) { 564 while (a->inv[i] != inv) i++; 565 while (a->inv[j] != inv) j++; 566 m1 = a->move[i]; 567 m2 = b->move[j]; 568 if (m1 - m2) 569 return m1 - m2; 570 } 571 572 return ma - mb; 573 } 574 575 static int 576 compare_algs(const void *avoid, const void *bvoid) 577 { 578 /* We sort a list of algs in a way that makes the most sense for the 579 * commands and steps where one usually wants many results, for 580 * example EO and DR. We sort by, in order: 581 * 1. Length of the solution 582 * 2. NISS type (first algs that are all on normal, then those that 583 * are all on inverse, then those that use NISS) 584 * 3. Last move on normal, or last two moves if they are parallel 585 * 4. All other moves on normal scramble 586 * 5. Last move on inverse, or last two moves if they are parallel 587 * 6. All other moves on inverse 588 */ 589 590 Alg *a = *(Alg **)avoid; 591 Alg *b = *(Alg **)bvoid; 592 593 int ntype_a, ntype_b, last_a, last_b, cmp; 594 595 /* 1. Compare length */ 596 if (a->len - b->len) 597 return a->len - b->len; 598 599 /* 2. Algs have the same length, compare NISS type */ 600 ntype_a = niss_type(a); 601 ntype_b = niss_type(b); 602 if (ntype_a - ntype_b) 603 return ntype_a - ntype_b; 604 605 /* 3. Algs have same NISS type, compare last moves on normal */ 606 last_a = last_move_pair(a, false); 607 last_b = last_move_pair(b, false); 608 if (last_a - last_b) 609 return last_a - last_b; 610 611 /* 4. Algs have same last moves on normal, compare all other moves */ 612 cmp = compare_algs_firstmoves(a, b, false); 613 if (cmp) 614 return cmp; 615 616 /* 5. Algs have same moves on normal, compare last on inverse */ 617 last_a = last_move_pair(a, true); 618 last_b = last_move_pair(b, true); 619 if (last_a - last_b) 620 return last_a - last_b; 621 622 /* 6. Algs have same last moves on inverse, compare other */ 623 cmp = compare_algs_firstmoves(a, b, true); 624 if (cmp) 625 return cmp; 626 627 /* Algs are equal */ 628 return 0; 629 } 630 631 void 632 sort_alglist(AlgList *al) 633 { 634 int i, n = al->len; 635 Alg* alg_array[n+1]; 636 AlgListNode *node; 637 638 for (i = 0, node = al->first; i < n; i++, node = node->next) 639 alg_array[i] = node->alg; 640 641 qsort(alg_array, n, sizeof(Alg *), &compare_algs); 642 643 for (i = 0, node = al->first; i < n; i++, node = node->next) 644 node->alg = alg_array[i]; 645 } 646 647 void 648 swapmove(Move *m1, Move *m2) 649 { 650 Move aux; 651 652 aux = *m1; 653 *m1 = *m2; 654 *m2 = aux; 655 } 656 657 Alg * 658 unniss(Alg *alg) 659 { 660 int i; 661 Alg *ret; 662 663 ret = new_alg(""); 664 665 for (i = 0; i < alg->len; i++) 666 if (!alg->inv[i]) 667 append_move(ret, alg->move[i], false); 668 669 for (i = alg->len-1; i >= 0; i--) 670 if (alg->inv[i]) 671 append_move(ret, inverse_move(alg->move[i]), false); 672 673 return ret; 674 } 675 676 void 677 init_moveset(Moveset *ms) 678 { 679 int j; 680 uint64_t l, one; 681 Move m, l2, l1; 682 683 one = 1; 684 685 for (j = 0, m = U; m < NMOVES; m++) 686 if (ms->allowed(m)) 687 ms->sorted_moves[j++] = m; 688 ms->sorted_moves[j] = NULLMOVE; 689 690 for (l1 = 0; l1 < NMOVES; l1++) { 691 for (l2 = 0; l2 < NMOVES; l2++) { 692 ms->mask[l2][l1] = 0; 693 for (l=0; ms->sorted_moves[l]!=NULLMOVE; l++) { 694 m = ms->sorted_moves[l]; 695 if (ms->allowed_next(l2, l1, m)) 696 ms->mask[l2][l1] |= (one<<m); 697 } 698 } 699 } 700 } 701 702 void 703 init_all_movesets(void) 704 { 705 int i; 706 707 for (i = 0; all_ms[i] != NULL; i++) 708 init_moveset(all_ms[i]); 709 }