cube.c - nissy-fmc - A Rubik's cube FMC assistant

cube.c (11883B)
      1 #include <stdbool.h>
      2 
      3 #include "cube.h"
      4 
      5 static void apply_permutation(int *, int *, int, int *);
      6 static void sum_arrays_mod(int *, int *, int, int);
      7 static Move read_move(char *, int *);
      8 static void init_moves(void);
      9 static void init_trans(void);
     10 
     11 static Cube move_array[NMOVES_ALL];
     12 Move moves_ttable[NTRANS][NMOVES_ALL];
     13 Trans trans_ttable[NTRANS][NTRANS];
     14 Trans trans_itable[NTRANS];
     15 
     16 static char move_string[NMOVES_ALL][7] = {
     17 	[NULLMOVE] = "-",
     18 	[U]  = "U",  [U2]  = "U2",  [U3]  = "U\'",
     19 	[D]  = "D",  [D2]  = "D2",  [D3]  = "D\'",
     20 	[R]  = "R",  [R2]  = "R2",  [R3]  = "R\'",
     21 	[L]  = "L",  [L2]  = "L2",  [L3]  = "L\'",
     22 	[F]  = "F",  [F2]  = "F2",  [F3]  = "F\'",
     23 	[B]  = "B",  [B2]  = "B2",  [B3]  = "B\'",
     24 	[Uw] = "Uw", [Uw2] = "Uw2", [Uw3] = "Uw\'",
     25 	[Dw] = "Dw", [Dw2] = "Dw2", [Dw3] = "Dw\'",
     26 	[Rw] = "Rw", [Rw2] = "Rw2", [Rw3] = "Rw\'",
     27 	[Lw] = "Lw", [Lw2] = "Lw2", [Lw3] = "Lw\'",
     28 	[Fw] = "Fw", [Fw2] = "Fw2", [Fw3] = "Fw\'",
     29 	[Bw] = "Bw", [Bw2] = "Bw2", [Bw3] = "Bw\'",
     30 	[M]  = "M",  [M2]  = "M2",  [M3]  = "M\'",
     31 	[E]  = "E",  [E2]  = "E2",  [E3]  = "E\'",
     32 	[S]  = "S",  [S2]  = "S2",  [S3]  = "S\'",
     33 	[x]  = "x",  [x2]  = "x2",  [x3]  = "x\'",
     34 	[y]  = "y",  [y2]  = "y2",  [y3]  = "y\'",
     35 	[z]  = "z",  [z2]  = "z2",  [z3]  = "z\'",
     36 };
     37 static char rotation_string[100][NTRANS/2] = {
     38 	[uf] = "",     [ur] = "y",    [ub] = "y2",    [ul] = "y3",
     39 	[df] = "z2",   [dr] = "y z2", [db] = "x2",    [dl] = "y3 z2",
     40 	[rf] = "z3",   [rd] = "z3 y", [rb] = "z3 y2", [ru] = "z3 y3",
     41 	[lf] = "z",    [ld] = "z y3", [lb] = "z y2",  [lu] = "z y",
     42 	[fu] = "x y2", [fr] = "x y",  [fd] = "x",     [fl] = "x y3",
     43 	[bu] = "x3",   [br] = "x3 y", [bd] = "x3 y2", [bl] = "x3 y3",
     44 };
     45 
     46 TransGroup
     47 tgrp_udfix = {
     48 	.n = 16,
     49 	.t = {
     50 	    uf, ur, ub, ul,
     51 	    df, dr, db, dl,
     52 	    uf_mirror, ur_mirror, ub_mirror, ul_mirror,
     53 	    df_mirror, dr_mirror, db_mirror, dl_mirror
     54 	},
     55 };
     56 
     57 static void
     58 apply_permutation(int *perm, int *set, int n, int *aux)
     59 {
     60 	int i;
     61 
     62 	for (i = 0; i < n; i++)
     63 		aux[i] = set[perm[i]];
     64 
     65 	for (i = 0; i < n; i++)
     66 		set[i] = aux[i];
     67 }
     68 
     69 static void
     70 sum_arrays_mod(int *src, int *dst, int n, int m)
     71 {
     72 	int i;
     73 
     74 	for (i = 0; i < n; i++)
     75 		dst[i] = (src[i] + dst[i]) % m;
     76 }
     77 
     78 void
     79 compose(Cube *c2, Cube *c1)
     80 {
     81 	int aux[12];
     82 
     83 	apply_permutation(c2->ep, c1->ep, 12, aux);
     84 	apply_permutation(c2->ep, c1->eo, 12, aux);
     85 	sum_arrays_mod(c2->eo, c1->eo, 12, 2);
     86 
     87 	apply_permutation(c2->cp, c1->cp, 8, aux);
     88 	apply_permutation(c2->cp, c1->co, 8, aux);
     89 
     90 	sum_arrays_mod(c2->co, c1->co, 8, 3);
     91 }
     92 
     93 void
     94 copy_cube(Cube *src, Cube *dst)
     95 {
     96 	int i;
     97 
     98 	for (i = 0; i < 12; i++) {
     99 		dst->ep[i] = src->ep[i];
    100 		dst->eo[i] = src->eo[i];
    101 	}
    102 
    103 	for (i = 0; i < 8; i++) {
    104 		dst->cp[i] = src->cp[i];
    105 		dst->co[i] = src->co[i];
    106 	}
    107 }
    108 
    109 void
    110 invert_cube(Cube *cube)
    111 {
    112 	Cube aux;
    113 	int i;
    114 
    115 	copy_cube(cube, &aux);
    116 
    117 	for (i = 0; i < 12; i++) {
    118 		cube->ep[aux.ep[i]] = i;
    119 		cube->eo[aux.ep[i]] = aux.eo[i];
    120 	}
    121 
    122 	for (i = 0; i < 8; i++) {
    123 		cube->cp[aux.cp[i]] = i;
    124 		cube->co[aux.cp[i]] = (3 - aux.co[i]) % 3;
    125 	}
    126 }
    127 
    128 bool
    129 is_solved(Cube *cube)
    130 {
    131 	int i;
    132 
    133 	for (i = 0; i < 12; i++)
    134 		if (cube->eo[i] != 0 || cube->ep[i] != i)
    135 			return false;
    136 
    137 	for (i = 0; i < 8; i++)
    138 		if (cube->co[i] != 0 || cube->cp[i] != i)
    139 			return false;
    140 
    141 	return true;
    142 }
    143 
    144 void
    145 make_solved(Cube *cube)
    146 {
    147 	int i;
    148 
    149 	for (i = 0; i < 12; i++) {
    150 		cube->ep[i] = i;
    151 		cube->eo[i] = 0;
    152 	}
    153 
    154 	for (i = 0; i < 8; i++) {
    155 		cube->cp[i] = i;
    156 		cube->co[i] = 0;
    157 	}
    158 }
    159 
    160 Move
    161 base_move(Move m)
    162 {
    163 	return m == NULLMOVE ? NULLMOVE : m - (m-1)%3;
    164 }
    165 
    166 Move
    167 inverse_move(Move m)
    168 {
    169 	return m == NULLMOVE ? NULLMOVE : m + 2 - 2*((m-1) % 3);
    170 }
    171 
    172 bool
    173 commute(Move m1, Move m2)
    174 {
    175 	if (m1 == NULLMOVE || m2 == NULLMOVE)
    176 		return m1 == m2;
    177 
    178 	return (m1-1)/6 == (m2-1)/6;
    179 }
    180 
    181 void
    182 copy_alg(Alg *src, Alg *dst)
    183 {
    184 	int i;
    185 
    186 	dst->len = src->len;
    187 	for (i = 0; i < src->len; i++) {
    188 		dst->move[i] = src->move[i];
    189 		dst->inv[i] = src->inv[i];
    190 	}
    191 }
    192 
    193 void
    194 append_move(Alg *alg, Move m, bool inverse)
    195 {
    196 	alg->move[alg->len] = m;
    197 	alg->inv[alg->len] = inverse;
    198 	alg->len++;
    199 }
    200 
    201 void
    202 apply_move(Move m, Cube *cube)
    203 {
    204 	compose(&move_array[m], cube);
    205 }
    206 
    207 void
    208 apply_alg(Alg *alg, Cube *cube)
    209 {
    210 	Cube aux;
    211 	int i;
    212 
    213 	copy_cube(cube, &aux);
    214 	make_solved(cube);
    215 
    216 	for (i = 0; i < alg->len; i++)
    217 		if (alg->inv[i])
    218 			apply_move(alg->move[i], cube);
    219 
    220 	invert_cube(cube);
    221 	compose(&aux, cube);
    222 
    223 	for (i = 0; i < alg->len; i++)
    224 		if (!alg->inv[i])
    225 			apply_move(alg->move[i], cube);
    226 }
    227 
    228 static Move
    229 read_move(char *str, int *i)
    230 {
    231 	Move j, m;
    232 	char upper, lower, inv;
    233 
    234 	for (j = U; j < NMOVES_ALL; j++) {
    235 		upper = move_string[j][0];
    236 		lower = upper - ('A' - 'a');
    237 		if (str[*i] == upper || (str[*i] == lower && j <= B)) {
    238 			m = j;
    239 			if (str[*i] == lower)
    240 				m += Uw - U;
    241 			if (m <= B && str[*i+1] == 'w') {
    242 				m += Uw - U;
    243 				*i += 1;
    244 			}
    245 			if (str[*i+1]=='2') {
    246 				m += 1;
    247 				*i += 1;
    248 			}
    249 			inv = str[*i+1] == '\'' ||
    250 			      str[*i+1] == '3'  ||
    251 			      str[*i+1] == '`';
    252 			/* TODO: add weird apostrophes */
    253 			if (inv) {
    254 				m += 2;
    255 				*i += 1;
    256 			}
    257 			return m;
    258 		}
    259 	}
    260 
    261 	return NULLMOVE;
    262 }
    263 
    264 bool 
    265 apply_scramble(char *str, Cube *c)
    266 {
    267 	int i;
    268 	bool niss;
    269 	Cube normal, inverse;
    270 	Move move;
    271 
    272 	niss = false;
    273 	make_solved(&normal);
    274 	make_solved(&inverse);
    275 	for (i = 0; str[i]; i++) {
    276 		if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n')
    277 			continue;
    278 
    279 		if ((str[i] == '(' && niss) || (str[i] == ')' && !niss))
    280 			return false;
    281 
    282 		if (str[i] == '(' || str[i] == ')') {
    283 			niss = !niss;
    284 			continue;
    285 		}
    286 
    287 		/* Single slash for comments */
    288 		if (str[i] == '/') {
    289 			while (str[i] && str[i] != '\n') i++;
    290 			if (!str[i]) i--;
    291 			continue;
    292 		}
    293 
    294 		move = read_move(str, &i);
    295 		if (move == NULLMOVE)
    296 			return false;
    297 		apply_move(move, niss ? &inverse : &normal);
    298 	}
    299 
    300 	if (niss)
    301 		return false;
    302 
    303 	invert_cube(&inverse);
    304 	compose(c, &inverse);
    305 	copy_cube(&inverse, c);
    306 	compose(&normal, c);
    307 
    308 	return true;
    309 }
    310 
    311 int
    312 alg_string(Alg *alg, char *str)
    313 {
    314 	int i, n;
    315 	bool niss;
    316 	Move m;
    317 
    318 	niss = false;
    319 	for (i = 0, n = 0; i < alg->len; i++) {
    320 		if (!niss && alg->inv[i]) {
    321 			if (i != 0)
    322 				str[n++] = ' ';
    323 			str[n++] = '(';
    324 		}
    325 		if (niss && !alg->inv[i]) {
    326 			str[n++] = ')';
    327 			str[n++] = ' ';
    328 		}
    329 		if (niss == alg->inv[i] && i != 0)
    330 			str[n++] = ' ';
    331 		m = alg->move[i];
    332 		str[n++] = move_string[m][0];
    333 		if (move_string[m][1])
    334 			str[n++] = move_string[m][1];
    335 		niss = alg->inv[i];
    336 	}
    337 
    338 	if (niss)
    339 		str[n++] = ')';
    340 	str[n] = 0;
    341 
    342 	return n;
    343 }
    344 
    345 void
    346 apply_trans(Trans t, Cube *cube)
    347 {
    348 	Cube aux, inv;
    349 	int i;
    350 
    351 	static Cube mirror_cube = {
    352 	.ep = { [UF] = UF, [UL] = UR, [UB] = UB, [UR] = UL,
    353 		[DF] = DF, [DL] = DR, [DB] = DB, [DR] = DL,
    354 		[FR] = FL, [FL] = FR, [BL] = BR, [BR] = BL },
    355 	.cp = { [UFR] = UFL, [UFL] = UFR, [UBL] = UBR, [UBR] = UBL,
    356 		[DFR] = DFL, [DFL] = DFR, [DBL] = DBR, [DBR] = DBL },
    357 	};
    358 
    359 	copy_cube(cube, &aux);
    360 	make_solved(cube);
    361 
    362 	if (t >= NTRANS/2)
    363 		compose(&mirror_cube, cube);
    364 	make_solved(&inv);
    365 	apply_scramble(rotation_string[t % (NTRANS/2)], &inv);
    366 	invert_cube(&inv);
    367 	compose(&inv, cube);
    368 	compose(&aux, cube);
    369 	apply_scramble(rotation_string[t % (NTRANS/2)], cube);
    370 	if (t >= NTRANS/2) {
    371 		compose(&mirror_cube, cube);
    372 		for (i = 0; i < 8; i++)
    373 			cube->co[i] = (3 - cube->co[i]) % 3;
    374 	}
    375 }
    376 
    377 Trans
    378 inverse_trans(Trans t)
    379 {
    380 	return trans_itable[t];
    381 }
    382 
    383 void
    384 transform_alg(Trans t, Alg *alg)
    385 {
    386 	int i;
    387 
    388 	for (i = 0; i < alg->len; i++)
    389 		alg->move[i] = transform_move(t, alg->move[i]);
    390 }
    391 
    392 Move
    393 transform_move(Trans t, Move m)
    394 {
    395 	return moves_ttable[t][m];
    396 }
    397 
    398 Trans
    399 transform_trans(Trans t, Trans m)
    400 {
    401 	return trans_ttable[t][m];
    402 }
    403 
    404 static void
    405 init_moves(void) {
    406 	Move m;
    407 
    408 	/* Moves are represented as cubes and applied using compose().
    409 	 * Every move is translated to a an <U, x, y> alg before filling
    410 	 * the transition tables. */
    411 	char equiv_alg_string[100][NMOVES_ALL] = {
    412 		[NULLMOVE] = "",
    413 
    414 		[U]   = "        U           ",
    415 		[U2]  = "        UU          ",
    416 		[U3]  = "        UUU         ",
    417 		[D]   = "  xx    U    xx      ",
    418 		[D2]  = "  xx    UU   xx      ",
    419 		[D3]  = "  xx    UUU  xx      ",
    420 		[R]   = "  yx    U    xxxyyy  ",
    421 		[R2]  = "  yx    UU   xxxyyy  ",
    422 		[R3]  = "  yx    UUU  xxxyyy  ",
    423 		[L]   = "  yyyx  U    xxxy    ",
    424 		[L2]  = "  yyyx  UU   xxxy    ",
    425 		[L3]  = "  yyyx  UUU  xxxy    ",
    426 		[F]   = "  x     U    xxx     ",
    427 		[F2]  = "  x     UU   xxx     ",
    428 		[F3]  = "  x     UUU  xxx     ",
    429 		[B]   = "  xxx   U    x       ",
    430 		[B2]  = "  xxx   UU   x       ",
    431 		[B3]  = "  xxx   UUU  x       ",
    432 
    433 		[Uw]  = "  xx    U    xx      y        ",
    434 		[Uw2] = "  xx    UU   xx      yy       ",
    435 		[Uw3] = "  xx    UUU  xx      yyy      ",
    436 		[Dw]  = "        U            yyy      ",
    437 		[Dw2] = "        UU           yy       ",
    438 		[Dw3] = "        UUU          y        ",
    439 		[Rw]  = "  yyyx  U    xxxy    x        ",
    440 		[Rw2] = "  yyyx  UU   xxxy    xx       ",
    441 		[Rw3] = "  yyyx  UUU  xxxy    xxx      ",
    442 		[Lw]  = "  yx    U    xxxyyy  xxx      ",
    443 		[Lw2] = "  yx    UU   xxxyyy  xx       ",
    444 		[Lw3] = "  yx    UUU  xxxyyy  x        ",
    445 		[Fw]  = "  xxx   U    x       yxxxyyy  ",
    446 		[Fw2] = "  xxx   UU   x       yxxyyy   ",
    447 		[Fw3] = "  xxx   UUU  x       yxyyy    ",
    448 		[Bw]  = "  x     U    xxx     yxyyy    ",
    449 		[Bw2] = "  x     UU   xxx     yxxyyy   ",
    450 		[Bw3] = "  x     UUU  xxx     yxxxyyy  ",
    451 
    452 		[M]   = "  yx  U    xx  UUU  yxyyy  ",
    453 		[M2]  = "  yx  UU   xx  UU   xxxy   ",
    454 		[M3]  = "  yx  UUU  xx  U    yxxxy  ",
    455 		[S]   = "  x   UUU  xx  U    yyyx   ",
    456 		[S2]  = "  x   UU   xx  UU   yyx    ",
    457 		[S3]  = "  x   U    xx  UUU  yx     ",
    458 		[E]   = "      U    xx  UUU  xxyyy  ",
    459 		[E2]  = "      UU   xx  UU   xxyy   ",
    460 		[E3]  = "      UUU  xx  U    xxy    ",
    461 
    462 		[x]   = "       x         ",
    463 		[x2]  = "       xx        ",
    464 		[x3]  = "       xxx       ",
    465 		[y]   = "       y         ",
    466 		[y2]  = "       yy        ",
    467 		[y3]  = "       yyy       ",
    468 		[z]   = "  yyy  x    y    ",
    469 		[z2]  = "  yy   xx        ",
    470 		[z3]  = "  y    x    yyy  "
    471 	};
    472 
    473 	const Cube mcu = {
    474 		.ep = { UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR },
    475 		.cp = { UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR },
    476 	};
    477 
    478 	const Cube mcx = {
    479 		.ep = { DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR },
    480 		.eo = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 },
    481 		.cp = { DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR },
    482 		.co = { [UFR] = 2, [UBR] = 1, [UFL] = 1, [UBL] = 2,
    483 			[DBR] = 2, [DFR] = 1, [DBL] = 1, [DFL] = 2 },
    484 	};
    485 
    486 	const Cube mcy = {
    487 		.ep = { UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL },
    488 		.eo = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 },
    489 		.cp = { UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL },
    490 	};
    491 
    492 	move_array[U] = mcu;
    493 	move_array[x] = mcx;
    494 	move_array[y] = mcy;
    495 
    496 	for (m = 0; m < NMOVES_ALL; m++) {
    497 		switch (m) {
    498 		case NULLMOVE:
    499 			make_solved(&move_array[m]);
    500 			break;
    501 		case U:
    502 		case x:
    503 		case y:
    504 			break;
    505 		default:
    506 			make_solved(&move_array[m]);
    507 			apply_scramble(equiv_alg_string[m], &move_array[m]);
    508 			break;
    509 		}
    510 	}
    511 }
    512 
    513 static void
    514 init_trans(void) {
    515 	Cube aux, cube;
    516 	Move mi, move;
    517 	Trans t, u, v;
    518 
    519 	for (t = 0; t < NTRANS; t++) {
    520 		for (mi = 0; mi < NMOVES_ALL; mi++) {
    521 			make_solved(&aux);
    522 			apply_move(mi, &aux);
    523 			apply_trans(t, &aux);
    524 			for (move = 0; move < NMOVES_ALL; move++) {
    525 				copy_cube(&aux, &cube);
    526 				apply_move(inverse_move(move), &cube);
    527 				if (is_solved(&cube)) {
    528 					moves_ttable[t][mi] = move;
    529 					break;
    530 				}
    531 			}
    532 		}
    533 	}
    534 
    535 	for (t = 0; t < NTRANS; t++) {
    536 		for (u = 0; u < NTRANS; u++) {
    537 			make_solved(&aux);
    538 			apply_scramble("R' U' F", &aux);
    539 			apply_trans(u, &aux);
    540 			apply_trans(t, &aux);
    541 			for (v = 0; v < NTRANS; v++) {
    542 				copy_cube(&aux, &cube);
    543 				apply_trans(v, &cube);
    544 				apply_scramble("F' U R", &cube);
    545 				if (is_solved(&cube)) {
    546 					/* This is the inverse of the correct
    547 					   value, it will be inverted later */
    548 					trans_ttable[t][u] = v;
    549 					if (v == uf)
    550 						trans_itable[t] = u;
    551 					break;
    552 				}
    553 			}
    554 		}
    555 	}
    556 	for (t = 0; t < NTRANS; t++)
    557 		for (u = 0; u < NTRANS; u++)
    558 			trans_ttable[t][u] = trans_itable[trans_ttable[t][u]];
    559 }
    560 
    561 void
    562 init_cube(void)
    563 {
    564 	init_moves();
    565 	init_trans();
    566 }
	nissy-fmc A Rubik's cube FMC assistant
	git clone https://git.tronto.net/nissy-fmc
	Download \| Log \| Files \| Refs \| README \| LICENSE