nissy-classic

Stable branch of nissy
git clone https://git.tronto.net/nissy-classic
Download | Log | Files | Refs | README | LICENSE

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 }