Commits

Anonymous committed 865b832

fixed and better pruning table for 2_solve (although guess it's not a pruning table anymore is it?)

Comments (0)

Files changed (1)

stand_alone/2_solve.c

 }
 
 /*
- * specific transition table initializations
- */
-void init_trans_tables(void)
-{
-	init_trans(cp_trans, 5040, set_cp_coord, get_cp_coord );
-	init_trans(co_trans,  729, set_co_coord, get_co_coord );
-}
-
-/*
  * generic pruning table initialization
  */
+// store the depth in the first nibble, the face we turned to get there in the second nibble
+#define PD(x) ((x) & 0x0f)
+#define PF(x) (((x) & 0xc0) >> 6)
+#define PN(x) (((x) & 0x30) >> 4)
 void init_prune(uint16_t trans_tablei[][3], uint16_t trans_tablej[][3], int maxi, int maxj, uint8_t prune_table[maxi][maxj], int mdepth)
 {
 	int d, i, j, k, face;
 
-	prune_table[0][0] = 0;
+	prune_table[0][0] = 0xc0;
 
 	for (d = 0; d < mdepth; d++) {
 		for (i = 0; i < maxi; i++) {
 			for (j = 0; j < maxj; j++) {
-				if (prune_table[i][j] != d)
+				if (PD(prune_table[i][j]) != d)
 					continue;
 				for (face = 0; face < 3; face++) {
+					if (PF(prune_table[i][j]) == face)
+						continue;
 					int ni = i, nj = j;
 					for (k = 0; k < 3; k++) {
 						ni = trans_tablei[ni][face];
 						nj = trans_tablej[nj][face];
 						if (prune_table[ni][nj] == 0xff)
-							prune_table[ni][nj] = d + 1;
+							prune_table[ni][nj] = (d + 1) | (face << 6) | ((2 - k) << 4);
 					}
 				}
 			}
 }
 
 /*
- * specific pruning table initializations
- */
-void init_prune_tables(void)
-{
-	memset(cpco_prune, 0xff, sizeof(cpco_prune));
-	init_prune(cp_trans, co_trans, 5040, 729, cpco_prune, 11);
-}
-
-void print_move(int mv)
-{
-	char *faces = "UFL", *num = " 2'";
-
-	printf("%c%c ", faces[mv / 3], num[mv % 3]);
-}
-
-/*
  * solve
  */
 int solve(int cp_coord, int co_coord)
 {
-	int face, i, cp_tmp, co_tmp;
-	int distance = cpco_prune[cp_coord][co_coord];
+	char *faces = "UFL", *nums = " 2'";
+	int face, num, i, distance = PD(cpco_prune[cp_coord][co_coord]);
 
-	while (distance) {
-		for (face = 0; face < 3; face++) {
-			cp_tmp = cp_coord;
-			co_tmp = co_coord;
+	while (distance--) {
+		face = PF(cpco_prune[cp_coord][co_coord]);
+		num  = PN(cpco_prune[cp_coord][co_coord]);
 
-			for (i = 0; i < 3; i++) {
-				cp_tmp = cp_trans[cp_tmp][face];
-				co_tmp = co_trans[co_tmp][face];
-
-				if (cpco_prune[cp_tmp][co_tmp] < distance) {
-					print_move(face * 3 + i);
-					distance--;
-					cp_coord = cp_tmp;
-					co_coord = co_tmp;
-					i = face = 3;
-				}
-			}
+		for (i = 0; i <= num; i++) {
+			cp_coord = cp_trans[cp_coord][face];
+			co_coord = co_trans[co_coord][face];
 		}
+		printf("%c%c ", faces[face], nums[num]);
 	}
 	printf("\n");
 }
 int main(void)
 {
 	char buf[128];
-	int i;
 
-	init_trans_tables();
-	init_prune_tables();
+	memset(cpco_prune, 0xff, sizeof(cpco_prune));
+	init_trans(cp_trans, 5040, set_cp_coord, get_cp_coord );
+	init_trans(co_trans,  729, set_co_coord, get_co_coord );
+	init_prune(cp_trans, co_trans, 5040, 729, cpco_prune, 11);
 
+	// this will solve every possible cube, without the need to parse them (set_cube() is slow)
+	/*
+	int i, j;
+	for (i = 0; i < 5040; i++)
+		for (j = 0; j < 729; j++)
+			solve(i, j);
+	*/
 	while (fgets(buf, sizeof(buf), stdin)) {
 		set_cube(buf);
 		solve(get_cp_coord(), get_co_coord());