alg.c (9045B)
1 #define ALG_C 2 3 #include "alg.h" 4 5 static int axis(Move m); 6 static void free_alglistnode(AlgListNode *aln); 7 static void realloc_alg(Alg *alg, int n); 8 9 void 10 append_alg(AlgList *l, Alg *alg) 11 { 12 AlgListNode *node = malloc(sizeof(AlgListNode)); 13 int i; 14 15 node->alg = new_alg(""); 16 for (i = 0; i < alg->len; i++) 17 append_move(node->alg, alg->move[i], alg->inv[i]); 18 node->next = NULL; 19 20 if (++l->len == 1) 21 l->first = node; 22 else 23 l->last->next = node; 24 l->last = node; 25 } 26 27 void 28 append_move(Alg *alg, Move m, bool inverse) 29 { 30 if (alg->len == alg->allocated) 31 realloc_alg(alg, 2*alg->len); 32 33 alg->move[alg->len] = m; 34 alg->inv [alg->len] = inverse; 35 alg->len++; 36 37 if (inverse) 38 alg->move_inverse[alg->len_inverse++] = m; 39 else 40 alg->move_normal[alg->len_normal++] = m; 41 } 42 43 static int 44 axis(Move m) 45 { 46 static int aux[] = { 47 [NULLMOVE] = 0, 48 49 [U] = 1, [U2] = 1, [U3] = 1, 50 [D] = 1, [D2] = 1, [D3] = 1, 51 [Uw] = 1, [Uw2] = 1, [Uw3] = 1, 52 [Dw] = 1, [Dw2] = 1, [Dw3] = 1, 53 [E] = 1, [E2] = 1, [E3] = 1, 54 [y] = 1, [y2] = 1, [y3] = 1, 55 56 [R] = 2, [R2] = 2, [R3] = 2, 57 [L] = 2, [L2] = 2, [L3] = 2, 58 [Rw] = 2, [Rw2] = 2, [Rw3] = 2, 59 [Lw] = 2, [Lw2] = 2, [Lw3] = 2, 60 [M] = 2, [M2] = 2, [M3] = 2, 61 [x] = 2, [x2] = 2, [x3] = 2, 62 63 [F] = 3, [F2] = 3, [F3] = 3, 64 [B] = 3, [B2] = 3, [B3] = 3, 65 [Fw] = 3, [Fw2] = 3, [Fw3] = 3, 66 [Bw] = 3, [Bw2] = 3, [Bw3] = 3, 67 [S] = 3, [S2] = 3, [S3] = 3, 68 [z] = 3, [z2] = 3, [z3] = 3, 69 }; 70 71 return aux[m]; 72 } 73 74 Move 75 base_move(Move m) 76 { 77 if (m == NULLMOVE) 78 return NULLMOVE; 79 else 80 return m - (m-1)%3; 81 } 82 83 bool 84 commute(Move m1, Move m2) 85 { 86 return axis(m1) == axis(m2); 87 } 88 89 int 90 compare(Move m1, Move m2) 91 { 92 if (!commute(m1, m2)) 93 return 0; 94 95 return m1 < m2 ? 1 : -1; 96 } 97 98 int 99 compare_last(Alg *alg, Move m, bool inverse) 100 { 101 Move last; 102 int n; 103 104 if (inverse) { 105 n = alg->len_inverse; 106 last = n > 0 ? alg->move_inverse[n-1] : NULLMOVE; 107 } else { 108 n = alg->len_normal; 109 last = n > 0 ? alg->move_normal[n-1] : NULLMOVE; 110 } 111 112 return compare(last, m); 113 } 114 115 void 116 compose_alg(Alg *alg1, Alg *alg2) 117 { 118 int i; 119 120 for (i = 0; i < alg2->len; i++) 121 append_move(alg1, alg2->move[i], alg2->inv[i]); 122 } 123 124 void 125 copy_alg(Alg *src, Alg *dst) 126 { 127 dst->len = dst->len_normal = dst->len_inverse = 0; 128 compose_alg(dst, src); 129 } 130 131 void 132 free_alg(Alg *alg) 133 { 134 free(alg->move); 135 free(alg->inv); 136 free(alg); 137 } 138 139 void 140 free_alglist(AlgList *l) 141 { 142 AlgListNode *aux, *i = l->first; 143 144 while (i != NULL) { 145 aux = i->next; 146 free_alglistnode(i); 147 i = aux; 148 } 149 free(l); 150 } 151 152 static void 153 free_alglistnode(AlgListNode *aln) 154 { 155 free_alg(aln->alg); 156 free(aln); 157 } 158 159 Alg * 160 inverse_alg(Alg *alg) 161 { 162 Alg *ret = new_alg(""); 163 int i; 164 165 for (i = alg->len-1; i >= 0; i--) 166 append_move(ret, inverse_move(alg->move[i]), alg->inv[i]); 167 168 return ret; 169 } 170 171 Move 172 inverse_move(Move m) 173 { 174 return m == NULLMOVE ? NULLMOVE : m + 2 - 2*((m-1) % 3); 175 } 176 177 char * 178 move_string(Move m) 179 { 180 static char move_string_aux[NMOVES][7] = { 181 [NULLMOVE] = "-", 182 [U] = "U", [U2] = "U2", [U3] = "U\'", 183 [D] = "D", [D2] = "D2", [D3] = "D\'", 184 [R] = "R", [R2] = "R2", [R3] = "R\'", 185 [L] = "L", [L2] = "L2", [L3] = "L\'", 186 [F] = "F", [F2] = "F2", [F3] = "F\'", 187 [B] = "B", [B2] = "B2", [B3] = "B\'", 188 [Uw] = "Uw", [Uw2] = "Uw2", [Uw3] = "Uw\'", 189 [Dw] = "Dw", [Dw2] = "Dw2", [Dw3] = "Dw\'", 190 [Rw] = "Rw", [Rw2] = "Rw2", [Rw3] = "Rw\'", 191 [Lw] = "Lw", [Lw2] = "Lw2", [Lw3] = "Lw\'", 192 [Fw] = "Fw", [Fw2] = "Fw2", [Fw3] = "Fw\'", 193 [Bw] = "Bw", [Bw2] = "Bw2", [Bw3] = "Bw\'", 194 [M] = "M", [M2] = "M2", [M3] = "M\'", 195 [E] = "E", [E2] = "E2", [E3] = "E\'", 196 [S] = "S", [S2] = "S2", [S3] = "S\'", 197 [x] = "x", [x2] = "x2", [x3] = "x\'", 198 [y] = "y", [y2] = "y2", [y3] = "y\'", 199 [z] = "z", [z2] = "z2", [z3] = "z\'", 200 }; 201 202 return move_string_aux[m]; 203 } 204 205 Alg * 206 new_alg(char *str) 207 { 208 Alg *alg; 209 int i; 210 bool niss, move_read; 211 Move j, m; 212 213 alg = malloc(sizeof(Alg)); 214 alg->allocated = 30; 215 alg->move = malloc(alg->allocated * sizeof(Move)); 216 alg->inv = malloc(alg->allocated * sizeof(bool)); 217 alg->move_normal = malloc(alg->allocated * sizeof(Move)); 218 alg->move_inverse = malloc(alg->allocated * sizeof(Move)); 219 alg->len = 0; 220 alg->len_normal = 0; 221 alg->len_inverse = 0; 222 223 niss = false; 224 for (i = 0; str[i]; i++) { 225 if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n') 226 continue; 227 228 if (str[i] == '(' && niss) { 229 fprintf(stderr, "Error reading moves: nested ( )\n"); 230 alg->len = alg->len_normal = alg->len_inverse = 0; 231 return alg; 232 } 233 234 if (str[i] == ')' && !niss) { 235 fprintf(stderr, "Error reading moves: unmatched )\n"); 236 alg->len = alg->len_normal = alg->len_inverse = 0; 237 return alg; 238 } 239 240 if (str[i] == '(' || str[i] == ')') { 241 niss = !niss; 242 continue; 243 } 244 245 /* Single slash for comments */ 246 if (str[i] == '/') { 247 while (str[i] && str[i] != '\n') 248 i++; 249 250 if (!str[i]) 251 i--; 252 253 continue; 254 } 255 256 move_read = false; 257 for (j = U; j < NMOVES; j++) { 258 if (str[i] == move_string(j)[0] || 259 (str[i] >= 'a' && str[i] <= 'z' && 260 str[i] == move_string(j)[0]-('A'-'a') && j<=B)) { 261 m = j; 262 if (str[i] >= 'a' && str[i] <= 'z' && j<=B) { 263 m += Uw - U; 264 } 265 if (m <= B && str[i+1]=='w') { 266 m += Uw - U; 267 i++; 268 } 269 if (str[i+1]=='2') { 270 m += 1; 271 i++; 272 } else if (str[i+1] == '\'' || 273 str[i+1] == '3' || 274 str[i+1] == '`' ) { 275 m += 2; 276 i++; 277 } else if ((int)str[i+1] == -62 && 278 (int)str[i+2] == -76) { 279 /* Weird apostrophe */ 280 m += 2; 281 i += 2; 282 } else if ((int)str[i+1] == -30 && 283 (int)str[i+2] == -128 && 284 (int)str[i+3] == -103) { 285 /* MacOS apostrophe */ 286 m += 2; 287 i += 3; 288 } 289 append_move(alg, m, niss); 290 move_read = true; 291 break; 292 } 293 } 294 295 if (!move_read) { 296 free(alg); 297 return new_alg(""); 298 } 299 } 300 301 if (niss) { 302 fprintf(stderr, "Error reading moves: unmatched (\n"); 303 alg->len = alg->len_normal = alg->len_inverse = 0; 304 } 305 306 return alg; 307 } 308 309 AlgList * 310 new_alglist() 311 { 312 AlgList *ret = malloc(sizeof(AlgList)); 313 314 ret->len = 0; 315 ret->first = NULL; 316 ret->last = NULL; 317 318 return ret; 319 } 320 321 Alg * 322 on_inverse(Alg *alg) 323 { 324 Alg *ret = new_alg(""); 325 int i; 326 327 for (i = 0; i < alg->len; i++) 328 append_move(ret, alg->move[i], !alg->inv[i]); 329 330 return ret; 331 } 332 333 void 334 print_alg(Alg *alg, bool l) 335 { 336 char fill[4]; 337 int i; 338 bool niss = false; 339 340 for (i = 0; i < alg->len; i++) { 341 if (!niss && alg->inv[i]) 342 strcpy(fill, i == 0 ? "(" : " ("); 343 if (niss && !alg->inv[i]) 344 strcpy(fill, ") "); 345 if (niss == alg->inv[i]) 346 strcpy(fill, i == 0 ? "" : " "); 347 348 printf("%s%s", fill, move_string(alg->move[i])); 349 niss = alg->inv[i]; 350 } 351 352 if (niss) 353 printf(")"); 354 if (l) 355 printf(" (%d)", alg->len); 356 357 printf("\n"); 358 } 359 360 void 361 print_alglist(AlgList *al, bool l) 362 { 363 AlgListNode *i; 364 365 for (i = al->first; i != NULL; i = i->next) 366 print_alg(i->alg, l); 367 } 368 369 static void 370 realloc_alg(Alg *alg, int n) 371 { 372 if (alg == NULL) { 373 fprintf(stderr, "Error: trying to reallocate NULL alg.\n"); 374 return; 375 } 376 377 if (n < alg->len) { 378 fprintf(stderr, "Error: alg too long for reallocation "); 379 fprintf(stderr, "(%d vs %d)\n", alg->len, n); 380 return; 381 } 382 383 if (n > 1000000) { 384 fprintf(stderr, "Warning: very long alg,"); 385 fprintf(stderr, "something might go wrong.\n"); 386 } 387 388 alg->move = realloc(alg->move, n * sizeof(int)); 389 alg->inv = realloc(alg->inv, n * sizeof(int)); 390 alg->move_normal = realloc(alg->move_normal, n * sizeof(int)); 391 alg->move_inverse = realloc(alg->move_inverse, n * sizeof(int)); 392 alg->allocated = n; 393 } 394 395 void 396 remove_last_move(Alg *a) 397 { 398 a->len--; 399 400 if (a->inv[a->len]) 401 a->len_inverse--; 402 else 403 a->len_normal--; 404 } 405 406 void 407 swapmove(Move *m1, Move *m2) 408 { 409 Move aux; 410 411 aux = *m1; 412 *m1 = *m2; 413 *m2 = aux; 414 } 415 416 char * 417 trans_string(Trans t) 418 { 419 static char trans_string_aux[NTRANS][20] = { 420 [uf] = "uf", [ur] = "ur", [ub] = "ub", [ul] = "ul", 421 [df] = "df", [dr] = "dr", [db] = "db", [dl] = "dl", 422 [rf] = "rf", [rd] = "rd", [rb] = "rb", [ru] = "ru", 423 [lf] = "lf", [ld] = "ld", [lb] = "lb", [lu] = "lu", 424 [fu] = "fu", [fr] = "fr", [fd] = "fd", [fl] = "fl", 425 [bu] = "bu", [br] = "br", [bd] = "bd", [bl] = "bl", 426 427 [uf_mirror] = "uf*", [ur_mirror] = "ur*", 428 [ub_mirror] = "ub*", [ul_mirror] = "ul*", 429 [df_mirror] = "df*", [dr_mirror] = "dr*", 430 [db_mirror] = "db*", [dl_mirror] = "dl*", 431 [rf_mirror] = "rf*", [rd_mirror] = "rd*", 432 [rb_mirror] = "rb*", [ru_mirror] = "ru*", 433 [lf_mirror] = "lf*", [ld_mirror] = "ld*", 434 [lb_mirror] = "lb*", [lu_mirror] = "lu*", 435 [fu_mirror] = "fu*", [fr_mirror] = "fr*", 436 [fd_mirror] = "fd*", [fl_mirror] = "fl*", 437 [bu_mirror] = "bu*", [br_mirror] = "br*", 438 [bd_mirror] = "bd*", [bl_mirror] = "bl*", 439 }; 440 441 return trans_string_aux[t]; 442 } 443 444 Alg * 445 unniss(Alg *alg) 446 { 447 int i; 448 Alg *ret; 449 450 ret = new_alg(""); 451 452 for (i = 0; i < alg->len_normal; i++) 453 append_move(ret, alg->move_normal[i], false); 454 455 for (i = 0; i < alg->len_inverse; i++) 456 append_move(ret, inverse_move(alg->move_inverse[i]), false); 457 458 return ret; 459 }