nissy-nx

A Rubik's cube optimal solver
git clone https://git.tronto.net/nissy-nx
Download | Log | Files | Refs | README | LICENSE

commit 569983380edfb3744192b5a652e2ac038840e53d
parent a125e69c8ce0a2764b1e50b2dad0a4fa9d141ef4
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Tue,  6 Sep 2022 23:25:31 +0200

Removed some code preparing for moving optimal solver away from general coordinate solving.
Kept symcoord for coordinate solving.

Diffstat:
MTODO.md | 36+++++++++++++++++++++---------------
Msrc/commands.c | 20++++++++++----------
Msrc/cubetypes.h | 64++++++++++++++--------------------------------------------------
Msrc/pruning.c | 99+++++++++----------------------------------------------------------------------
Msrc/solve.c | 133+++++++++++++++++++++++++++++++++++++++++++++----------------------------------
Msrc/solve.h | 2+-
Msrc/steps.c | 78++++++++++++++----------------------------------------------------------------
Msrc/steps.h | 148+++++++++++++++++++++++++++++++------------------------------------------------
8 files changed, 204 insertions(+), 376 deletions(-)

diff --git a/TODO.md b/TODO.md @@ -3,20 +3,28 @@ This is a list of things that I would like to add or change at some point. It's more of a personal reminder than anything else. +## After symcoord +### Solving standard coordinates +* add Void * extradata to DfsArg and a custom move function +* add optional custom pre-process for generating special table (nx) +* copy_dfsdata should copy extra too! +* Pruning: remove base value? +### nx.c +* implement nxopt with all tables and all tricks + (maybe compile time variable for maximum memory to use?) +* custom pruning table, copy some code from pruning.h +* generate compressed: hard-code the base value, doable! +* special type of pruning table with fallback and whatnot +* is_valid should also unniss / cleanup the alg +### fst_cube +* slightly different from cube in v2.0.2: each "side" coordinate + is a transformation of the other, not an eorl or similar (changes + the permutation!) +* add fst_index for some coordinates? +* inverse: for edges, just generate ep[12] and convert back +* corners: big table (150Mb if 16bit integers are used) + ## For version 2.1 -### Slow: it is slower than the old nissy 2.0.2 :( -* nxopt's trick (switching to reduce branching) actually saves about 50%! -* Another factor is estimating *while* moving (i.e. do not move all - coordinates if the first one already gives a high value!) -* simplify solve, remove everything that is used only by optimal solvers -* Good compromise: each stepalt offers one of two alternatives: either solve - by simply using pruning tables and moving coordinates, or using a custom - estimator and moving a cube (or fast_cube) and computing coordinates - in the estimator -* is there really no way to use inverse branching trick with current system? -* new file optimal.c with the old solve logic; try first with the simple - cube implementation and the new indexers, if it is still slow change - to fast_cube (intermediate nissy v2.0.2 implementation) ### Changes to Step and Solve * remove cube from dfsarg? (i still need to save the scramble somewhere, but I really only use it in dfs_niss) @@ -24,8 +32,6 @@ It's more of a personal reminder than anything else. * steps.c: checkers (use coordinates), all stepalt and steps (WIP...) * commands gen and freemem * commands.c: twophase, ...? -* Coordinate should have a moveset field? No, at worst there are some garbage - values in mtable, but no risk for errors ### Rotate, not transform, before solving * solve should re-orient first if needed and not just give up if centers are off ### Documentation diff --git a/src/commands.c b/src/commands.c @@ -2,7 +2,7 @@ #include "commands.h" -static bool read_step(CommandArgs *args, char *str); +static bool read_cs(CommandArgs *args, char *str); static bool read_scrtype(CommandArgs *args, char *str); static bool read_scramble(int c, char **v, CommandArgs *args); @@ -95,7 +95,7 @@ solve_parse_args(int c, char **v) a->opts->print_number = false; } else if (!strcmp(v[i], "-c")) { a->opts->count_only = true; - } else if (!read_step(a, v[i])) { + } else if (!read_cs(a, v[i])) { break; } } @@ -218,7 +218,7 @@ solve_exec(CommandArgs *args) make_solved(&c); apply_alg(args->scramble, &c); - sols = solve(&c, args->step, args->opts); + sols = solve(&c, args->cs, args->opts); if (args->opts->count_only) printf("%d\n", sols->len); @@ -345,8 +345,8 @@ steps_exec(CommandArgs *args) { int i; - for (i = 0; steps[i] != NULL; i++) - printf("%-15s %s\n", steps[i]->shortname, steps[i]->name); + for (i = 0; csteps[i] != NULL; i++) + printf("%-15s %s\n", csteps[i]->shortname, csteps[i]->name); } void @@ -503,13 +503,13 @@ read_scrtype(CommandArgs *args, char *str) } static bool -read_step(CommandArgs *args, char *str) +read_cs(CommandArgs *args, char *str) { int i; - for (i = 0; steps[i] != NULL; i++) { - if (!strcmp(steps[i]->shortname, str)) { - args->step = steps[i]; + for (i = 0; csteps[i] != NULL; i++) { + if (!strcmp(csteps[i]->shortname, str)) { + args->cs = csteps[i]; return true; } } @@ -546,7 +546,7 @@ new_args() args->opts = malloc(sizeof(SolveOptions)); /* step and command are static */ - args->step = steps[0]; /* default: first step in list */ + args->cs = csteps[0]; /* default: first step in list */ args->command = NULL; return args; diff --git a/src/cubetypes.h b/src/cubetypes.h @@ -84,7 +84,7 @@ trans typedef struct alg Alg; typedef struct alglist AlgList; typedef struct alglistnode AlgListNode; -typedef struct block Block; +typedef struct choicestep ChoiceStep; typedef struct command Command; typedef struct commandargs CommandArgs; typedef struct coordinate Coordinate; @@ -97,13 +97,14 @@ typedef struct pdgendata PDGenData; typedef struct prunedata PruneData; typedef struct solveoptions SolveOptions; typedef struct step Step; -typedef struct stepalt StepAlt; typedef struct symdata SymData; typedef struct threaddatasolve ThreadDataSolve; typedef struct threaddatagenpt ThreadDataGenpt; typedef struct transgroup TransGroup; typedef bool (*Checker) (Cube *); +typedef bool (*DfsMover) (DfsArg *); +typedef void (*DfsExtraCopier) (void *, void *); typedef bool (*Validator) (Alg *); typedef void (*Exec) (CommandArgs *); typedef CommandArgs * (*ArgParser) (int, char **); @@ -137,11 +138,13 @@ alglistnode }; struct -block +choicestep { - bool edge[12]; - bool corner[8]; - bool center[6]; + char * shortname; + char * name; + Step * step[99]; + Trans t[99]; + char * ready_msg; }; struct @@ -160,7 +163,7 @@ commandargs bool success; Alg * scramble; SolveOptions * opts; - Step * step; + ChoiceStep * cs; Command * command; /* For help */ int n; char scrtype[20]; @@ -210,7 +213,7 @@ dfsarg Cube * cube; Movable ind[MAX_N_COORD]; Trans t; - StepAlt * sa; + Step * s; SolveOptions * opts; int d; int bound; @@ -220,6 +223,7 @@ dfsarg AlgList * sols; pthread_mutex_t * sols_mutex; Alg * current_alg; + void * extra; }; struct @@ -245,7 +249,6 @@ pdgendata { Coordinate * coord; Moveset * moveset; - bool compact; PruneData * pd; }; @@ -256,10 +259,7 @@ prunedata uint64_t n; Coordinate * coord; Moveset * moveset; - bool compact; - int base; uint64_t count[16]; - uint64_t fbmod; }; struct @@ -280,54 +280,18 @@ solveoptions struct step { - char * shortname; - char * name; - StepAlt * alt[99]; - Trans t[99]; - char * ready_msg; -}; - -struct -stepalt -{ Checker ready; bool final; Moveset * moveset; - /* Just a comment, (TODO: remove this): moveset is really a stepalt - * property, because for example we may want to define a "fingertrick - * friendly ZBLL" step, where we allow either <R U D> or <R U F> as - * movesets (or similar) */ int n_coord; Coordinate * coord[MAX_N_COORD]; Trans coord_trans[MAX_N_COORD]; PruneData * pd[MAX_N_COORD]; - bool compact_pd[MAX_N_COORD]; - Coordinate * fallback_coord[MAX_N_COORD]; - PruneData * fallback_pd[MAX_N_COORD]; - uint64_t fbmod[MAX_N_COORD]; - int n_dbtrick; - int dbtrick[MAX_N_COORD][3]; Validator is_valid; + DfsMover custom_move_checkstop; + DfsExtraCopier copy_extra; }; -/* -struct -symdata -{ - char * filename; - bool generated; - Coordinate * coord; - Coordinate * sym_coord; - int ntrans; - Trans * trans; - uint64_t * class; - uint64_t * unsym; - Trans * transtorep; - uint64_t * selfsim; -}; -*/ - - struct threaddatasolve { diff --git a/src/pruning.c b/src/pruning.c @@ -3,13 +3,10 @@ #include "pruning.h" #define ENTRIES_PER_GROUP (2*sizeof(entry_group_t)) -#define ENTRIES_PER_GROUP_COMPACT (4*sizeof(entry_group_t)) static int findchunk(PruneData *pd, int nchunks, uint64_t i); static void genptable_bfs(PruneData *pd, int d, int nt, int nc); -static void genptable_compress(PruneData *pd); static void genptable_fixnasty(PruneData *pd, int d, int nthreads); -static void genptable_setbase(PruneData *pd); static void * instance_bfs(void *arg); static void * instance_fixnasty(void *arg); static void ptable_update(PruneData *pd, uint64_t ind, int m); @@ -32,16 +29,13 @@ findchunk(PruneData *pd, int nchunks, uint64_t i) PruneData * genptable(PDGenData *pdg, int nthreads) { - bool compact; int d, nchunks, i; - uint64_t oldn, sz; + uint64_t oldn; PruneData *pd; for (i = 0; active_pdg[i] != NULL; i++) { pd = active_pdg[i]->pd; - if (pd->coord == pdg->coord && - pd->moveset == pdg->moveset && - pd->compact == pdg->compact) + if (pd->coord == pdg->coord && pd->moveset == pdg->moveset) return pd; } @@ -49,10 +43,7 @@ genptable(PDGenData *pdg, int nthreads) pdg->pd = pd; pd->coord = pdg->coord; pd->moveset = pdg->moveset; - pd->compact = pdg->compact; - - sz = ptablesize(pd) * (pd->compact ? 2 : 1); - pd->ptable = malloc(sz * sizeof(entry_group_t)); + pd->ptable = malloc(ptablesize(pd) * sizeof(entry_group_t)); gen_coord(pd->coord); @@ -70,11 +61,6 @@ genptable(PDGenData *pdg, int nthreads) ); } - - /* For the first steps we proceed the same way for compact and not */ - compact = pd->compact; - pd->compact = false; - nchunks = MIN(ptablesize(pd), 100000); fprintf(stderr, "Generating pt_%s_%s with %d threads\n", pd->coord->name, pd->moveset->name, nthreads); @@ -102,10 +88,6 @@ genptable(PDGenData *pdg, int nthreads) oldn = pd->n; } fprintf(stderr, "Pruning table generated!\n"); - - genptable_setbase(pd); - if (compact) - genptable_compress(pd); if (!write_ptable_file(pd)) fprintf(stderr, "Error writing ptable file\n"); @@ -115,7 +97,6 @@ genptable_done: active_pdg[i] = malloc(sizeof(PDGenData)); active_pdg[i]->coord = pdg->coord; active_pdg[i]->moveset = pdg->moveset; - active_pdg[i]->compact = pdg->compact; active_pdg[i]->pd = pd; return pd; @@ -156,31 +137,6 @@ genptable_bfs(PruneData *pd, int d, int nthreads, int nchunks) } static void -genptable_compress(PruneData *pd) -{ - int val; - uint64_t i, j; - entry_group_t mask, v; - - fprintf(stderr, "Compressing table to 2 bits per entry\n"); - - for (i = 0; i < pd->coord->max; i += ENTRIES_PER_GROUP_COMPACT) { - mask = (entry_group_t)0; - for (j = 0; j < ENTRIES_PER_GROUP_COMPACT; j++) { - if (i+j >= pd->coord->max) - break; - val = ptableval(pd, i+j) - pd->base; - v = (entry_group_t)MIN(3, MAX(0, val)); - mask |= v << (2*j); - } - pd->ptable[i/ENTRIES_PER_GROUP_COMPACT] = mask; - } - - pd->compact = true; - pd->ptable = realloc(pd->ptable, sizeof(entry_group_t)*ptablesize(pd)); -} - -static void genptable_fixnasty(PruneData *pd, int d, int nthreads) { int i; @@ -208,22 +164,6 @@ genptable_fixnasty(PruneData *pd, int d, int nthreads) free(upmtx); } -static void -genptable_setbase(PruneData *pd) -{ - int i; - uint64_t sum, newsum; - - pd->base = 0; - sum = pd->count[0] + pd->count[1] + pd->count[2]; - for (i = 3; i < 16; i++) { - newsum = sum + pd->count[i] - pd->count[i-3]; - if (newsum > sum) - pd->base = i-3; - sum = newsum; - } -} - static void * instance_bfs(void *arg) { @@ -317,7 +257,6 @@ print_ptable(PruneData *pd) uint64_t i; printf("Table %s_%s\n", pd->coord->name, pd->moveset->name); - printf("Base value: %d\n", pd->base); for (i = 0; i < 16; i++) printf("%2" PRIu64 "\t%10" PRIu64 "\n", i, pd->count[i]); } @@ -325,11 +264,7 @@ print_ptable(PruneData *pd) uint64_t ptablesize(PruneData *pd) { - uint64_t e; - - e = pd->compact ? ENTRIES_PER_GROUP_COMPACT : ENTRIES_PER_GROUP; - - return (pd->coord->max + e - 1) / e; + return (pd->coord->max + ENTRIES_PER_GROUP - 1) / ENTRIES_PER_GROUP; } static void @@ -350,23 +285,11 @@ ptable_update(PruneData *pd, uint64_t ind, int n) int ptableval(PruneData *pd, uint64_t ind) { - int sh, ret; - uint64_t e; - entry_group_t m; - - if (pd->compact) { - e = ENTRIES_PER_GROUP_COMPACT; - m = 3; - sh = (ind % e) * 2; - } else { - e = ENTRIES_PER_GROUP; - m = 15; - sh = (ind % e) * 4; - } + int sh; - ret = (pd->ptable[ind/e] & (m << sh)) >> sh; + sh = (ind % ENTRIES_PER_GROUP) * 4; - return pd->compact ? ret + pd->base : ret; + return (pd->ptable[ind/ENTRIES_PER_GROUP] & (15 << sh)) >> sh; } static bool @@ -376,7 +299,7 @@ read_ptable_file(PruneData *pd) FILE *f; char fname[strlen(tabledir)+256]; - int i; + int i, phony; uint64_t r; strcpy(fname, tabledir); @@ -388,7 +311,7 @@ read_ptable_file(PruneData *pd) if ((f = fopen(fname, "rb")) == NULL) return false; - r = fread(&(pd->base), sizeof(int), 1, f); + r = fread(&phony, sizeof(int), 1, f); for (i = 0; i < 16; i++) r += fread(&(pd->count[i]), sizeof(uint64_t), 1, f); r += fread(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f); @@ -405,7 +328,7 @@ write_ptable_file(PruneData *pd) FILE *f; char fname[strlen(tabledir)+256]; - int i; + int i, phony = 0; uint64_t w; strcpy(fname, tabledir); @@ -417,7 +340,7 @@ write_ptable_file(PruneData *pd) if ((f = fopen(fname, "wb")) == NULL) return false; - w = fwrite(&(pd->base), sizeof(int), 1, f); + w = fwrite(&phony, sizeof(int), 1, f); /* phony replace base */ for (i = 0; i < 16; i++) w += fwrite(&(pd->count[i]), sizeof(uint64_t), 1, f); w += fwrite(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f); diff --git a/src/solve.c b/src/solve.c @@ -4,7 +4,7 @@ /* Local functions ***********************************************************/ -static bool allowed_next(Move move, StepAlt *sa, Move l0, Move l1); +static bool allowed_next(Move move, Step *s, Move l0, Move l1); static bool cancel_niss(DfsArg *arg); static void copy_dfsarg(DfsArg *src, DfsArg *dst); static void dfs(DfsArg *arg); @@ -19,13 +19,13 @@ static bool solvestop(int d, int op, SolveOptions *opts, AlgList *sols); /* Local functions ***********************************************************/ static bool -allowed_next(Move m, StepAlt *sa, Move l0, Move l1) +allowed_next(Move m, Step *s, Move l0, Move l1) { bool allowed, order; uint64_t mbit; mbit = ((uint64_t)1) << m; - allowed = mbit & sa->moveset->mask[l1][l0]; + allowed = mbit & s->moveset->mask[l1][l0]; order = !commute(l0, m) || l0 < m; return allowed && order; @@ -41,7 +41,7 @@ cancel_niss(DfsArg *arg) if (arg->lastinv[0] == NULLMOVE) return false; - ms = arg->sa->moveset; + ms = arg->s->moveset; i1 = inverse_move(arg->lastinv[0]); i2 = inverse_move(arg->lastinv[1]); @@ -63,7 +63,7 @@ copy_dfsarg(DfsArg *src, DfsArg *dst) dst->cube = src->cube; dst->t = src->t; - dst->sa = src->sa; + dst->s = src->s; dst->opts = src->opts; dst->d = src->d; dst->bound = src->bound; /* In theory not needed */ @@ -77,10 +77,14 @@ copy_dfsarg(DfsArg *src, DfsArg *dst) dst->lastinv[i] = src->lastinv[i]; } - for (i = 0; i < src->sa->n_coord; i++) { + 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 @@ -99,9 +103,9 @@ dfs(DfsArg *arg) return; } - for (i = 0; arg->sa->moveset->sorted_moves[i] != NULLMOVE; i++) { - m = arg->sa->moveset->sorted_moves[i]; - if (allowed_next(m, arg->sa, arg->last[0], arg->last[1])) { + for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) { + m = arg->s->moveset->sorted_moves[i]; + if (allowed_next(m, arg->s, arg->last[0], arg->last[1])) { copy_dfsarg(arg, &newarg); newarg.last[1] = arg->last[0]; newarg.last[0] = m; @@ -120,9 +124,9 @@ dfs_add_sol(DfsArg *arg) { bool valid, accepted, nisscanc; - valid = arg->sa->is_valid==NULL || arg->sa->is_valid(arg->current_alg); + valid = arg->s->is_valid==NULL || arg->s->is_valid(arg->current_alg); accepted = valid || arg->opts->all; - nisscanc = arg->sa->final && cancel_niss(arg); + nisscanc = arg->s->final && cancel_niss(arg); if (accepted && !nisscanc) { pthread_mutex_lock(arg->sols_mutex); @@ -159,7 +163,7 @@ dfs_niss(DfsArg *arg) compose(c, newarg.cube); /* New indexes */ - compute_ind(newarg.sa, newarg.cube, newarg.ind); + compute_ind(newarg.s, newarg.cube, newarg.ind); swapmove(&(newarg.last[0]), &(newarg.lastinv[0])); swapmove(&(newarg.last[1]), &(newarg.lastinv[1])); @@ -175,36 +179,35 @@ dfs_niss(DfsArg *arg) static bool dfs_move_checkstop(DfsArg *arg) { - bool b; - int i, goal; + int i, goal, nsols; Move mm; Trans tt = uf; /* Avoid uninitialized warning */ - /* Moving */ - if (arg->last[0] != NULLMOVE) { - for (i = 0; i < arg->sa->n_coord; i++) { + /* 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->sa->coord[i], + 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); } - } - /* Computing bound for coordinates */ - goal = arg->d - arg->current_alg->len; - arg->bound = estimate_stepalt(arg->sa, arg->ind, goal); - if (arg->opts->can_niss && !arg->niss) - arg->bound = MIN(1, arg->bound); + 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) { - b = true; - } else { - pthread_mutex_lock(arg->sols_mutex); - b = arg->sols->len >= arg->opts->max_solutions; - pthread_mutex_unlock(arg->sols_mutex); + if (arg->bound > goal) + return true; } - return b; + pthread_mutex_lock(arg->sols_mutex); + nsols = arg->sols->len; + pthread_mutex_unlock(arg->sols_mutex); + + return nsols >= arg->opts->max_solutions; } static void * @@ -240,7 +243,7 @@ instance_thread(void *arg) invert_cube(&c); copy_dfsarg(&td->arg, &darg); - compute_ind(td->arg.sa, &c, darg.ind); + compute_ind(td->arg.s, &c, darg.ind); darg.cube = &c; darg.niss = inv; @@ -279,11 +282,11 @@ multidfs(DfsArg *arg) pthread_mutex_init(start_mutex, NULL); pthread_mutex_init(sols_mutex, NULL); - for (i = 0; arg->sa->moveset->sorted_moves[i] != NULLMOVE; i++) { + for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) { alg = new_alg(""); - append_move(alg, arg->sa->moveset->sorted_moves[i], false); + append_move(alg, arg->s->moveset->sorted_moves[i], false); append_alg(start, alg); - if (arg->opts->can_niss && !arg->sa->final) { + if (arg->opts->can_niss && !arg->s->final) { alg->inv[0] = true; append_alg(start, alg); } @@ -318,15 +321,25 @@ multidfs(DfsArg *arg) static bool niss_makes_sense(DfsArg *arg) { - Cube testcube; + Move m, mm; + uint64_t u; + int i; - if (arg->sa->final || arg->niss || !arg->opts->can_niss) + if (arg->s->final || arg->niss || !arg->opts->can_niss) return false; - make_solved(&testcube); - apply_move(inverse_move(arg->last[0]), &testcube); - return arg->current_alg->len == 0 || - estimate_stepalt(arg->sa, arg->ind, 0) > 0; + if (arg->last[0] == NULLMOVE) + 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 @@ -344,38 +357,38 @@ solvestop(int d, int op, SolveOptions *opts, AlgList *sols) /* Public functions **********************************************************/ AlgList * -solve(Cube *cube, Step *step, SolveOptions *opts) +solve(Cube *cube, ChoiceStep *cs, SolveOptions *opts) { - int i, d, op; + 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_step(step, opts); + prepare_cs(cs, opts); s = new_alglist(); - for (i = 0, one_ready = false; step->alt[i] != NULL; i++) { + for (i = 0, one_ready = false; cs->step[i] != NULL; i++) { c[i] = malloc(sizeof(Cube)); copy_cube(cube, c[i]); - apply_trans(step->t[i], c[i]); + apply_trans(cs->t[i], c[i]); arg[i].cube = c[i]; - arg[i].t = step->t[i]; - arg[i].sa = step->alt[i]; + arg[i].t = cs->t[i]; + arg[i].s = cs->step[i]; arg[i].opts = opts; arg[i].sols = s; - if ((ready[i] = step->alt[i]->ready(c[i]))) { + if ((ready[i] = cs->step[i]->ready(c[i]))) { one_ready = true; /* Only for local use for 0 moves solutions */ - compute_ind(step->alt[i], c[i], ind[i]); + compute_ind(cs->step[i], c[i], ind[i]); } } if (!one_ready) { fprintf(stderr, "Cube not ready for solving step: "); - fprintf(stderr, "%s\n", step->ready_msg); + fprintf(stderr, "%s\n", cs->ready_msg); return s; } @@ -383,10 +396,16 @@ solve(Cube *cube, Step *step, SolveOptions *opts) * 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; step->alt[i] != NULL; i++) { - if (ready[i] && estimate_stepalt(step->alt[i],ind[i],0) == 0) { - ready[i] = false; - zerosol = true; + 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) { @@ -401,7 +420,7 @@ solve(Cube *cube, Step *step, SolveOptions *opts) if (opts->verbose) fprintf(stderr, "Searching depth %d\n", d); - for (i=0; step->alt[i]!=NULL && !solvestop(d,op,opts,s); i++) { + for (i=0; cs->step[i]!=NULL && !solvestop(d,op,opts,s); i++) { if (!ready[i]) continue; @@ -413,7 +432,7 @@ solve(Cube *cube, Step *step, SolveOptions *opts) } } - for (i = 0; step->alt[i] != NULL; i++) + for (i = 0; cs->step[i] != NULL; i++) free(c[i]); return s; diff --git a/src/solve.h b/src/solve.h @@ -5,7 +5,7 @@ #include "steps.h" #include "trans.h" -AlgList * solve(Cube *cube, Step *step, SolveOptions *opts); +AlgList * solve(Cube *cube, ChoiceStep *cs, SolveOptions *opts); Alg * solve_2phase(Cube *cube, int nthreads); #endif diff --git a/src/steps.c b/src/steps.c @@ -132,90 +132,40 @@ validate_singlecw_ending(Alg *alg) /* Public functions **********************************************************/ void -compute_ind(StepAlt *a, Cube *cube, Movable *ind) +compute_ind(Step *s, Cube *cube, Movable *ind) { int i; Cube mvd; Trans t, tt; - for (i = 0; i < a->n_coord; i++) { - t = a->coord_trans[i]; + for (i = 0; i < s->n_coord; i++) { + t = s->coord_trans[i]; copy_cube(cube, &mvd); apply_trans(t, &mvd); - ind[i].val = index_coord(a->coord[i], &mvd, &tt); + ind[i].val = index_coord(s->coord[i], &mvd, &tt); ind[i].t = transform_trans(tt, t); } } -int -estimate_stepalt(StepAlt *a, Movable *ind, int goal) -{ - int i, ret, est[a->n_coord]; - - for (i = 0; i < a->n_coord; i++) { - est[i] = ptableval(a->pd[i], ind[i].val); - if (est[i] == a->pd[i]->base && a->compact_pd[i]) - est[i] = ptableval(a->fallback_pd[i], - ind[i].val/a->fbmod[i]); - if (ind[i].val != 0 && est[i] == 0) /* est == 0 iff solved */ - est[i] = 1; -/* -TODO: remove this debug code -printf("%d: est=%d | ", i, est[i]); -*/ - - if (est[i] > goal) - return est[i]; - } - - for (i = 0; i < a->n_dbtrick; i++) - if (est[a->dbtrick[i][0]] > 0 && - est[a->dbtrick[i][0]] == est[a->dbtrick[i][1]] && - est[a->dbtrick[i][0]] == est[a->dbtrick[i][2]]) - est[a->dbtrick[i][0]] += 1; - - for (i = 0, ret = -1; i < a->n_coord; i++) - ret = MAX(ret, est[i]); - -/* -TODO: remove this debug code -printf("Final estimate: %d\n", ret); -*/ - - return ret; -} - void -prepare_step(Step *step, SolveOptions *opts) +prepare_cs(ChoiceStep *cs, SolveOptions *opts) { int i, j; PDGenData pdg; - StepAlt *a; + Step *s; - for (i = 0; step->alt[i] != NULL; i++) { - a = step->alt[i]; - init_moveset(a->moveset); - pdg.moveset = a->moveset; - for (j = 0; j < a->n_coord; j++) { - gen_coord(a->coord[j]); + for (i = 0; cs->step[i] != NULL; i++) { + s = cs->step[i]; + init_moveset(s->moveset); + pdg.moveset = s->moveset; + for (j = 0; j < s->n_coord; j++) { + gen_coord(s->coord[j]); - pdg.coord = a->coord[j]; - pdg.compact = a->compact_pd[j]; + pdg.coord = s->coord[j]; pdg.pd = NULL; - a->pd[j] = genptable(&pdg, opts->nthreads); - - if (a->compact_pd[j]) { - gen_coord(a->fallback_coord[j]); - - pdg.coord = a->fallback_coord[j]; - pdg.compact = false; - pdg.pd = NULL; - - a->fallback_pd[j] = - genptable(&pdg, opts->nthreads); - } + s->pd[j] = genptable(&pdg, opts->nthreads); } } } diff --git a/src/steps.h b/src/steps.h @@ -13,9 +13,8 @@ bool check_cornershtr(Cube *cube); bool check_eofb(Cube *cube); bool check_drud(Cube *cube); bool check_htr(Cube *cube); -void compute_ind(StepAlt *a, Cube *cube, Movable *ind); -int estimate_stepalt(StepAlt *a, Movable *ind, int goal); -void prepare_step(Step *step, SolveOptions *opts); +void compute_ind(Step *a, Cube *cube, Movable *ind); +void prepare_cs(ChoiceStep *cs, SolveOptions *opts); bool always_valid(Alg *alg); bool validate_singlecw_ending(Alg *alg); @@ -27,26 +26,25 @@ extern char check_dr_msg[100]; extern char check_htr_msg[100]; extern char check_drany_msg[100]; -extern StepAlt sa_nxopt31_HTM; -extern StepAlt sa_eofb_HTM; -extern StepAlt sa_drud_HTM; -extern StepAlt sa_drfin_drud; - -extern Step optimal_HTM; -extern Step eoany_HTM; -extern Step eofb_HTM; -extern Step eorl_HTM; -extern Step eoud_HTM; -extern Step drany_HTM; -extern Step drud_HTM; -extern Step drrl_HTM; -extern Step drfb_HTM; -extern Step dranyfin_DR; -extern Step drudfin_drud; -extern Step drrlfin_drrl; -extern Step drfbfin_drfb; - -extern Step *steps[]; +extern Step step_eofb_HTM; +extern Step step_drud_HTM; +extern Step step_drfin_drud; + +extern ChoiceStep optimal_HTM; +extern ChoiceStep eoany_HTM; +extern ChoiceStep eofb_HTM; +extern ChoiceStep eorl_HTM; +extern ChoiceStep eoud_HTM; +extern ChoiceStep drany_HTM; +extern ChoiceStep drud_HTM; +extern ChoiceStep drrl_HTM; +extern ChoiceStep drfb_HTM; +extern ChoiceStep dranyfin_DR; +extern ChoiceStep drudfin_drud; +extern ChoiceStep drrlfin_drrl; +extern ChoiceStep drfbfin_drfb; + +extern ChoiceStep *csteps[]; #else @@ -56,83 +54,51 @@ char check_dr_msg[100] = "DR must be solved on given axis"; char check_htr_msg[100] = "HTR must be solved"; char check_drany_msg[100] = "DR must be solved on at least one axis"; -/* Optimal solvers *******************/ -/* TODO: build options for smaller optimal solvers */ - -StepAlt -sa_nxopt31_HTM = { - .ready = check_centers, - .final = true, - .moveset = &moveset_HTM, - .n_coord = 6, - .coord = {&coord_nxopt31, &coord_nxopt31, &coord_nxopt31, - &coord_eposepe, &coord_eposepe, &coord_eposepe}, - /* TODO: use khuge as fallback? */ - .coord_trans = {uf, rd, bl, uf, rd, bl}, - .compact_pd = {true, true, true, false, false, false}, - .fallback_coord = {&coord_drud_sym16, &coord_drud_sym16, - &coord_drud_sym16}, - .fbmod = {BINOM8ON4, BINOM8ON4, BINOM8ON4}, - .n_dbtrick = 1, /* TODO: change to 2 when khuge */ - .dbtrick = {{0, 1, 2}}, - .is_valid = NULL, -}; -Step -optimal_HTM = { - .shortname = "optimal", - .name = "Optimal solve (in HTM)", - .alt = {&sa_nxopt31_HTM, NULL}, - .t = {uf}, - .ready_msg = check_centers_msg, -}; - /* Optimal after EO ******************/ /* TODO: eofin_eo (generic), eofbfin_eofb, eorlfin_eorl, eoudfin_eoud */ /* EO steps **************************/ /* TODO: eoany_HTM (generic), eofb_HTM, eorl_HTM, eoud_HTM */ -StepAlt -sa_eofb_HTM = { +Step +step_eofb_HTM = { .ready = check_centers, .final = false, .moveset = &moveset_HTM, .n_coord = 1, .coord = {&coord_eofb}, .coord_trans = {uf}, - .compact_pd = {false}, - .n_dbtrick = 0, .is_valid = validate_singlecw_ending, }; -Step +ChoiceStep eoany_HTM = { .shortname = "eo", .name = "EO on any axis", - .alt = {&sa_eofb_HTM, &sa_eofb_HTM, &sa_eofb_HTM, NULL}, + .step = {&step_eofb_HTM, &step_eofb_HTM, &step_eofb_HTM, NULL}, .t = {uf, ur, fd}, .ready_msg = check_centers_msg, }; -Step +ChoiceStep eofb_HTM = { .shortname = "eofb", .name = "EO on F/B", - .alt = {&sa_eofb_HTM, NULL}, + .step = {&step_eofb_HTM, NULL}, .t = {uf}, .ready_msg = check_centers_msg, }; -Step +ChoiceStep eorl_HTM = { .shortname = "eorl", .name = "EO on R/L", - .alt = {&sa_eofb_HTM, NULL}, + .step = {&step_eofb_HTM, NULL}, .t = {ur}, .ready_msg = check_centers_msg, }; -Step +ChoiceStep eoud_HTM = { .shortname = "eoud", .name = "EO on U/D", - .alt = {&sa_eofb_HTM, NULL}, + .step = {&step_eofb_HTM, NULL}, .t = {fd}, .ready_msg = check_centers_msg, }; @@ -150,93 +116,90 @@ eoud_HTM = { /* TODO: dr_eofb (generic), dr_eorl (generic), dr_eoud (generic) */ /* TODO: drud_eofb, drrl_eofb, drud_eorl, drfb_eorl, drrl_eoud, drfb_eoud */ -StepAlt -sa_drud_HTM = { +Step +step_drud_HTM = { .ready = check_centers, .final = false, .moveset = &moveset_HTM, .n_coord = 1, .coord = {&coord_drud_sym16}, .coord_trans = {uf}, - .compact_pd = {false}, /* TODO: maybe compactify */ - .n_dbtrick = 0, .is_valid = validate_singlecw_ending, }; -Step +ChoiceStep drany_HTM = { .shortname = "dr", .name = "DR on any axis", - .alt = {&sa_drud_HTM, &sa_drud_HTM, &sa_drud_HTM, NULL}, + .step = {&step_drud_HTM, &step_drud_HTM, &step_drud_HTM, NULL}, .t = {uf, rf, fd}, .ready_msg = check_centers_msg, }; -Step +ChoiceStep drud_HTM = { .shortname = "drud", .name = "DR on U/D", - .alt = {&sa_drud_HTM, NULL}, + .step = {&step_drud_HTM, NULL}, .t = {uf}, .ready_msg = check_centers_msg, }; -Step +ChoiceStep drrl_HTM = { .shortname = "drrl", .name = "DR on R/L", - .alt = {&sa_drud_HTM, NULL}, + .step = {&step_drud_HTM, NULL}, .t = {rf}, .ready_msg = check_centers_msg, }; -Step +ChoiceStep drfb_HTM = { .shortname = "drfb", .name = "DR on F/B", - .alt = {&sa_drud_HTM, NULL}, + .step = {&step_drud_HTM, NULL}, .t = {fd}, .ready_msg = check_centers_msg, }; /* DR finish steps */ -StepAlt -sa_drfin_drud = { +Step +step_drfin_drud = { .ready = check_drud, .final = true, .moveset = &moveset_drud, .n_coord = 1, .coord = {&coord_drudfin_noE_sym16}, /* TODO: maybe no noE */ .coord_trans = {uf}, - .compact_pd = {false}, /* TODO: maybe compactify */ - .n_dbtrick = 0, .is_valid = NULL, }; -Step +ChoiceStep dranyfin_DR = { .shortname = "drfin", .name = "DR finish on any axis without breaking DR", - .alt = {&sa_drfin_drud, &sa_drfin_drud, &sa_drfin_drud, NULL}, + .step = {&step_drfin_drud, &step_drfin_drud, + &step_drfin_drud, NULL}, .t = {uf, rf, fd}, .ready_msg = check_dr_msg, }; -Step +ChoiceStep drudfin_drud = { .shortname = "drudfin", .name = "DR finis on U/D without breaking DR", - .alt = {&sa_drfin_drud, NULL}, + .step = {&step_drfin_drud, NULL}, .t = {uf}, .ready_msg = check_dr_msg, }; -Step +ChoiceStep drrlfin_drrl = { .shortname = "drrlfin", .name = "DR finish on R/L without breaking DR", - .alt = {&sa_drfin_drud, NULL}, + .step = {&step_drfin_drud, NULL}, .t = {rf}, .ready_msg = check_dr_msg, }; -Step +ChoiceStep drfbfin_drfb = { .shortname = "drfbfin", .name = "DR finish on F/B without breaking DR", - .alt = {&sa_drfin_drud, NULL}, + .step = {&step_drfin_drud, NULL}, .t = {fd}, .ready_msg = check_dr_msg, }; @@ -247,13 +210,16 @@ drfbfin_drfb = { /* HTR finish */ /* TODO: htrfin_htr */ -Step *steps[] = { - &optimal_HTM, /* first is default */ +ChoiceStep *csteps[] = { +/* TODO: re-implement optimal + &optimal_HTM, +*/ &eoany_HTM, &eofb_HTM, &eorl_HTM, &eoud_HTM, &drany_HTM, &drud_HTM, &drrl_HTM, &drfb_HTM, &dranyfin_DR, &drudfin_drud, &drrlfin_drrl, &drfbfin_drfb, +NULL /* TODO: &optimal_light_HTM,