Commits

Anonymous committed ea74193

first pass at adjusting timeout to meet target length solutions. sloppy, wrong, underdamped, get wild swings.

  • Participants
  • Parent commits 509cb37

Comments (0)

Files changed (4)

 
 solve
 -----
+tune target length
+- keep averages of different length that affect the change base on the order of magnitude of the length
+- i.e. averages of the last 10, 100, 1000 cubes, compare trends, ...
+- think I need to adjust based on rate of change, not (or as well as) distance from target
 add option to only print best solution found (helpful with timeout)
 is a phase 1 length of 0 indicative of an optimal solution?
 recursion elimination so I can save state of solver for a given cube and continue later
 int main(int argc, char **argv)
 {
 	char buf[128];
-	int i, current, solved = 1;
+	int i, current, solved;
 
 	while (fgets(buf, sizeof(buf), stdin)) {
+		solved = 1;
 		printf("input: %s", buf);
 		set_cube(buf);
 		get_cube(buf, sizeof(buf));
  * 0 1 2 3 4 5
  */
 int sol[38];
-int num, len, p1_len = 0, p2_len;
+int num, 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 one_sol = 0;
+int interval= 0;
 int gen_tab = 0;
 int all_sol = 0;
 int max_len = 0;
 	}
 }
 
-void print_solution(void)
+void sprint_solution(char *str)
 {
 	int i;
+	char *p = str, *faces = "UDFBRL", *num = " 2'";
 
-	for (i = 20 - p1_len; i < 20; i++)
-		print_move(sol[i]);
-	for (i = 38 - p2_len; i < 38; i++)
-		print_move(sol[i]);
+	old_len = len;
 
+	for (i = 20 - p1_len; i < 20; i++) {
+		*p++ = faces[sol[i] / 3];
+		*p++ = num  [sol[i] % 3];
+		*p++ = ' ';
+	}
+	for (i = 38 - p2_len; i < 38; i++) {
+		*p++ = faces[sol[i] / 3];
+		*p++ = num  [sol[i] % 3];
+		*p++ = ' ';
+	}
+	*p = '\0';
+}
+
+void print_solution(int old)
+{
+	if (!old) sprint_solution(sol_str);
+	printf("%s", sol_str);
 	if (verbose) printf(" (%d)(%d,%d)", len, p1_len, p2_len);
 	printf("\n");
 	fflush(stdout);
 
 int begin_phase2(int last)
 {
-	int i, success;
+	int i, solved;
 
 	copy_cube(1, co_, eo_, cp_, ep_);
 	for (i = 20 - p1_len; i < 20; i++)
 		do_move(sol[i]);
 
 	for (p2_len = 0; (!all_sol && p2_len + p1_len < len) || (all_sol && p2_len + p1_len <= len); p2_len++)
-		if ((success = solve(PHASE2, get_ep_coord(), get_cp_coord(), get_ud2_coord(), p2_len, last)))
+		if ((solved = solve(PHASE2, get_ep_coord(), get_cp_coord(), get_ud2_coord(), p2_len, last)) || optimal)
 			break;
-	if ((!all_sol && p2_len + p1_len < len) || (all_sol && success && p2_len + p1_len <= len)) {
+	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))
+			setitimer(ITIMER_REAL, &iv, NULL);
 		len = p2_len + p1_len;
-		print_solution();
+		if (one_sol) sprint_solution(sol_str);
+		else         print_solution(0);
 		num++;
-		return (p2_len == 0 || len <= end_len || (num >= num_sol && num_sol));
+		return (sigtstp || timeout || p2_len == 0 || len <= end_len || (num >= num_sol && num_sol));
 	}
 	return 0;
 }
  */
 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, solved;
 
-	if (sigtstp || (timeout && num)) return 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;
 			if (phase == PHASE1) 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 ((solved = solve(phase, e_tmp, c_tmp, ud_tmp, depth - 1, face))) return solved;
 			if (phase == PHASE2 && face > 1) break;
 		}
 	}
 void signal_handler(int signal)
 {
 	switch (signal) {
+		case SIGALRM  :
 		case SIGVTALRM: timeout = 1; break;
 		case SIGTSTP  : sigtstp = 1; break;
 	}
 int main(int argc, char **argv)
 {
 	struct sigaction s = { .sa_handler = signal_handler };
-	struct itimerval iv;
-	struct timeval tv;
 
 	char buf[128];
 	int i;
+	int total_solves = 0;
+	int total_moves = 0;
+	double tiny_avg = 0;
+	double small_avg = 0;
+	double big_avg = 0;
+	double avg_len = 0;
 
-	while ((i = getopt(argc, argv, "1:agm:n:s:t:v")) != -1) {
+	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;
 		read_tables();
 	}
 
-	if (timeout) {
-		if (sigaction(SIGVTALRM, &s, NULL) < 0) {
+	if (target) {
+		one_sol = 1;
+		timeout = 100;
+		avg_len = target;
+		small_avg = target;
+		big_avg = target;
+	}
+	if (timeout || num_cps) {
+		//if (sigaction(SIGVTALRM, &s, NULL) < 0) {
+		if (sigaction(SIGALRM, &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;
+		if (num_cps) timeout  = 1000000 / num_cps;
+		else         timeout *= 1000;
 
-		iv.it_value    = tv;
-		iv.it_interval = (struct timeval){ 0, 0 };
+		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)) {
 		set_cube(buf);
 		if (verbose) puts(get_cube(buf, sizeof(buf)));
 		sigtstp = 0;
 		copy_cube(0, co_, eo_, cp_, ep_);
 
-		if (iv.it_value.tv_sec || iv.it_value.tv_usec)
-			setitimer(ITIMER_VIRTUAL, &iv, NULL);
+		if (!num_cps && (iv.it_value.tv_sec || iv.it_value.tv_usec))
+			setitimer(ITIMER_REAL, &iv, NULL);
 
-		for (p1_len = 0; p1_len <= len; p1_len++) {
+		for (p1_len = 0; p1_len <= len && (!max_p1d || p1_len <= max_p1d); p1_len++) {
 			if (solve(PHASE1, get_eo_coord(), get_co_coord(), get_ud1_coord(), p1_len, -1))
 				break;
 			if (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 (target) {
+			struct timeval dif, res;
+			int us;
 
+			// average of last 100 solves
+			tiny_avg = (tiny_avg * 9 + old_len) / 10.0;
+			small_avg = (small_avg * 99 + old_len) / 100.0;
+			big_avg = (big_avg * 999 + old_len) / 1000.0;
+
+			total_solves++;
+			total_moves += old_len;
+			avg_len = (double) total_moves / (double) total_solves;
+
+			us = big_avg * 1000000 - target * 1000000;
+			us /= 10;
+			if ((big_avg < target && tiny_avg > target) || (big_avg > target && tiny_avg < target)) {
+				us = us / 10;// / 10;
+			} else
+			if ((big_avg < target && tiny_avg < target && tiny_avg > big_avg) ||
+			    (big_avg > target && tiny_avg > target && tiny_avg < big_avg)) {
+				us = 0;
+			}
+			if (us < 0) timersub(&iv.it_value, &((struct timeval){-us / 1000000,-us % 1000000 }), &res);
+			else        timeradd(&iv.it_value, &((struct timeval){ us / 1000000, us % 1000000 }), &res);
+			if (timercmp(&res, &((struct timeval){ 0, 0 }), <=)) res = (struct timeval){ 0, 1 };
+			iv.it_value = res;
+			if (verbose) {
+				printf("total: solves: %d moves: %d\n", total_solves, total_moves);
+				printf("average length: %f target %d\n", avg_len, target);
+				printf("adjustment %d us\n", us);
+			}
+			fprintf(stderr, "now: %d avg: %f sml: %f big: %f dt: % 7.7d timeout: %d.%.6d\n",
+					old_len, avg_len, tiny_avg, big_avg, us, iv.it_value.tv_sec, iv.it_value.tv_usec);
+			fflush(stderr);
+		}
 		if (verbose) printf("----------\n");
 	}
 

File stand_alone/multi

 #!/bin/sh
 #SOLVE="./solve"
 #SOLVE="./2_solve"
-SOLVE="../solve -n 1"
+#SOLVE="../solve -n 1"
 #SOLVE="../solve -n 1 -m 20"
+#SOLVE="../solve -1r6"
+SOLVE="../solve -l 20"
 
 unset pids in out
 trap  die SIGTERM SIGINT
+trap  ""  SIGALRM
 die() { kill $pids; }
 
 num=${1:-$(grep -c processor /proc/cpuinfo)}