Commits

Anonymous committed 2d8368c

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

  • Participants
  • Parent commits e2e81c7

Comments (0)

Files changed (1)

 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;
 }