From bf44088d4373a9520e860152c56a958332819c4b Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 1 May 2023 16:33:51 +0200 Subject: Split nissy in other repos, see README.md --- old/solve_old.c | 447 -------------------------------------------------------- 1 file changed, 447 deletions(-) delete mode 100644 old/solve_old.c (limited to 'old/solve_old.c') diff --git a/old/solve_old.c b/old/solve_old.c deleted file mode 100644 index 8662c9e..0000000 --- a/old/solve_old.c +++ /dev/null @@ -1,447 +0,0 @@ -#define SOLVE_C - -#include "solve.h" - -/* Local functions ***********************************************************/ - -static void copy_dfsarg(DfsArg *src, DfsArg *dst); -static void dfs(DfsArg *arg); -static void dfs_add_sol(DfsArg *arg); -static void dfs_niss(DfsArg *arg); -static bool dfs_move_checkstop(DfsArg *arg); -static void * instance_thread(void *arg); -static void multidfs(DfsArg *arg); -static bool niss_makes_sense(DfsArg *arg); -static bool solvestop(int d, int op, SolveOptions *opts, AlgList *sols); - -/* Local functions ***********************************************************/ - -static void -copy_dfsarg(DfsArg *src, DfsArg *dst) -{ - int i; - - dst->cube = src->cube; - dst->t = src->t; - dst->s = src->s; - dst->opts = src->opts; - dst->d = src->d; - dst->bound = src->bound; /* In theory not needed */ - dst->niss = src->niss; - dst->sols = src->sols; - dst->sols_mutex = src->sols_mutex; - dst->current_alg = src->current_alg; - - for (i = 0; i < src->s->n_coord; i++) { - dst->ind[i].val = src->ind[i].val; - dst->ind[i].t = src->ind[i].t; - } - - src->s->copy_extra(src, dst); -} - -static void -dfs(DfsArg *arg) -{ - int i; - Move m, l0, l1; - DfsArg newarg; - - if (dfs_move_checkstop(arg)) - return; - - if (arg->bound == 0) { - if (arg->current_alg->len == arg->d) - dfs_add_sol(arg); - return; - } - - for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) { - m = arg->s->moveset->sorted_moves[i]; - if (arg->s->moveset->can_append(arg->current_alg, m, arg->niss) - && compare_last(arg->current_alg, m, arg->niss) >= 0) { - copy_dfsarg(arg, &newarg); - append_move(arg->current_alg, m, newarg.niss); - dfs(&newarg); - remove_last_move(arg->current_alg); - } - } - - if (niss_makes_sense(arg)) - dfs_niss(arg); -} - -static void -dfs_add_sol(DfsArg *arg) -{ - bool valid, accepted, nisscanc; - - valid = arg->s->is_valid==NULL || arg->s->is_valid(arg->current_alg); - accepted = valid || arg->opts->all; - nisscanc = arg->s->final && - arg->s->moveset->cancel_niss(arg->current_alg); - - if (accepted && !nisscanc) { - pthread_mutex_lock(arg->sols_mutex); - - if (arg->sols->len < arg->opts->max_solutions) { - append_alg(arg->sols, arg->current_alg); - transform_alg( - inverse_trans(arg->t), arg->sols->last->alg); - if (arg->opts->verbose) - print_alg(arg->sols->last->alg, false); - } - - pthread_mutex_unlock(arg->sols_mutex); - } -} - -static void -dfs_niss(DfsArg *arg) -{ - DfsArg newarg; - Alg *inv; - Cube *c; - - copy_dfsarg(arg, &newarg); - - /* Invert current alg and scramble */ - newarg.cube = malloc(sizeof(Cube)); - inv = inverse_alg(arg->current_alg); - c = malloc(sizeof(Cube)); - make_solved(newarg.cube); - apply_alg(inv, newarg.cube); - copy_cube(arg->cube, c); - invert_cube(c); - compose(c, newarg.cube); - - /* New indexes */ - compute_ind(newarg.s, newarg.cube, newarg.ind); - - newarg.niss = !(arg->niss); - - dfs(&newarg); - - free_alg(inv); - free(c); - free(newarg.cube); -} - -static bool -dfs_move_checkstop(DfsArg *arg) -{ - int i, goal, nsols; - Move mm; - Trans tt = uf; /* Avoid uninitialized warning */ - - /* Moving and computing bound */ - arg->bound = 0; - goal = arg->d - arg->current_alg->len; - for (i = 0; i < arg->s->n_coord; i++) { - if (arg->last[0] != NULLMOVE) { - mm = transform_move(arg->ind[i].t, arg->last[0]); - arg->ind[i].val = move_coord(arg->s->coord[i], - mm, arg->ind[i].val, &tt); - arg->ind[i].t = transform_trans(tt, arg->ind[i].t); - } - - arg->bound = - MAX(arg->bound, ptableval(arg->s->pd[i], arg->ind[i].val)); - if (arg->opts->can_niss && !arg->niss) - arg->bound = MIN(1, arg->bound); - - if (arg->bound > goal) - return true; - } - - pthread_mutex_lock(arg->sols_mutex); - nsols = arg->sols->len; - pthread_mutex_unlock(arg->sols_mutex); - - return nsols >= arg->opts->max_solutions; -} - -static void * -instance_thread(void *arg) -{ - bool b, inv; - Cube c; - Move m; - ThreadDataSolve *td; - AlgListNode *node; - DfsArg darg; - - td = (ThreadDataSolve *)arg; - - while (1) { - b = false; - - pthread_mutex_lock(td->start_mutex); - if ((node = *(td->node)) == NULL) - b = true; - else - *(td->node) = (*(td->node))->next; - pthread_mutex_unlock(td->start_mutex); - - if (b) - break; - - inv = node->alg->inv[0]; - m = node->alg->move[0]; - - copy_cube(td->arg.cube, &c); - if (inv) - invert_cube(&c); - - copy_dfsarg(&td->arg, &darg); - compute_ind(td->arg.s, &c, darg.ind); - darg.cube = &c; - - darg.niss = inv; - darg.current_alg = new_alg(""); - append_move(darg.current_alg, m, inv); - - dfs(&darg); - - free_alg(darg.current_alg); - } - - return NULL; -} - -static void -multidfs(DfsArg *arg) -{ - int i; - Cube local_cube; - Alg *alg; - AlgList *start; - AlgListNode **node; - pthread_t t[arg->opts->nthreads]; - ThreadDataSolve td[arg->opts->nthreads]; - pthread_mutex_t *start_mutex, *sols_mutex; - - node = malloc(sizeof(AlgListNode *)); - start_mutex = malloc(sizeof(pthread_mutex_t)); - sols_mutex = malloc(sizeof(pthread_mutex_t)); - - start = new_alglist(); - pthread_mutex_init(start_mutex, NULL); - pthread_mutex_init(sols_mutex, NULL); - - for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) { - alg = new_alg(""); - append_move(alg, arg->s->moveset->sorted_moves[i], false); - append_alg(start, alg); - if (arg->opts->can_niss && !arg->s->final) { - alg->inv[0] = true; - append_alg(start, alg); - } - free_alg(alg); - } - *node = start->first; - - copy_cube(arg->cube, &local_cube); - - for (i = 0; i < arg->opts->nthreads; i++) { - copy_dfsarg(arg, &(td[i].arg)); - td[i].arg.cube = &local_cube; - td[i].arg.sols_mutex = sols_mutex; - - td[i].thid = i; - td[i].start = start; - td[i].node = node; - td[i].start_mutex = start_mutex; - - pthread_create(&t[i], NULL, instance_thread, &td[i]); - } - - for (i = 0; i < arg->opts->nthreads; i++) - pthread_join(t[i], NULL); - - free_alglist(start); - free(node); - free(start_mutex); - free(sols_mutex); -} - -static bool -niss_makes_sense(DfsArg *arg) -{ - Move m, mm; - uint64_t u; - int i; - - if (arg->s->final || arg->niss || !arg->opts->can_niss) - return false; - - if (arg->current_alg->len_normal == 0) - return true; - - m = inverse_move(arg->last[0]); - for (i = 0; i < arg->s->n_coord; i++) { - mm = transform_move(arg->ind[i].t, m); - u = move_coord(arg->s->coord[i], mm, 0, NULL); - if (ptableval(arg->s->pd[i], u) > 0) - return true; - } - - return false; -} - -static bool -solvestop(int d, int op, SolveOptions *opts, AlgList *sols) -{ - bool opt_done, max_moves_exceeded, max_sols_exceeded; - - opt_done = opts->optimal != -1 && op != -1 && d > opts->optimal + op; - max_moves_exceeded = d > opts->max_moves; - max_sols_exceeded = sols->len >= opts->max_solutions; - - return opt_done || max_moves_exceeded || max_sols_exceeded; -} - -/* Public functions **********************************************************/ - -AlgList * -solve(Cube *cube, ChoiceStep *cs, SolveOptions *opts) -{ - int i, j, d, op, est; - bool ready[99], one_ready, zerosol; - Movable ind[99][10]; - AlgList *s; - Cube *c[99]; - DfsArg arg[99]; - - prepare_cs(cs, opts); - s = new_alglist(); - - for (i = 0, one_ready = false; cs->step[i] != NULL; i++) { - c[i] = malloc(sizeof(Cube)); - copy_cube(cube, c[i]); - apply_trans(cs->t[i], c[i]); - - arg[i].cube = c[i]; - arg[i].t = cs->t[i]; - arg[i].s = cs->step[i]; - arg[i].opts = opts; - arg[i].sols = s; - - if ((ready[i] = cs->step[i]->ready(c[i]))) { - one_ready = true; - /* Only for local use for 0 moves solutions */ - compute_ind(cs->step[i], c[i], ind[i]); - } - } - if (!one_ready) { - fprintf(stderr, "Cube not ready for solving step: "); - fprintf(stderr, "%s\n", cs->ready_msg); - return s; - } - - /* If the empty moves sequence is a solution for one of the - * alternatives, all longer solutions will be discarded, so we may - * just set its ready[] value to false. If the solution is accepted - * we append it and start searching from d = 1. */ - for (i = 0, zerosol = false; cs->step[i] != NULL; i++) { - if (ready[i]) { - est = 0; - for (j = 0; j < cs->step[i]->n_coord; j++) - est = MAX(est, ptableval(cs->step[i]->pd[j], - ind[i][j].val)); - if (est == 0) { - ready[i] = false; - zerosol = true; - } - } - } - if (zerosol && opts->min_moves == 0) { - append_alg(s, new_alg("")); - opts->min_moves = 1; - if (opts->verbose) - printf("Step is already solved" - "(empty alg is a solution)\n"); - } - - for (d = opts->min_moves, op = -1; !solvestop(d, op, opts, s); d++) { - if (opts->verbose) - fprintf(stderr, "Searching depth %d\n", d); - - for (i=0; cs->step[i]!=NULL && !solvestop(d,op,opts,s); i++) { - if (!ready[i]) - continue; - - arg[i].d = d; - multidfs(&arg[i]); - - if (s->len > 0 && op == -1) - op = d; - } - } - - for (i = 0; cs->step[i] != NULL; i++) - free(c[i]); - - return s; -} - -/* TODO: make more general! */ -Alg * -solve_2phase(Cube *cube, int nthreads) -{ - int bestlen, newb; - Alg *bestalg, *ret; - AlgList *sols1, *sols2; - AlgListNode *i; - Cube c; - SolveOptions opts1, opts2; - - opts1.min_moves = 0; - opts1.max_moves = 13; - opts1.max_solutions = 20; - opts1.nthreads = nthreads; - opts1.optimal = 3; - opts1.can_niss = false; - opts1.verbose = false; - opts1.all = true; - - opts2.min_moves = 0; - opts2.max_moves = 19; - opts2.max_solutions = 1; - opts2.nthreads = nthreads; - opts2.can_niss = false; - opts2.verbose = false; - - /* We skip step1 if it is solved on U/D */ - if (check_drud(cube)) { - sols1 = new_alglist(); - append_alg(sols1, new_alg("")); - } else { - sols1 = solve(cube, &drud_HTM, &opts1); - } - bestalg = new_alg(""); - bestlen = 999; - for (i = sols1->first; i != NULL; i = i->next) { - copy_cube(cube, &c); - apply_alg(i->alg, &c); - sols2 = solve(&c, &dranyfin_DR, &opts2); - - if (sols2->len > 0) { - newb = i->alg->len + sols2->first->alg->len; - if (newb < bestlen) { - bestlen = newb; - copy_alg(i->alg, bestalg); - compose_alg(bestalg, sols2->first->alg); - } - } - - free_alglist(sols2); - } - - free_alglist(sols1); - - ret = cleanup(bestalg); - free_alg(bestalg); - - return ret; -} -- cgit v1.3