Commits

Anonymous committed 75615f5

first pass at continuing the search for shorter solutions, now it's time for cleanup

Comments (0)

Files changed (4)

 		}
 		printf("corner permutation is %d (%ssolved)\n", get_cp_coord()     , (current = get_cp_coord() ) ? "not " : ""); solved &= !current;
 		printf("edge   permutation is %d (%ssolved)\n", get_ep_coord()     , (current = get_ep_coord() ) ? "not " : ""); solved &= !current;
-		printf("fedge  permutation is %d (%ssolved)\n", get_ep_coord_full(), (current = get_ep_coord() ) ? "not " : ""); solved &= !current;
+		printf("fedge  permutation is %d (%ssolved)\n", get_ep_coord_full(), (current = get_ep_coord_full() ) ? "not " : ""); solved &= !current;
 
 		printf("\n");
 		printf("cube is %ssolved\n", solved ? "" : "not ");
+		fflush(stdout);
 	}
 
 	return !solved;
 {
 	char *faces = "UDFBRL", *num = " 2'";
 
-	printf("%c%c ", faces[mv / 3], num[mv % 3]);
+	if (mv < 0 || mv > 17) printf(".");
+	else printf("%c%c ", faces[mv / 3], num[mv % 3]);
 }
 
 /*
 
 int main(int argc, char **argv)
 {
-	char *p, *k, buf[32], faces[] = "UDFBRL", nums[] = " +1222'-3";
+	char *p, *k, buf[256], faces[] = "UDFBRL", nums[] = " +1222'-3";
 
 	int i, mv, last = undef, cur = undef;
 
 		fprintf(stderr, "malformed cube, assuming solved cube\n");
 	}
 
-	set_cube(start_cube);
+	strcpy(cube, start_cube);
+	set_cube(cube);
 
 	while (fgets(buf, sizeof(buf), stdin)) {
 		for (p = buf; *p; p++) {
 					do_move(mv);
 				get_cube(cube, sizeof(cube));
 				printf("%s\n", cube);
-				set_cube(start_cube);
+				fflush(stdout);
+				strcpy(cube, start_cube);
+				set_cube(cube);
 				cur = undef;
 			} else {
 				fprintf(stderr, "bad character %c\n", *p);
 	if (cur != undef) {
 		get_cube(cube, sizeof(cube));
 		printf("%s\n", cube);
+		fflush(stdout);
 	}
 
 	return 0;
  *
  * NOTE: values are 1 based due to current set_p_coord()
  */
+/* the co_ eo_ cp_ ep_ arrays are used to store the original cube state */
+uint8_t  co_[8],            eo_[12],           cp_[8],             ep_[12];
 uint8_t  co_prune[2187],    eo_prune[2048],    cp_prune[40320],    ep_prune[40320],    ud1_prune[495],    ud2_prune[24];
 uint16_t co_trans[2187][6], eo_trans[2048][6], cp_trans[40320][6], ep_trans[40320][6], ud1_trans[495][6], ud2_trans[24][6];
 
  * U D F B R L
  * 0 1 2 3 4 5
  */
-int sol[30];
+int sol[38];
+int len;
 
 /*
  * generic transition table initialization
 	init_prune(1, 0, ud2_prune, ud2_trans, 5, 0, -1);
 }
 
+void copy_cube(int set, uint8_t co_[8], uint8_t eo_[12], uint8_t cp_[8], uint8_t ep_[12])
+{
+	if (set) {
+		memcpy(co, co_, sizeof(co));
+		memcpy(eo, eo_, sizeof(eo));
+		memcpy(cp, cp_, sizeof(cp));
+		memcpy(ep, ep_, sizeof(ep));
+	} else {
+		memcpy(co_, co, sizeof(co));
+		memcpy(eo_, eo, sizeof(eo));
+		memcpy(cp_, cp, sizeof(cp));
+		memcpy(ep_, ep, sizeof(ep));
+	}
+	if (memcmp(co, co_, sizeof(co))) printf("co arrays differ\n");
+	if (memcmp(eo, eo_, sizeof(eo))) printf("eo arrays differ\n");
+	if (memcmp(cp, cp_, sizeof(cp))) printf("cp arrays differ\n");
+	if (memcmp(ep, ep_, sizeof(ep))) printf("ep arrays differ\n");
+}
+
 /*
  * phase solver
  */
+void phase2(int last);
+int p1_len;
+
 int solve(int phase, int e_coord, int c_coord, int ud_coord, int depth, int last)
 {
 	int i, e_tmp, c_tmp, ud_tmp, face;
 
-	if (e_coord == 0 && c_coord == 0 && ud_coord == 0) return 1; /* success! */
+	if (e_coord == 0 && c_coord == 0 && ud_coord == 0 && depth == 0) {
+		if (!phase) {
+			phase2(last);
+			return 0;
+		}
+		return 1; /* success! */
+	}
 	if (!phase && (depth == 0 || eo_prune[e_coord] > depth || co_prune[c_coord] > depth || ud1_prune[ud_coord] > depth)) return 0; /* test for phase G0 */
 	if ( phase && (depth == 0 || ep_prune[e_coord] > depth || cp_prune[c_coord] > depth || ud2_prune[ud_coord] > depth)) return 0; /* test for phase G1 */
 
 			c_tmp  = phase ? cp_trans [c_tmp ][face] : co_trans [c_tmp ][face];
 			ud_tmp = phase ? ud2_trans[ud_tmp][face] : ud1_trans[ud_tmp][face];
 
-			if (solve(phase, e_tmp, c_tmp, ud_tmp, depth - 1, face)) {
-				sol[(phase ? 30 : 12) - depth] = face * 3 + ((phase && face > 1) ? 1 : i);
-				return 1;
-			}
-			if (phase && face > 1)
-				break;
+			if (!phase) sol[20 - depth] = face * 3 + i;
+			else        sol[38 - depth] = face * 3 + ((face > 1) ? 1 : i);
+
+			if (solve(phase, e_tmp, c_tmp, ud_tmp, depth - 1, face)) return 1;
+			if (phase && face > 1) break;
 		}
 	}
 	return 0;
 }
 
-int main(void)
+void phase1(void)
+{
+	copy_cube(0, co_, eo_, cp_, ep_);
+
+	for (p1_len = 0; ; p1_len++) {
+		copy_cube(1, co_, eo_, cp_, ep_);
+		solve(0, get_eo_coord(), get_co_coord(), get_ud1_coord(), p1_len, -1);
+	}
+}
+
+void phase2(int last)
+{
+	int i, p2_len;
+
+	copy_cube(1, co_, eo_, cp_, ep_);
+	for (i = 20 - p1_len; i < 20; i++)
+		do_move(sol[i]);
+
+	for (p2_len = 0; p2_len + p1_len < len; p2_len++)
+		if (solve(1, get_ep_coord(), get_cp_coord(), get_ud2_coord(), p2_len, last))
+			break;
+
+	if (p2_len + p1_len >= len)
+		return;
+
+	len = p2_len + p1_len;
+
+	for (i = 20 - p1_len; i < 20; i++)
+		print_move(sol[i]);
+	for (i = 38 - p2_len; i < 38; i++)
+		print_move(sol[i]);
+
+	printf(" (%d)(%d,%d)\n", len, p1_len, p2_len);
+	//printf("\n");
+	fflush(stdout);
+}
+
+int main(int argc, char **argv)
 {
 	char buf[128];
 	int i;
 	init_trans_tables();
 	init_prune_tables();
 
-	/* Use to read a single cube as 1 or 20 arguments */
-	/*
 	*buf = '\0';
 	for (i = 1; i < argc; i++) {
 		strcat(buf, argv[i]);
 		strcat(buf, " ");
 	}
-	*/
+	memset(sol, -1, sizeof(sol));
+	len = 30;
+	set_cube(buf);
 
-	/* Use to continually read cubes from stdin */
-	while (fgets(buf, sizeof(buf), stdin)) {
-		memset(sol, -1, sizeof(sol));
-		set_cube(buf);
-
-		for (i = 0; solve(0, get_eo_coord(), get_co_coord(), get_ud1_coord(), i, -1) == 0; i++)
-			;
-
-		for (i = 12 - i; i < 12; i++)
-			do_move(sol[i]);
-
-		for (i = 0; solve(1, get_ep_coord(), get_cp_coord(), get_ud2_coord(), i, -1) == 0; 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[11] > -1 && sol[30 - i] > -1 && sol[30 - i] / 3 == sol[11] / 3) {
-			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");
-		fflush(stdout);
-	}
+	phase1();
 	return 0;
 }
 
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.