Better trans-detection system (for e.g. drfin for HTR scramble)

6 files changed, 97 insertions, 155 deletions

diff --git a/TODO.md b/TODO.md
index 2b41c6f..fc5d9bb 100644
--- 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
index 3379505..ce40157 100755
--- a/nissy
+++ b/nissy
diff --git a/nissy.exe b/nissy.exe
index 845955c..cd521d5 100755
--- a/nissy.exe
+++ b/nissy.exe
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,
@@ -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 **********************************************************/