From 87a15e960e31365698df7e06cd3e6b851e17c1a5 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sun, 5 Mar 2023 10:13:01 +0100 Subject: I made a mess, but it works. Still need to implement new optimal solver. After that, a big redesign is due. --- old/solve_old.c | 447 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 447 insertions(+) create mode 100644 old/solve_old.c (limited to 'old/solve_old.c') diff --git a/old/solve_old.c b/old/solve_old.c new file mode 100644 index 0000000..8662c9e --- /dev/null +++ b/old/solve_old.c @@ -0,0 +1,447 @@ +#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