Anonymous avatar Anonymous committed 4e603b7

add some options, a little cleanup

Comments (0)

Files changed (2)

 
 solve
 -----
-no move on same face from phase 1 to 2, may create longer scrambles, but easier to count solution length and continuing searches will make up for it
-use own stack instead of recursion so I can continue from where I left off in phase 1 to search for shorter solutions
-serialize and print/read state of solver so I can continue from where I left off to search for shorter solutions
+is a phase 1 length of 0 indicative of an optimal solution?
+-p option is broken, timer interupts screw us up
 bigger/combined pruning tables
 serialize and print/read tables (helpful for when they're bigger)
 use symmetry to make tables/searches smaller
 gui
 ---
 maybe?...
+paint cube, spit out cube state
 talk through pipelines to rand, check, valid, solver, etc.
 
 other
+#include <signal.h>
 #include <stdio.h>
+#include <stdlib.h>
 #include <string.h>
+#include <unistd.h>
+
+#include <sys/time.h>
 
 #include "cubeutils.h"
 
  * U D F B R L
  * 0 1 2 3 4 5
  */
-int sol[38];
-int len;
+/* sol_ holds the current full solution */
+int sol[38], sol_[38];
+int num, len, p1_len = 0, p2_len;
+
+int max_len = 30;
+int num_sol = 0;
+int print_all = 1;
+int timeout = 0;
+int verbose = 0;
 
 /*
  * generic transition table initialization
 		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");
+}
+
+void print_solution(void)
+{
+	int i;
+
+	for (i = 20 - p1_len; i < 20; i++)
+		print_move(sol[i]);
+	for (i = 38 - p2_len; i < 38; i++)
+		print_move(sol[i]);
+
+	if (verbose) printf(" (%d)(%d,%d)", len, p1_len, p2_len);
+	printf("\n");
+	fflush(stdout);
 }
 
 /*
  * 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;
+	int i, e_tmp, c_tmp, ud_tmp, face, success;
 
-	if (e_coord == 0 && c_coord == 0 && ud_coord == 0 && depth == 0) {
-		if (!phase) {
-			phase2(last);
+	if (timeout && num) return 1;
+	if (e_coord == 0 && c_coord == 0 && ud_coord == 0 && depth == 0) { /* found a solution at the desired depth */
+		if (!phase) { /* we are in the first phase, let's do the second phase */
+			//if (depth != 0) return 0;
+			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 ((success = solve(1, get_ep_coord(), get_cp_coord(), get_ud2_coord(), p2_len, last)))
+					break;
+			if (success && p2_len + p1_len <= len) {
+				len = p2_len + p1_len;
+				if (print_all) {
+					print_solution();
+				} else {
+					memset(sol_, -1, sizeof(sol));
+					for (i = 20 - p1_len; i < 20; i++)
+						sol_[i] = sol[i];
+					for (i = 38 - p2_len; i < 38; i++)
+						sol_[i] = sol[i];
+				}
+				num++;
+				return (p2_len == 0 || len <= max_len || (num >= num_sol && num_sol));
+			}
 			return 0;
+		} else { /* we are in the second phase, we have a full solution, success! */
+			return 1;
 		}
-		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 */
 	return 0;
 }
 
-void phase1(void)
+void timeout_handler(int unused)
 {
-	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);
+	timeout = 1;
 }
 
 int main(int argc, char **argv)
 {
+	struct sigaction s = { .sa_handler = timeout_handler };
+	struct itimerval iv;
+	struct timeval tv;
+
 	char buf[128];
 	int i;
 
+	while ((i = getopt(argc, argv, "l:n:pt:v")) != -1) {
+		switch (i) {
+			case 'l': max_len = atoi(optarg); break;
+			case 'n': num_sol = atoi(optarg); break;
+			case 'p': print_all = 0;          break;
+			case 't': timeout = atoi(optarg); break;
+			case 'v': verbose = 1;            break;
+			default : printf("bad argument\n"); exit(EXIT_FAILURE);
+		}
+	}
+
 	init_trans_tables();
 	init_prune_tables();
 
-	*buf = '\0';
-	for (i = 1; i < argc; i++) {
-		strcat(buf, argv[i]);
-		strcat(buf, " ");
+	if (timeout) {
+		if (sigaction(SIGVTALRM, &s, NULL) < 0) {
+			printf("sigaction failed\n");
+			exit(EXIT_FAILURE);
+		}
+
+		timeout  *= 1000; // ms to us
+		tv.tv_sec  = timeout / 1000000;
+		tv.tv_usec = timeout % 1000000;
+
+		iv.it_value    = tv;
+		iv.it_interval = (struct timeval){ 0, 0 };
 	}
-	memset(sol, -1, sizeof(sol));
-	len = 30;
-	set_cube(buf);
 
-	phase1();
+	while (fgets(buf, sizeof(buf), stdin)) {
+		set_cube(buf);
+
+		memset(sol, -1, sizeof(sol));
+		num = 0;
+		len = max_len;
+		timeout = 0;
+		copy_cube(0, co_, eo_, cp_, ep_);
+
+		if (iv.it_value.tv_sec || iv.it_value.tv_usec)
+			setitimer(ITIMER_VIRTUAL, &iv, NULL);
+
+		for (p1_len = 0; p1_len <= len && solve(0, get_eo_coord(), get_co_coord(), get_ud1_coord(), p1_len, -1) == 0; p1_len++) {
+			if (verbose) printf("finished phase 1 search depth %d\n", p1_len);
+			copy_cube(1, co_, eo_, cp_, ep_);
+		}
+
+		if (!print_all) {
+			for (i = 0; i < 38; i++)
+				if (sol_[i] > -1)
+					print_move(sol_[i]);
+			printf("\n");
+			fflush(stdout);
+		}
+		if (verbose) printf("----------\n");
+	}
+
 	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.