# Commits

committed 2d8368c

major refactoring of solve, removed ~ 80 SLOC, also faster now (with -O3)

• Participants
• Parent commits e2e81c7

# solve.c

` char co[8],             eo[12],            cp[8],              ep[12];`
` char co_prune[2187],    eo_prune[2048],    cp_prune[40320],    ep_prune[40320],    ud1_prune[495],    ud2_prune[24];`
` int  co_trans[2187][6], eo_trans[2048][6], cp_trans[40320][6], ep_trans[40320][6], ud1_trans[495][6], ud2_trans[24][6];`
`-int  co_coord,          eo_coord,          cp_coord,           ep_coord,           ud1_coord,         ud2_coord;`
` `
` /*`
`  * moves are:`
`  * U U2 U' D D2 D' F F2 F' B B2 B' R  R2 R' L  L2 L'`
`  * 0 1  2  3 4  5  6 7  8  9 10 11 12 13 14 15 16 17`
`  */`
`-int phase_1_moves[12], phase_2_moves[18]; // yuck, need a single array for all moves`
`+int sol[30];`
`+`
`+/*`
`+ * groups are:`
`+ * 0 = G0 = <U, D, F , B , R , L >`
`+ * 1 = G1 = <U, D, F2, B2, R2, L2>`
`+ */`
` `
` char c_cycles[6][4] = {`
` 	{ 0, 1, 2, 3 }, // U`
` };`
` `
` /*`
`- * takes a permutation and orientation (either cp and co, or ep and eo), and a`
`- * cycle and twist (an entry in the {c,e}_{cycles,twists} tables), and twists`
`- * and cycles the appropriate pieces`
`- *`
`- * NOTE: ok, worst explanation ever, I'll work on that`
`+ * perform the permutation cycle 1 - 3 times based on move`
`+ * perform the orientation twists on the cubies that are being cycled`
`  */`
` void move_pieces(char *perm, char *orie, char *cycle, char *twist, int mod)`
` {`
`-	char otmp, ptmp, *p;`
`+	char otmp, ptmp, i;`
` `
`-	ptmp = perm[*cycle];`
`-	otmp = orie[*cycle];`
`-	for (p = cycle; p - cycle < 3; p++) {`
`-		orie[*p] = (orie[*(p + 1)] + twist[p - cycle + 1]) % mod;`
`-		perm[*p] = perm[*(p + 1)];`
`+	ptmp = perm[cycle[0]];`
`+	otmp = orie[cycle[0]];`
`+	for (i = 0; i < 3; i++) {`
`+		orie[cycle[i]] = (orie[cycle[i + 1]] + twist[i + 1]) % mod;`
`+		perm[cycle[i]] =  perm[cycle[i + 1]];`
` 	}`
`-	orie[*p] = (otmp + twist[0]) % mod;`
`-	perm[*p] = ptmp;`
`+	orie[cycle[3]] = (otmp + twist[0]) % mod;`
`+	perm[cycle[3]] =  ptmp;`
` }`
` `
`+/*`
`+ * perform the given move on the array cube`
`+ */`
` void do_move(int mv)`
` {`
`-	int i, face;`
`+	int face = mv / 3;`
` `
`-	face = mv / 3;`
`-`
`-	for (i = 0; i < (mv % 3) + 1; i++) {`
`+	for (mv = mv % 3 + 1; mv; mv--) {`
` 		move_pieces(cp, co, c_cycles[face], c_twists[face], 3);`
` 		move_pieces(ep, eo, e_cycles[face], e_twists[face], 2);`
` 	}`
` }`
` `
`-int fact(int n)`
`-{`
`-	int i;`
`-`
`-	for (i = 1; n > 0; n--)`
`-		i *= n;`
`-`
`-	return i;`
`-}`
`-`
`-int choose(int n, int k)`
`-{`
`-	return fact(n)/(fact(k) * fact(n - k));`
`-}`
`+// math functions`
`+int fact [12] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800 };`
`+int choose(int n, int k) { return fact[n]/(fact[k] * fact[n - k]); }`
` `
` /*`
`  * coordinate functions`
`- * based on descriptions given at http://kociemba.org/math/twophase.htm`
`+ *`
`+ * the ud1 and ud2 coordinates are based on descriptions at http://kociemba.org/math/twophase.htm`
`+ * the oriention and permuation functions are based on descirptions at http://www.jaapsch.net/puzzles/compindx.htm`
`+ *`
`  * the get functions return the coordinate for the current state of the array cube`
`  * the set functions set the current state of the array cube to the given coordinate`
`  */`
`-void set_eo_coord(int coord)`
`-{`
`-	int i;`
` `
`-	eo[11] = 0;`
`-	for (i = 10; i >= 0; i--, coord >>= 1) {`
`-		eo[i] = coord & 1;`
`-		eo[11] ^= eo[i];`
`-	}`
`-}`
`-`
`-int get_eo_coord(void)`
`-{`
`-	int i, coord;`
`-`
`-	for (i = coord = 0; i < 11; i++, coord <<= 1)`
`-		coord |= eo[i];`
`-`
`-	return coord >> 1;`
`-}`
`-`
`-void set_co_coord(int coord)`
`-{`
`-	int i, p = 729;`
`-`
`-	co[7] = 0;`
`-	for (i = 6; i >= 0; i--, p /= 3) {`
`-		co[i] = coord / p;`
`-		coord -= co[i] * p;`
`-		co[7] = (co[7] + 3 - co[i]) % 3;`
`-	}`
`-}`
`-`
`-int get_co_coord(void)`
`-{`
`-	int i, p, coord;`
`-`
`-	for (i = coord = 0, p = 1; i < 7; i++, p *= 3)`
`-		coord += co[i] * p;`
`-`
`-	return coord;`
`-}`
`-`
`+/*`
`+ * ud1 coordinate`
`+ */`
` void set_ud1_coord(int coord)`
` {`
` 	int i, j;`
` `
`-	for (i = 0; i < 12; i++)`
`-		ep[i] = 0;`
`+	memset(ep, 0, 12);`
` 	for (i = 11, j = 4; i >= 0 && j; i--) {`
` 		if (coord >= choose(i, j - 1)) {`
` 			coord -= choose(i, j - 1);`
` 	int i, j = 0, coord = 0;`
` `
` 	for (i = 0; i < 12; i++) {`
`-		if (ep[i] > 7)`
`-			j++;`
`-		if (j && ep[i] < 8)`
`-			coord += choose(i, j - 1);`
`+		if (ep[i] > 7     ) j++;`
`+		if (ep[i] < 8 && j) coord += choose(i, j - 1);`
` 	}`
` 	return coord;`
` }`
` `
`-// set a permutation coordinate: cp, ep, ud2`
`+/*`
`+ * generic orientation coordinate`
`+ */`
`+void set_o_coord(char *orie, int len, int coord, int mod)`
`+{`
`+	int i, s = 0;`
`+`
`+	for (i = len - 2; i >= 0; i--) {`
`+		orie[i] = coord % mod;`
`+		s = (s - orie[i] + mod) % mod;`
`+		coord /= mod;`
`+	}`
`+	orie[len - 1] = s;`
`+}`
`+`
`+int get_o_coord(char *orie, int len, int mod)`
`+{`
`+	int i, coord = 0;`
`+`
`+	for (i = 0; i < len - 1; i++)`
`+		coord = coord * mod + orie[i];`
`+`
`+	return coord;`
`+}`
`+`
`+/*`
`+ * specific orientation coordinates`
`+ */`
`+void set_eo_coord(int coord) { set_o_coord(eo, 12, coord, 2); }`
`+void set_co_coord(int coord) { set_o_coord(co,  8, coord, 3); }`
`+`
`+int get_eo_coord(void) { return get_o_coord(eo, 12, 2); }`
`+int get_co_coord(void) { return get_o_coord(co,  8, 3); }`
`+`
`+/*`
`+ * generic permutation coordinate`
`+ */`
` void set_p_coord(char *perm, int len, int coord)`
` {`
`-	int i, j, k, p;`
`-	int used = 0; // haven't figure out a better way yet :-(`
`+	int i, j;`
` `
`-	p = fact(len - 1);`
`+	perm[len - 1] = 1;`
` `
`-	for (i = len - 1; i >= 0; i--) {`
`-		for (j = len - 1; used & (1 << j); j--)`
`-			;`
`-		for (k = 0; k < coord / p; j--)`
`-			if (!(used & (1 << j)))`
`-				k++;`
`-		for (; used & (1 << j); j--)`
`-			;`
`-`
`-		used |= 1 << j;`
`-		perm[i] = j;`
`-		coord %= p;`
`-		if (i)`
`-			p /= i;`
`+	for (i = len - 2; i >= 0; i--) {`
`+		perm[i] = (coord % (len - i)) + 1;`
`+		coord /= len - i;`
`+		for (j = i + 1; j < len; j++)`
`+			if (perm[j] >= perm[i])`
`+				perm[j]++;`
` 	}`
` }`
` `
` int get_p_coord(char *perm, int len)`
` {`
`-	int i, j, p, q, coord = 0;`
`+	int i, j, coord = 0;`
` `
`-	for (i = p = 1; i < len; p *= ++i) {`
`-		for (j = q = 0; j < i; j++)`
`-			if (perm[j] > perm[i])`
`-				q++;`
`-		coord += p * q;`
`+	for (i = 0; i < len - 1; i++) {`
`+		coord *= (len - i);`
`+		for (j = i + 1; j < len; j++)`
`+			if (perm[i] > perm[j])`
`+				coord++;`
` 	}`
` 	return coord;`
` }`
` `
`+/*`
`+ * specific permutation coordinates`
`+ */`
` void set_cp_coord (int coord) { set_p_coord(cp,     8, coord); }`
` void set_ep_coord (int coord) { set_p_coord(ep,     8, coord); }`
` void set_ud2_coord(int coord) { set_p_coord(ep + 8, 4, coord); }`
` int get_ep_coord (void) { return get_p_coord(ep,     8); }`
` int get_ud2_coord(void) { return get_p_coord(ep + 8, 4); }`
` `
`-// initialize a pruning table`
`-// group: 0 = G0 = <U, D, F , B , R , L >`
`-//        1 = G1 = <U, D, F2, B2, R2, L2>`
`-void init_prune(int group, int coord, char prune_table[], int tran_table[][6], int mdepth, int depth, int last)`
`+/*`
`+ * generic pruning table initialization`
`+ */`
`+void init_prune(int group, int coord, char prune_table[], int trans_table[][6], int mdepth, int depth, int last)`
` {`
`-	int i, mv, old;`
`+	int i, mv, old = coord;`
` `
` 	if (depth == mdepth || prune_table[coord] <= depth)`
` 		return;`
` `
` 	prune_table[coord] = depth;`
` `
`-	old = coord;`
`-	for (mv = 0; mv < 18; mv += 3) {`
`+	for (mv = 0; mv < 18; mv += 3, coord = old) {`
` 		if (mv / 3 == last / 3)`
` 			continue;`
` 		for (i = 0; i < 3; i++) {`
` 			if (group && mv >= 6 && i) // only want double turns on F, B, R, L in G1`
` 				break;`
`-			coord = tran_table[coord][mv / 3];`
`-			init_prune(group, coord, prune_table, tran_table, mdepth, depth + 1, mv);`
`+			coord = trans_table[coord][mv / 3];`
`+			init_prune(group, coord, prune_table, trans_table, mdepth, depth + 1, mv);`
` 		}`
`-		coord = old;`
` 	}`
` }`
` `
`+/*`
`+ * specific pruning table initializations`
`+ */`
` void init_prune_tables(void)`
` {`
` 	memset(eo_prune,  127, sizeof(eo_prune ));`
` 	memset(co_prune,  127, sizeof(co_prune ));`
`+	memset(ep_prune,  127, sizeof(ep_prune ));`
` 	memset(cp_prune,  127, sizeof(cp_prune ));`
`-	memset(ep_prune,  127, sizeof(ep_prune ));`
` 	memset(ud1_prune, 127, sizeof(ud1_prune));`
` 	memset(ud2_prune, 127, sizeof(ud2_prune));`
` `
` 	init_prune(1, 0, ud2_prune, ud2_trans, 5, 0, -1);`
` }`
` `
`+/*`
`+ * generic transition table initialization`
`+ */`
` void init_trans(int group, int tran_table[][6], int len, void (*set_coord)(int), int (*get_coord)(void))`
` {`
` 	int i, mv;`
` 	}`
` }`
` `
`+/*`
`+ * specific transition table initializations`
`+ */`
` void init_trans_tables(void)`
` {`
` 	init_trans(0, eo_trans,  2048,  set_eo_coord,  get_eo_coord );`
` 	init_trans(1, ud2_trans, 24,    set_ud2_coord, get_ud2_coord);`
` }`
` `
`-// last is 0-5 represents last face (thanks Tom)`
`-int phase_1(int eo_coord, int co_coord, int ud1_coord, int depth, int last)`
`+/*`
`+ * generic phase solver`
`+ */`
`+int solve(int group, int e_coord, int c_coord, int ud_coord, int depth, int last)`
` {`
`-	int mv;`
`-	int i, eo_tmp, co_tmp, ud1_tmp, face;`
`+	int mv, i, e_tmp, c_tmp, ud_tmp, face;`
` `
`-	if (eo_coord == 0 && co_coord == 0 && ud1_coord == 0)`
`-		return 1;`
`+	if (e_coord == 0 && c_coord == 0 && ud_coord == 0) return 1; // success!`
`+	if (!group && (depth == 0 || eo_prune[e_coord] > depth || co_prune[c_coord] > depth || ud1_prune[ud_coord] > depth)) return 0;`
`+	if ( group && (depth == 0 || ep_prune[e_coord] > depth || cp_prune[c_coord] > depth || ud2_prune[ud_coord] > depth)) return 0;`
` `
`-	if (depth == 0 || eo_prune[eo_coord] > depth || co_prune[co_coord] > depth || ud1_prune[ud1_coord] > depth)`
`-		return 0;`
`-`
`-	for (mv = 0; mv < 18; mv += 3) {`
`-		face = mv / 3;`
`+	for (mv = face = 0; mv < 18; mv += 3, face = mv / 3) {`
` 		// no two moves in a row on same face, no move on same axis after U, F, R`
` 		if (face == last || ((last & 1) == 0 && face == last + 1))`
` 			continue;`
` `
`-		eo_tmp  = eo_coord;`
`-		co_tmp  = co_coord;`
`-		ud1_tmp = ud1_coord;`
`+		e_tmp  = e_coord;`
`+		c_tmp  = c_coord;`
`+		ud_tmp = ud_coord;`
` `
` 		for (i = 0; i < 3; i++) {`
`-			eo_tmp  = eo_trans [eo_tmp ][face];`
`-			co_tmp  = co_trans [co_tmp ][face];`
`-			ud1_tmp = ud1_trans[ud1_tmp][face];`
`+			e_tmp  = group ? ep_trans [e_tmp ][face] : eo_trans [e_tmp ][face];`
`+			c_tmp  = group ? cp_trans [c_tmp ][face] : co_trans [c_tmp ][face];`
`+			ud_tmp = group ? ud2_trans[ud_tmp][face] : ud1_trans[ud_tmp][face];`
` `
`-			if (phase_1(eo_tmp, co_tmp, ud1_tmp, depth - 1, face)) {`
`-				phase_1_moves[depth - 1] = mv + i;`
`+			if (solve(group, e_tmp, c_tmp, ud_tmp, depth - 1, face)) {`
`+				sol[(group ? 30 : 12) - depth] = mv + ((group && mv >= 6) ? 1 : i);`
` 				return 1;`
` 			}`
`-		}`
`-	}`
`-	return 0;`
`-}`
`-`
`-int phase_2(int ep_coord, int cp_coord, int ud2_coord, int depth, int last)`
`-{`
`-	int mv;`
`-	int i, ep_tmp, cp_tmp, ud2_tmp, face;`
`-`
`-	if (ep_coord == 0 && cp_coord == 0 && ud2_coord == 0)`
`-		return 1;`
`-`
`-	if (depth == 0 || ep_prune[ep_coord] > depth || cp_prune[cp_coord] > depth || ud2_prune[ud2_coord] > depth)`
`-		return 0;`
`-`
`-	for (mv = 0; mv < 18; mv += 3) {`
`-		face = mv / 3;`
`-		// no two moves in a row on same face, no move on same axis after U, F, R`
`-		if (face == last || ((last & 1) == 0 && face == last + 1))`
`-			continue;`
`-`
`-		ep_tmp  = ep_coord;`
`-		cp_tmp  = cp_coord;`
`-		ud2_tmp = ud2_coord;`
`-`
`-		for (i = (mv >= 6) ? 1 : 0; i < 3; i++) { // fancy (read yucky) stuff for G1`
`-			ep_tmp  = ep_trans [ep_tmp ][face];`
`-			cp_tmp  = cp_trans [cp_tmp ][face];`
`-			ud2_tmp = ud2_trans[ud2_tmp][face];`
`-`
`-			if (phase_2(ep_tmp, cp_tmp, ud2_tmp, depth - 1, face)) {`
`-				phase_2_moves[depth - 1] = mv + i;`
`-				return 1;`
`-			}`
`-			if (mv >= 6)`
`+			if (group && mv >= 6)`
` 				break;`
` 		}`
` 	}`
` `
` void print_move(int mv)`
` {`
`-	char *faces = "UDFBRL";`
`-	char *num   = " 2'";`
`+	char *faces = "UDFBRL", *num = " 2'";`
` `
`-	if (mv == -1) return;`
` 	printf("%c%c ", faces[mv / 3], num[mv % 3]);`
` }`
` `
`+/*`
`+ * set array cube from input`
`+ */`
` void set_cube(char *cube)`
` {`
`-	char *p, *t;`
`-	int i, j;`
`+	char *p, *t, i, j;`
` `
` 	for (i = 0, p = strtok(cube, " \n"); p && i < 12; i++, p = strtok(NULL, " \n")) {`
`-		for (j = 0; j < 12; j++) {`
`-			if ((t = strstr(names[j], p)) != NULL) {`
`-				ep[i] = j;`
`-				eo[i] = t - names[j];`
`-			}`
`-		}`
`+		for (j = 0; (t = strstr(names[j], p)) == NULL; j++)`
`+			;`
`+		ep[i] = j;`
`+		eo[i] = t - names[j];`
` 	}`
` `
` 	for (i = 0; p && i < 8; i++, p = strtok(NULL, " \n")) {`
`-		for (j = 0; j < 8; j++) {`
`-			if ((t = strstr(names[j + 12], p)) != NULL) {`
`-				cp[i] = j;`
`-				co[i] = t - names[j + 12];`
`-			}`
`-		}`
`+		for (j = 0; (t = strstr(names[j + 12], p)) == NULL; j++)`
`+			;`
`+		cp[i] = j;`
`+		co[i] = t - names[j + 12];`
` 	}`
`-`
`-	co_coord  = get_co_coord();`
`-	eo_coord  = get_eo_coord();`
`-	ud1_coord = get_ud1_coord();`
` }`
` `
` int main(int argc, char **argv)`
` {`
`-	char buf[256] = {0};`
`-	int i;`
`+	char buf[128], i;`
` `
`-	ep_coord = cp_coord = ud2_coord = 0;`
` 	init_trans_tables();`
` 	init_prune_tables();`
` `
` 	while (fgets(buf, sizeof(buf), stdin)) {`
`-		memset(phase_1_moves, -1, sizeof(phase_1_moves));`
`-		memset(phase_2_moves, -1, sizeof(phase_2_moves));`
`+		memset(sol, -1, sizeof(sol));`
` 		set_cube(buf);`
` `
`-		for (i = 0; phase_1(eo_coord, co_coord, ud1_coord, i, -1) == 0; i++)`
`+		for (i = 0; solve(0, get_eo_coord(), get_co_coord(), get_ud1_coord(), i, -1) == 0; i++)`
` 			;`
` `
`-		for (i = 11; i > -1; i--)`
`-			if (phase_1_moves[i] != -1)`
`-				do_move(phase_1_moves[i]);`
`+		for (i = 12 - i; i < 12; i++)`
`+			do_move(sol[i]);`
` `
`-		ep_coord  = get_ep_coord();`
`-		cp_coord  = get_cp_coord();`
`-		ud2_coord = get_ud2_coord();`
`-`
`-		for (i = 0; phase_2(ep_coord, cp_coord, ud2_coord, i, -1) == 0; i++)`
`+		for (i = 0; solve(1, get_ep_coord(), get_cp_coord(), get_ud2_coord(), i, -1) == 0; i++)`
` 			;`
` `
`-		for (i = 11; i > -1; i--)`
`-			print_move(phase_1_moves[i]);`
`-		for (i = 17; i > -1; i--)`
`-			print_move(phase_2_moves[i]);`
`+		// if the last move from phase 1 and first move from phase 2 are on the same face`
`+		// it will always be a quarter turn then half turn on FBLR`
`+		if (sol[30 - i] > -1 && sol[30 - i] / 6 == sol[11] / 6) {`
`+			sol[30 - i] = -1;`
`+			sol[11] += (sol[11] % 3) ? -2 : 2;`
`+		}`
`+`
`+		for (i = 0; i < 30; i++)`
`+			if (sol[i] > -1)`
`+				print_move(sol[i]);`
`+`
` 		printf("\n");`
` 	}`
`-`
` 	return 0;`
` }`
` `