From b82df53eb461506984eb2b6a9b53e445b75e46af Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sun, 26 Dec 2021 00:36:39 +0100 Subject: Better trans-detection system (for e.g. drfin for HTR scramble) --- src/cubetypes.h | 4 +- src/solve.c | 73 ++++++++++++++++--------- src/steps.c | 165 ++++++++++++++------------------------------------------ 3 files changed, 93 insertions(+), 149 deletions(-) (limited to 'src') diff --git a/src/cubetypes.h b/src/cubetypes.h index 1b679aa..b002e8b 100644 --- a/src/cubetypes.h +++ b/src/cubetypes.h @@ -100,7 +100,7 @@ typedef bool (*Validator) (Alg *); typedef void (*Exec) (CommandArgs *); typedef uint64_t (*Indexer) (Cube); typedef CommandArgs * (*ArgParser) (int, char **); -typedef Trans (*TransDetector) (Cube); +typedef int (*TransDetector) (Cube, Trans *); typedef int (*TransFinder) (uint64_t, Trans *); @@ -202,6 +202,7 @@ dfsarg { Step * step; SolveOptions * opts; + Trans t; Cube cube; Cube inverse; int d; @@ -323,6 +324,7 @@ struct threaddatasolve { int thid; + Trans t; Cube cube; Step * step; int depth; diff --git a/src/solve.c b/src/solve.c index 79e421d..5a72bba 100644 --- a/src/solve.c +++ b/src/solve.c @@ -13,8 +13,10 @@ static void dfs_niss(DfsArg *arg); static bool dfs_stop(DfsArg *arg); static void * instance_thread(void *arg); static void invert_branch(DfsArg *arg); -static void multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d); +static void multidfs(Cube c, Trans t, Step *s, SolveOptions *opts, + AlgList *sols, int d); static bool niss_makes_sense(DfsArg *arg); +static bool solvestop(int d, int op, SolveOptions *opts, AlgList *sols); /* Local functions ***********************************************************/ @@ -62,6 +64,7 @@ copy_dfsarg(DfsArg *src, DfsArg *dst) { dst->step = src->step; dst->opts = src->opts; + dst->t = src->t; dst->cube = src->cube; dst->inverse = src->inverse; dst->d = src->d; @@ -146,7 +149,7 @@ dfs_check_solved(DfsArg *arg) append_alg(arg->sols, arg->current_alg); transform_alg( - inverse_trans(arg->step->pre_trans), + inverse_trans(arg->t), arg->sols->last->alg ); if (arg->step->final) @@ -260,6 +263,7 @@ instance_thread(void *arg) darg.step = td->step; darg.opts = td->opts; + darg.t = td->t; darg.cube = c; darg.d = td->depth; darg.niss = node->alg->inv[0]; @@ -304,7 +308,7 @@ invert_branch(DfsArg *arg) } static void -multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d) +multidfs(Cube c, Trans tr, Step *s, SolveOptions *opts, AlgList *sols, int d) { int i; Alg *alg; @@ -324,8 +328,6 @@ multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d) for (i = 0; s->moveset->sorted_moves[i] != NULLMOVE; i++) { alg = new_alg(""); - /* TODO: start on inverse also in case of final step - and ed->sw true */ append_move(alg, s->moveset->sorted_moves[i], false); append_alg(start, alg); if (opts->can_niss) { @@ -338,6 +340,7 @@ multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d) for (i = 0; i < opts->nthreads; i++) { td[i].thid = i; + td[i].t = tr; td[i].cube = c; td[i].step = s; td[i].depth = d; @@ -368,47 +371,69 @@ niss_makes_sense(DfsArg *arg) return arg->current_alg->len == 0 || arg->step->is_done(testcube); } +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, Step *step, SolveOptions *opts) { - int d, op; + bool ready; + int i, d, op, nt; AlgList *sols; Cube c; + Trans tt[NTRANS]; prepare_step(step, opts); - if (step->detect != NULL) - step->pre_trans = step->detect(cube); - c = apply_trans(step->pre_trans, cube); + if (step->detect != NULL) { + nt = step->detect(cube, tt); + } else { + tt[0] = step->pre_trans; + ready = step->ready == NULL || + step->ready(apply_trans(tt[0], cube)); + nt = ready ? 1 : 0; + } sols = new_alglist(); - if (step->ready != NULL && !step->ready(c)) { + if (nt == 0) { fprintf(stderr, "Cube not ready for solving step: "); fprintf(stderr, "%s\n", step->ready_msg); return sols; } - if (opts->min_moves == 0 && step->is_done(cube)) { - append_alg(sols, new_alg("")); - return sols; + if (opts->min_moves == 0) { + for (i = 0; i < nt; i++) { + c = apply_trans(tt[i], cube); + if (step->is_done(c)) { + append_alg(sols, new_alg("")); + return sols; + } + } } op = -1; - for (d = opts->min_moves; - d <= opts->max_moves && - !(opts->optimal != -1 && op != -1 && opts->optimal + op < d) && - sols->len < opts->max_solutions; - d++) { + for (d = opts->min_moves; !solvestop(d, op, opts, sols); d++) { if (opts->verbose) - fprintf(stderr, - "Found %d solutions, searching depth %d...\n", - sols->len, d); - multidfs(c, step, opts, sols, d); - if (sols->len > 0 && op == -1) - op = d; + fprintf(stderr, "Searching depth %d\n", d); + + for (i = 0; i < nt && !solvestop(d, op, opts, sols); i++) { + c = apply_trans(tt[i], cube); + multidfs(c, tt[i], step, opts, sols, d); + if (sols->len > 0 && op == -1) + op = d; + } } return sols; diff --git a/src/steps.c b/src/steps.c index cfd9a23..98e26b5 100644 --- a/src/steps.c +++ b/src/steps.c @@ -5,30 +5,22 @@ /* Checkers, estimators and validators ***************************************/ static bool check_centers(Cube cube); -static bool check_coany_HTM(Cube cube); static bool check_coud_HTM(Cube cube); -static bool check_coany_URF(Cube cube); static bool check_coud_URF(Cube cube); static bool check_corners_HTM(Cube cube); static bool check_corners_URF(Cube cube); static bool check_cornershtr(Cube cube); -static bool check_eoany(Cube cube); static bool check_eofb(Cube cube); -static bool check_drany(Cube cube); static bool check_drud(Cube cube); static bool check_htr(Cube cube); -static int estimate_eoany_HTM(DfsArg *arg); static int estimate_eofb_HTM(DfsArg *arg); -static int estimate_coany_HTM(DfsArg *arg); static int estimate_coud_HTM(DfsArg *arg); -static int estimate_coany_URF(DfsArg *arg); static int estimate_coud_URF(DfsArg *arg); static int estimate_corners_HTM(DfsArg *arg); static int estimate_cornershtr_HTM(DfsArg *arg); static int estimate_corners_URF(DfsArg *arg); static int estimate_cornershtr_URF(DfsArg *arg); -static int estimate_drany_HTM(DfsArg *arg); static int estimate_drud_HTM(DfsArg *arg); static int estimate_drud_eofb(DfsArg *arg); static int estimate_dr_eofb(DfsArg *arg); @@ -46,8 +38,9 @@ static bool validate_singlecw_ending(Alg *alg); /* Pre-transformation detectors **********************************************/ -static Trans detect_pretrans_eofb(Cube cube); -static Trans detect_pretrans_drud(Cube cube); +static int detect_pretrans_eofb(Cube cube, Trans *ret); +static int detect_pretrans_drud(Cube cube, Trans *ret); +static int detect_pretrans_void_3axis(Cube cube, Trans *ret); /* Messages for when cube is not ready ***************************************/ @@ -206,14 +199,14 @@ eoany_HTM = { .name = "EO on any axis", .final = false, - .is_done = check_eoany, - .estimate = estimate_eoany_HTM, + .is_done = check_eofb, + .estimate = estimate_eofb_HTM, .ready = check_centers, .ready_msg = check_centers_msg, .is_valid = validate_singlecw_ending, .moveset = &moveset_HTM, - .pre_trans = uf, + .detect = detect_pretrans_void_3axis, .tables = {&pd_eofb_HTM}, .ntables = 1, @@ -283,13 +276,13 @@ coany_HTM = { .name = "CO on any axis", .final = false, - .is_done = check_coany_HTM, - .estimate = estimate_coany_HTM, + .is_done = check_coud_HTM, + .estimate = estimate_coud_HTM, .ready = NULL, .is_valid = validate_singlecw_ending, .moveset = &moveset_HTM, - .pre_trans = uf, + .detect = detect_pretrans_void_3axis, .tables = {&pd_coud_HTM}, .ntables = 1, @@ -355,13 +348,13 @@ coany_URF = { .name = "CO any axis (URF moveset)", .final = false, - .is_done = check_coany_URF, - .estimate = estimate_coany_URF, + .is_done = check_coud_URF, + .estimate = estimate_coud_URF, .ready = NULL, .is_valid = validate_singlecw_ending, .moveset = &moveset_URF, - .pre_trans = uf, + .detect = detect_pretrans_void_3axis, .tables = {&pd_coud_HTM}, .ntables = 1, @@ -501,14 +494,14 @@ drany_HTM = { .name = "DR on any axis", .final = false, - .is_done = check_drany, - .estimate = estimate_drany_HTM, + .is_done = check_drud, + .estimate = estimate_drud_HTM, .ready = check_centers, .ready_msg = check_centers_msg, .is_valid = validate_singlecw_ending, .moveset = &moveset_HTM, - .pre_trans = uf, + .detect = detect_pretrans_void_3axis, .tables = {&pd_drud_sym16_HTM}, .ntables = 1, @@ -1002,31 +995,12 @@ check_centers(Cube cube) return cube.cpos == 0; } -static bool -check_coany_HTM(Cube cube) -{ - return cube.cofb == 0 || cube.corl == 0 || cube.coud == 0; -} - static bool check_coud_HTM(Cube cube) { return cube.coud == 0; } -static bool -check_coany_URF(Cube cube) -{ - Cube c2, c3; - - c2 = apply_move(y, apply_move(z, cube)); - c3 = apply_move(y, apply_move(x, cube)); - - return check_coany_HTM(cube) || - check_coany_HTM(c2) || - check_coany_HTM(c3); -} - static bool check_coud_URF(Cube cube) { @@ -1065,26 +1039,12 @@ check_cornershtr(Cube cube) return coord_cornershtr.index(cube) == 0; } -static bool -check_eoany(Cube cube) -{ - return cube.eofb == 0 || cube.eorl == 0 || cube.eoud == 0; -} - static bool check_eofb(Cube cube) { return cube.eofb == 0; } -static bool -check_drany(Cube cube) -{ - return (cube.eofb == 0 && cube.eorl == 0 && cube.coud == 0) || - (cube.eorl == 0 && cube.eoud == 0 && cube.cofb == 0) || - (cube.eoud == 0 && cube.eofb == 0 && cube.corl == 0); -} - static bool check_drud(Cube cube) { @@ -1097,61 +1057,18 @@ check_htr(Cube cube) return check_drud(cube) && coord_htr_drud.index(cube) == 0; } -static int -estimate_eoany_HTM(DfsArg *arg) -{ - int r1, r2, r3; - - r1 = ptableval(&pd_eofb_HTM, arg->cube); - r2 = ptableval(&pd_eofb_HTM, apply_trans(ur, arg->cube)); - r3 = ptableval(&pd_eofb_HTM, apply_trans(fd, arg->cube)); - - return MIN(r1, MIN(r2, r3)); -} - static int estimate_eofb_HTM(DfsArg *arg) { return ptableval(&pd_eofb_HTM, arg->cube); } -static int -estimate_coany_HTM(DfsArg *arg) -{ - int r1, r2, r3; - - r1 = ptableval(&pd_coud_HTM, arg->cube); - r2 = ptableval(&pd_coud_HTM, apply_trans(rf, arg->cube)); - r3 = ptableval(&pd_coud_HTM, apply_trans(fd, arg->cube)); - - return MIN(r1, MIN(r2, r3)); -} - static int estimate_coud_HTM(DfsArg *arg) { return ptableval(&pd_coud_HTM, arg->cube); } -static int -estimate_coany_URF(DfsArg *arg) -{ - int r1, r2, r3; - Cube c; - - c = arg->cube; - - r1 = estimate_coud_URF(arg); - arg->cube = apply_trans(rf, c); - r2 = estimate_coud_URF(arg); - arg->cube = apply_trans(fd, c); - r3 = estimate_coud_URF(arg); - - arg->cube = c; - - return MIN(r1, MIN(r2, r3)); -} - static int estimate_coud_URF(DfsArg *arg) { @@ -1231,18 +1148,6 @@ estimate_corners_URF(DfsArg *arg) return ret; } -static int -estimate_drany_HTM(DfsArg *arg) -{ - int r1, r2, r3; - - r1 = ptableval(&pd_drud_sym16_HTM, arg->cube); - r2 = ptableval(&pd_drud_sym16_HTM, apply_trans(rf, arg->cube)); - r3 = ptableval(&pd_drud_sym16_HTM, apply_trans(fd, arg->cube)); - - return MIN(r1, MIN(r2, r3)); -} - static int estimate_drud_HTM(DfsArg *arg) { @@ -1515,28 +1420,40 @@ validate_singlecw_ending(Alg *alg) /* Pre-transformation detectors **********************************************/ -static Trans -detect_pretrans_eofb(Cube cube) +static int +detect_pretrans_eofb(Cube cube, Trans *ret) { - Trans i; + int i, n; + static Trans tt[3] = {uf, ur, fd}; - for (i = 0; i < NROTATIONS; i++) - if (check_eofb(apply_trans(i, cube))) - return i; + for (i = 0, n = 0; i < 3; i++) + if (check_eofb(apply_trans(tt[i], cube))) + ret[n++] = tt[i]; - return 0; + return n; } -static Trans -detect_pretrans_drud(Cube cube) +static int +detect_pretrans_drud(Cube cube, Trans *ret) { - Trans i; + int i, n; + static Trans tt[3] = {uf, ur, fd}; + + for (i = 0, n = 0; i < 3; i++) + if (check_drud(apply_trans(tt[i], cube))) + ret[n++] = tt[i]; - for (i = 0; i < NROTATIONS; i++) - if (check_drud(apply_trans(i, cube))) - return i; + return n; +} + +static int +detect_pretrans_void_3axis(Cube cube, Trans *ret) +{ + ret[0] = uf; + ret[1] = fr; + ret[2] = rd; - return 0; + return 3; } /* Public functions **********************************************************/ -- cgit v1.3