commit b82df53eb461506984eb2b6a9b53e445b75e46af
parent ce4d6f93c8d00a56b9356d0c0d8489c28e1459df
Author: Sebastiano Tronto <sebastiano.tronto@gmail.com>
Date: Sun, 26 Dec 2021 00:36:39 +0100
Better trans-detection system (for e.g. drfin for HTR scramble)
Diffstat:
6 files changed, 97 insertions(+), 155 deletions(-)
diff --git a/TODO.md b/TODO.md
@@ -24,8 +24,6 @@ including e.g. solutions that were not shown because -c)
### Improvements to currently implemented commands
* **solve should re-orient first if needed and not just give up if centers are off**
* solve should try up to a small bound without loading the large pruning table
-* **drfin for HTR scrambles should try all 3 axis and pick the best solutions;
- in general every step that automatically detects orientation should do this**
### New features
* cleanup: translate an alg to the standard HTM moveset + reorient at the end
@@ -33,7 +31,7 @@ including e.g. solutions that were not shown because -c)
* configure max ram to be used (via config file and/or command line option)
* transform alg, rufify etc...
* more scramble stuff (scramble FMC with rufify...)
-* **command notation to list available moves**
+* command notation to list available moves
## Distribution
@@ -73,7 +71,7 @@ including e.g. solutions that were not shown because -c)
### Cleanup
* Remove khuge from everywhere
* sort again functions alphabetically in their files
-* **more stuff to load at start (or when suitable command is called) rather
- than when called directly, to avoid nasty problems with threading**
+* more stuff to load at start (or when suitable command is called) rather
+ than when called directly, to avoid nasty problems with threading
* unniss and inverse_alg work differently (one in place, the other makes
- a copy and returns).
+ a copy and returns) changing inverse_alg seems the best option.
diff --git a/nissy b/nissy
Binary files differ.
diff --git a/nissy.exe b/nissy.exe
Binary files differ.
diff --git 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
@@ -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
@@ -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,
@@ -1003,31 +996,12 @@ check_centers(Cube cube)
}
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)
{
Cube c2, c3;
@@ -1066,26 +1040,12 @@ check_cornershtr(Cube cube)
}
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)
{
return cube.eofb == 0 && cube.eorl == 0 && cube.coud == 0;
@@ -1098,61 +1058,18 @@ check_htr(Cube cube)
}
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)
{
/* TODO: I can improve this by checking first the orientation of
@@ -1232,18 +1149,6 @@ estimate_corners_URF(DfsArg *arg)
}
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)
{
return ptableval(&pd_drud_sym16_HTM, arg->cube);
@@ -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 **********************************************************/
