Commits

committed 15d8fc8 Merge

merge

• Participants
• Parent commits 2774d6d, ea74193
• Branches default

File TODO

` `
` 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`

File check.c

` 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));`

File solve.c

`  * 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 i;`
` 	char *p = str, *faces = "UDFBRL", *num = " 2'";`
` `
`+	old_len = len;`
`+`
` 	for (i = 20 - p1_len; i < 20; i++) {`
` 		*p++ = faces[sol[i] / 3];`
` 		*p++ = num  [sol[i] % 3];`
` `
` void print_solution(int old)`
` {`
`-	int i;`
`-`
` 	if (!old) sprint_solution(sol_str);`
`-	fputs(sol_str, stdout);`
`+	printf("%s", sol_str);`
` 	if (verbose) printf(" (%d)(%d,%d)", len, p1_len, p2_len);`
` 	printf("\n");`
` 	fflush(stdout);`
` 		if ((solved = solve(PHASE2, get_ep_coord(), get_cp_coord(), get_ud2_coord(), p2_len, last)) || optimal)`
` 			break;`
` 	if (solved <= 0)`
`-			return solved;`
`+		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_VIRTUAL, &iv, NULL) < 0)`
` void signal_handler(int signal)`
` {`
` 	switch (signal) {`
`+		case SIGALRM  :`
` 		case SIGVTALRM: timeout = 1; break;`
` 		case SIGTSTP  : sigtstp = 1; break;`
` 	}`
` `
` 	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, "1ad:gim:n:os: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`
`+		if (num_cps) timeout  = 1000000 / num_cps;`
`+		else         timeout *= 1000;`
` `
`-		iv.it_value.tv_sec  = timeout / 1000000;`
`-		iv.it_value.tv_usec = timeout % 1000000;`
`-		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)`
`+		if (!num_cps && (iv.it_value.tv_sec || iv.it_value.tv_usec))`
` 			if (setitimer(ITIMER_VIRTUAL, &iv, NULL) < 0)`
` 				printf("setitimer failed\n");`
` `
` 			if (verbose) { printf("finished phase 1 search depth %d\n", p1_len); fflush(stdout); }`
` 			copy_cube(1, co_, eo_, cp_, ep_);`
` 		}`
`+		if (one_sol) print_solution(1);`
`+		if (target) {`
`+			struct timeval dif, res;`
`+			int us;`
` `
`-		if (one_sol) print_solution(1);`
`-		if (verbose) { printf("----------\n"); fflush(stdout); }`
`+			// 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");`
` 	}`
` `
` 	return 0;`

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`