Anonymous avatar Anonymous committed 7319915

get rid of all the options. worry about those when the code is clean and fast

Comments (0)

Files changed (1)

 
 #include "cubeutils.h"
 
+#define verbose_printf(fmt, args...) ({ if (verbose) { printf(fmt, ##args); fflush(stdout); } })
+
 #define TABLES_PATH ".tables"
 enum { PHASE1 = 0, PHASE2 = 1 };
 /*
  * 0 1 2 3 4 5
  */
 int sol[38];
-int num, len, p1_len = 0, p2_len, old_len;
+int len, p1_len = 0, p2_len, old_len;
 char sol_str[128];
 
-struct itimerval iv;
-int target = 0;
-int num_cps = 0;
-int optimal = 0;
-int max_p1d = 0;
+int verbose = 0;
+int sigtstp = 0;
 int one_sol = 0;
-int interval= 0;
-int gen_tab = 0;
-int all_sol = 0;
-int max_len = 0;
-int end_len = 0;
-int num_sol = 0;
-int timeout = 0;
-int sigtstp = 0;
-int verbose = 0;
 
 /*
  * generic transition table initialization
  */
 void init_trans_tables(void)
 {
-	if (verbose) { printf("Initializing phase 1 transition tables..."); fflush(stdout); }
+	verbose_printf("Initializing phase 1 transition tables...");
 	init_trans(PHASE1, eo_trans,  2048,  set_eo_coord,  get_eo_coord );
 	init_trans(PHASE1, co_trans,  2187,  set_co_coord,  get_co_coord );
 	init_trans(PHASE1, ud1_trans,  495,  set_ud1_coord, get_ud1_coord);
-	if (verbose) printf("done\n");
+	verbose_printf("done\n");
 
-	if (verbose) { printf("Initializing phase 2 transition tables..."); fflush(stdout); }
+	verbose_printf("Initializing phase 2 transition tables...");
 	init_trans(PHASE2, cp_trans,  40320, set_cp_coord,  get_cp_coord );
 	init_trans(PHASE2, ep_trans,  40320, set_ep_coord,  get_ep_coord );
 	init_trans(PHASE2, ud2_trans,    24, set_ud2_coord, get_ud2_coord);
-	if (verbose) printf("done\n");
+	verbose_printf("done\n");
 }
 
 void init_p2_prune(void)
 
 	SET_P2_PRUNE(0, 0, 0);
 
-	if (verbose) printf("\nDepth: 0.");
+	verbose_printf("\nDepth: 0.");
 	for (d = 0; d < 13; d++) {
-		if (verbose) { printf("%d.", d + 1); fflush(stdout); }
+		verbose_printf("%d.", d + 1);
 		for (c = 0; c < maxc; c++) {
 			for (e = 0; e < maxe; e++) {
 				if (GET_P2_PRUNE(c, e) != d % 3)
 		}
 	}
 	for (d = 13; d < 18; d++) {
-		if (verbose) { printf("%d.", d + 1); fflush(stdout); }
+		verbose_printf("%d.", d + 1);
 		for (c = 0; c < maxc; c++) {
 			for (e = 0; e < maxe; e++) {
 				if (GET_P2_PRUNE(c, e) == 0x03) {
 
 	SET_P1_PRUNE(0, 0, 0, 0);
 
-	if (verbose) printf("\nDepth: 0.");
+	verbose_printf("\nDepth: 0.");
 	for (d = 0; d < 9; d++) {
-		if (verbose) { printf("%d.", d + 1); fflush(stdout); }
+		verbose_printf("%d.", d + 1);
 		for (c = 0; c < maxc; c++) {
 			for (e = 0; e < maxe; e++) {
 				for (ud = 0; ud < maxud; ud++) {
 		}
 	}
 	for (d = 9; d < 12; d++) {
-		if (verbose) { printf("%d.", d + 1); fflush(stdout); }
+		verbose_printf("%d.", d + 1);
 		for (c = 0; c < maxc; c++) {
 			for (e = 0; e < maxe; e++) {
 				for (ud = 0; ud < maxud; ud++) {
 	memset(p1_prune, 0xff, sizeof(p1_prune));
 	memset(p2_prune, 0xff, sizeof(p2_prune));
 
-	if (verbose) { printf("Initializing phase 1 pruning table..."); fflush(stdout); }
+	verbose_printf("Initializing phase 1 pruning table...");
 	init_p1_prune();
-	if (verbose) printf("done\n");
+	verbose_printf("done\n");
 
-	if (verbose) { printf("Initializing phase 2 pruning table..."); fflush(stdout); }
+	verbose_printf("Initializing phase 2 pruning table...");
 	init_p2_prune();
-	if (verbose) printf("done\n");
+	verbose_printf("done\n");
 }
 
 void copy_cube(int set, uint8_t co_[8], uint8_t eo_[12], uint8_t cp_[8], uint8_t ep_[12])
 {
 	if (!old) sprint_solution(sol_str);
 	printf("%s", sol_str);
-	if (verbose) printf(" (%d)(%d,%d)", len, p1_len, p2_len);
+	verbose_printf(" (%d)(%d,%d)", len, p1_len, p2_len);
 	printf("\n");
 	fflush(stdout);
 }
 
 int find_p1_depth(int c, int e, int ud)
 {
-	int i, j, face, c_tmp, e_tmp, ud_tmp;
+	int i, j, face, c_tmp, e_tmp, ud_tmp, p;
 
 	for (i = 0; c || e || ud; i++) {
+		p = GET_P1_PRUNE(c, e, ud);
 		for (face = 0; face < 6; face++) {
 			c_tmp  = c;
 			e_tmp  = e;
 				c_tmp  = co_trans [c_tmp ][face];
 				e_tmp  = eo_trans [e_tmp ][face];
 				ud_tmp = ud1_trans[ud_tmp][face];
-				if ((GET_P1_PRUNE(c_tmp, e_tmp, ud_tmp) + 1) % 3 == GET_P1_PRUNE(c, e, ud)) {
+				if ((GET_P1_PRUNE(c_tmp, e_tmp, ud_tmp) + 1) % 3 == p) {
 					c  = c_tmp;
 					e  = e_tmp;
 					ud = ud_tmp;
 	return i;
 }
 
-int find_p2_depth(int c, int e)
+int find_p2_depth(int c, int e, int max)
 {
-	int i, j, face, c_tmp, e_tmp;
+	int i, j, face, c_tmp, e_tmp, p;
 
-	for (i = 0; c || e; i++) {
+	for (i = 0; i < max && (c || e); i++) {
+		p = GET_P2_PRUNE(c, e);
 		for (face = 0; face < 6; face++) {
 			c_tmp = c;
 			e_tmp = e;
 			for (j = 0; j < 3; j++) {
 				c_tmp = cp_trans[c_tmp][face];
 				e_tmp = ep_trans[e_tmp][face];
-				if ((GET_P2_PRUNE(c_tmp, e_tmp) + 1) % 3 == GET_P2_PRUNE(c, e)) {
+				if ((GET_P2_PRUNE(c_tmp, e_tmp) + 1) % 3 == p) {
 					c = c_tmp;
 					e = e_tmp;
 					face = 6;
 
 int begin_phase2(int last)
 {
-	int i, solved = 0, prune_depth;
+	int i, cp, ep, prune_depth, max_depth, solved = 0;
 
 	copy_cube(1, co_, eo_, cp_, ep_);
 	for (i = 20 - p1_len; i < 20; i++)
 		do_move(sol[i]);
 
-	prune_depth = find_p2_depth(get_cp_coord(), get_ep_coord());
-	for (p2_len = prune_depth; (!all_sol && p2_len + p1_len < len) || (all_sol && p2_len + p1_len <= len); p2_len++) {
-		if ((solved = solve(PHASE2, get_cp_coord(), get_ep_coord(), get_ud2_coord(), p2_len, prune_depth, last)) || optimal)
+
+	cp = get_cp_coord();
+	ep = get_ep_coord();
+	max_depth   = len - p1_len;
+	prune_depth = find_p2_depth(cp, ep, max_depth);
+	for (p2_len = prune_depth; p2_len < max_depth; p2_len++) {
+		if ((solved = phase2(cp, ep, get_ud2_coord(), p2_len, prune_depth, last)))
 			break;
 	}
 	if (solved <= 0)
 		return solved;
-	if ((!all_sol && p2_len + p1_len < len) || (all_sol && p2_len + p1_len <= len)) {
-		if (interval && (iv.it_value.tv_sec || iv.it_value.tv_usec))
-			if (setitimer(ITIMER_REAL, &iv, NULL) < 0)
-				printf("setitimer failed\n");
-		len = p2_len + p1_len;
-		if (one_sol) sprint_solution(sol_str);
-		else         print_solution(0);
-		num++;
-		return (sigtstp || timeout || p2_len == 0 || len <= end_len || (num >= num_sol && num_sol));
-	}
-	return 0;
+
+	len = p2_len + p1_len;
+	print_solution(0);
+	return p2_len == 0 || one_sol;
 }
 /*
  * phase solver
  */
-int solve(int phase, int c_coord, int e_coord, int ud_coord, int depth, int prune_depth, int last)
+int phase1(int c_coord, int e_coord, int ud_coord, int depth, int prune_depth, int last)
 {
 	int i, e_tmp, c_tmp, ud_tmp, face, solved;
 	int np, cp;
 	int dp[3] = { 0, -1, 1 };
 
-	if (sigtstp || (timeout && num)) return -1;
-	if (e_coord == 0 && c_coord == 0 && ud_coord == 0) { /* found a solution */
-		if (phase == PHASE2) return 1;
-		else if (depth != 0) return 0;
-		else return begin_phase2(last);
-	}
-	/* would it make sense to move these checks down to _before_ a call to solve? didn't notice a big improvement */
-	if (depth == 0 || prune_depth > depth) return 0;
+	if (sigtstp) return -1;
+	if (e_coord == 0 && c_coord == 0 && ud_coord == 0) /* found a solution */
+		return depth ? 0 : begin_phase2(last);
+	if (depth == 0) return 0;
 
-	if (phase == PHASE1) cp = GET_P1_PRUNE(c_coord, e_coord, ud_coord);
-	else                 cp = GET_P2_PRUNE(c_coord, e_coord);
+	cp = GET_P1_PRUNE(c_coord, e_coord, ud_coord);
 
 	for (face = 0; face < 6; face++) {
 		/* no two moves in a row on same face, no move on same axis after U, F, R */
 		ud_tmp = ud_coord;
 
 		for (i = 0; i < 3; i++) {
-			e_tmp  = (phase == PHASE1) ? eo_trans [e_tmp ][face] : ep_trans [e_tmp ][face];
-			c_tmp  = (phase == PHASE1) ? co_trans [c_tmp ][face] : cp_trans [c_tmp ][face];
-			ud_tmp = (phase == PHASE1) ? ud1_trans[ud_tmp][face] : ud2_trans[ud_tmp][face];
+			e_tmp  = eo_trans [e_tmp ][face];
+			c_tmp  = co_trans [c_tmp ][face];
+			ud_tmp = ud1_trans[ud_tmp][face];
+			np     = GET_P1_PRUNE(c_tmp, e_tmp, ud_tmp);
 
-			if (phase == PHASE1) sol[20 - depth] = face * 3 + i;
-			else                 sol[38 - depth] = face * 3 + ((face > 1) ? 1 : i);
+			if ((depth == prune_depth     && (np + 1) % 3 != cp) ||
+			    (depth == prune_depth + 1 && (cp + 1) % 3 == np))
+				continue;
 
-			if (phase == PHASE1) np = prune_depth + dp[(cp - GET_P1_PRUNE(c_tmp, e_tmp, ud_tmp) + 3) % 3];
-			else                 np = prune_depth + dp[(cp - GET_P2_PRUNE(c_tmp, e_tmp) + 3) % 3];
+			np = prune_depth + dp[(cp - np + 3) % 3];
+			sol[20 - depth] = face * 3 + i;
 
-			if ((solved = solve(phase, c_tmp, e_tmp, ud_tmp, depth - 1, np, face))) return solved;
-			if (phase == PHASE2 && face > 1) break;
+			if ((solved = phase1(c_tmp, e_tmp, ud_tmp, depth - 1, np, face)))
+				return solved;
+		}
+	}
+	return 0;
+}
+int phase2(int c_coord, int e_coord, int ud_coord, int depth, int prune_depth, int last)
+{
+	int i, e_tmp, c_tmp, ud_tmp, face, solved;
+	int np, cp;
+	int dp[3] = { 0, -1, 1 };
+
+	if (sigtstp) return -1;
+	if (e_coord == 0 && c_coord == 0 && ud_coord == 0) /* found a solution */
+		return 1;
+	if (depth == 0) return 0;
+
+	cp = GET_P2_PRUNE(c_coord, e_coord);
+
+	for (face = 0; face < 6; face++) {
+		/* 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;
+
+		e_tmp  = e_coord;
+		c_tmp  = c_coord;
+		ud_tmp = ud_coord;
+
+		for (i = 0; i < 3; i++) {
+			if (face > 1)
+				i = 3;
+
+			e_tmp  = ep_trans [e_tmp ][face];
+			c_tmp  = cp_trans [c_tmp ][face];
+			ud_tmp = ud2_trans[ud_tmp][face];
+			np     = GET_P2_PRUNE(c_tmp, e_tmp);
+
+			if ((depth == prune_depth     && (np + 1) % 3 != cp) ||
+			    (depth == prune_depth + 1 && (cp + 1) % 3 == np))
+				continue;
+
+			np = prune_depth + dp[(cp - np + 3) % 3];
+			sol[38 - depth] = face * 3 + ((face > 1) ? 1 : i);
+
+			if ((solved = phase2(c_tmp, e_tmp, ud_tmp, depth - 1, np, face)))
+				return solved;
 		}
 	}
 	return 0;
 void signal_handler(int signal)
 {
 	switch (signal) {
-		case SIGALRM  :
-		case SIGVTALRM: timeout = 1; break;
 		case SIGTSTP  : sigtstp = 1; break;
 	}
 }
 		printf("failed to open/create table file\n");
 		exit(EXIT_FAILURE);
 	}
+	verbose_printf("Saving tables...");
 	write_all(fd, co_trans, sizeof(co_trans));
 	write_all(fd, eo_trans, sizeof(eo_trans));
 	write_all(fd, ud1_trans, sizeof(ud1_trans));
 
 	write_all(fd, p1_prune, sizeof(p1_prune));
 	write_all(fd, p2_prune, sizeof(p2_prune));
+	verbose_printf("done\n");
 
 	if (close(fd) < 0) {
 		printf("failed to close table file\n");
 		printf("failed to open table file\n");
 		exit(EXIT_FAILURE);
 	}
+	verbose_printf("Reading tables...");
 	read_all(fd, co_trans, sizeof(co_trans));
 	read_all(fd, eo_trans, sizeof(eo_trans));
 	read_all(fd, ud1_trans, sizeof(ud1_trans));
 
 	read_all(fd, p1_prune, sizeof(p1_prune));
 	read_all(fd, p2_prune, sizeof(p2_prune));
+	verbose_printf("done\n");
 
 	if (close(fd) < 0) {
 		printf("failed to close table file\n");
 }
 int main(int argc, char **argv)
 {
+	char buf[128];
+	int c, prune_depth;
 	struct sigaction s = { .sa_handler = signal_handler };
 
-	char buf[128];
-	int i, oold_len, prune_depth;
-	int total_solves = 0;
-	int total_moves = 0;
-
-	while ((i = getopt(argc, argv, "1ad:gil:m:n:or:s:t:v")) != -1) {
-		switch (i) {
-			case '1': one_sol = 1;            break;
-			case 'a': all_sol = 1;            break;
-			case 'd': max_p1d = atoi(optarg); break;
-			case 'g': gen_tab = 1;            break;
-			case 'i': interval= 1;            break;
-			case 'l': target  = atoi(optarg); break;
-			case 'm': max_len = atoi(optarg); break;
-			case 'n': num_sol = atoi(optarg); break;
-			case 'o': optimal = 1;            break;
-			case 'r': num_cps = atoi(optarg); break;
-			case 's': end_len = atoi(optarg); break;
-			case 't': timeout = atoi(optarg); break;
-			case 'v': verbose = 1;            break;
+	/* got rid of all the options, will worry about that once the code is clean and fast */
+	while ((c = getopt(argc, argv, "1v")) != -1) {
+		switch (c) {
+			case '1': one_sol = 1; break;
+			case 'v': verbose = 1; break;
 			default : printf("bad argument\n"); exit(EXIT_FAILURE);
 		}
 	}
 
-	if (gen_tab || access(TABLES_PATH, R_OK) < 0) {
-		if (verbose) printf("Initializing tables\n");
+	if (access(TABLES_PATH, R_OK) < 0) {
 		init_trans_tables();
 		init_prune_tables();
-		if (gen_tab) {
-			write_tables();
-			return 0;
-		}
+		write_tables();
 	} else {
 		read_tables();
 	}
 
-	if (timeout || num_cps) {
-		//if (sigaction(SIGVTALRM, &s, NULL) < 0) {
-		if (sigaction(SIGALRM, &s, NULL) < 0) {
-			printf("sigaction failed\n");
-			exit(EXIT_FAILURE);
-		}
-
-		if (num_cps) timeout  = 1000000 / num_cps;
-		else         timeout *= 1000;
-
-		iv.it_value = (struct timeval){ timeout / 1000000, timeout % 1000000 };
-		if (num_cps) iv.it_interval = (struct timeval){ timeout / 1000000, timeout % 1000000 };
-		else         iv.it_interval = (struct timeval){                 0,                 0 };
-	}
 	if (sigaction(SIGTSTP, &s, NULL) < 0) {
 		printf("sigaction failed\n");
 		exit(EXIT_FAILURE);
 	}
 
-	if (num_cps)
-		setitimer(ITIMER_REAL, &iv, NULL);
-
 	while (fgets(buf, sizeof(buf), stdin)) {
+		verbose_printf("----------\n");
 		set_cube(buf);
-		if (verbose) puts(get_cube(buf, sizeof(buf)));
+		verbose_printf("Cube: %s\n\n", get_cube(buf, sizeof(buf)));
 
 		memset(sol, -1, sizeof(sol));
-		len = max_len ? max_len : 30;
-		if (!all_sol) len++;
-		num = 0;
-		timeout = 0;
+		len = 30;
 		sigtstp = 0;
 		copy_cube(0, co_, eo_, cp_, ep_);
 
-		if (!num_cps && (iv.it_value.tv_sec || iv.it_value.tv_usec)) {
-			if (target) {
-				if (setitimer(ITIMER_VIRTUAL, &iv, NULL) < 0)
-					printf("setitimer failed\n");
-			} else {
-				if (setitimer(ITIMER_REAL, &iv, NULL) < 0)
-					printf("setitimer failed\n");
-			}
-		}
-
 		prune_depth = find_p1_depth(get_co_coord(), get_eo_coord(), get_ud1_coord());
-		for (p1_len = prune_depth; p1_len <= len && (!max_p1d || p1_len <= max_p1d); p1_len++) {
-			if (solve(PHASE1, get_co_coord(), get_eo_coord(), get_ud1_coord(), p1_len, prune_depth, -1))
+		verbose_printf("starting phase 1 search at depth %d\n", prune_depth);
+		for (p1_len = prune_depth; p1_len <= len; p1_len++) {
+			if (phase1(get_co_coord(), get_eo_coord(), get_ud1_coord(), p1_len, prune_depth, -1))
 				break;
-			if (verbose) { printf("finished phase 1 search depth %d\n", p1_len); fflush(stdout); }
+			verbose_printf("finished phase 1 search depth %d\n", p1_len);
 			copy_cube(1, co_, eo_, cp_, ep_);
 		}
-		if (one_sol) print_solution(1);
-		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.