nissy-nx

A Rubik's cube optimal solver
git clone https://git.tronto.net/nissy-nx
Download | Log | Files | Refs | README | LICENSE

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 }