Added NISS to coord solver

9 files changed, 308 insertions, 103 deletions

diff --git a/shell/shell.c b/shell/shell.c
index 0387856..1b66f19 100644
--- a/shell/shell.c
+++ b/shell/shell.c
@@ -73,7 +73,8 @@ static int64_t countmoves_exec(args_t *);
 static int64_t help_exec(args_t *);
 
 static int parse_args(int, char **, args_t *);
-static bool parse_uint(char *, unsigned *);
+static bool parse_uint(const char *, unsigned *);
+static uint8_t parse_nisstype(const char *);
 
 static bool set_cube(int, char **, args_t *);
 static bool set_cube_perm(int, char **, args_t *);
@@ -111,7 +112,7 @@ struct {
         OPTION(FLAG_MOVES, 1, set_str_moves),
         OPTION(FLAG_TRANS, 1, set_str_trans),
         OPTION(FLAG_SOLVER, 1, set_str_solver),
-        OPTION(FLAG_NISSTYPE, 1, set_str_nisstype), /* TODO: more args ? */
+        OPTION(FLAG_NISSTYPE, 1, set_str_nisstype),
         OPTION(FLAG_MINMOVES, 1, set_minmoves),
         OPTION(FLAG_MAXMOVES, 1, set_maxmoves),
         OPTION(FLAG_OPTIMAL, 1, set_optimal),
@@ -431,12 +432,18 @@ solve_exec(args_t *args)
         int64_t ret, gendata_ret, size;
         size_t read;
 
-        nissflag = NISSY_NISSFLAG_NORMAL; /* TODO: parse str_nisstype */
+        nissflag = parse_nisstype(args->str_nisstype);
+        if (nissflag == UINT8_MAX) {
+                fprintf(stderr, "solve: unknown niss type '%s', use one "
+                    "of the following:\nnormal\ninverse\nlinear\nmixed\nall",
+                    args->str_nisstype);
+                return -1;
+        }
 
         size = nissy_solverinfo(args->str_solver, dataid);
 
         if (size < 0) {
-                fprintf(stderr, "solve: unknown solver %s\n",
+                fprintf(stderr, "solve: unknown solver '%s'\n",
                     args->str_solver);
                 return size;
         }
@@ -622,8 +629,8 @@ parse_args(int argc, char **argv, args_t *args)
         return 0;
 }
 
-bool
-parse_uint(char *argv, unsigned *result)
+static bool
+parse_uint(const char *argv, unsigned *result)
 {
         *result = strtol(argv, NULL, 10);
 
@@ -631,6 +638,27 @@ parse_uint(char *argv, unsigned *result)
         return true;
 }
 
+static uint8_t
+parse_nisstype(const char *arg)
+{
+        if (!strcmp("normal", arg))
+                return NISSY_NISSFLAG_NORMAL;
+
+        if (!strcmp("inverse", arg))
+                return NISSY_NISSFLAG_INVERSE;
+
+        if (!strcmp("linear", arg))
+                return NISSY_NISSFLAG_LINEAR;
+
+        if (!strcmp("mixed", arg))
+                return NISSY_NISSFLAG_MIXED;
+
+        if (!strcmp("all", arg))
+                return NISSY_NISSFLAG_ALL;
+
+        return UINT8_MAX;
+}
+
 static bool
 set_cube(int argc, char **argv, args_t *args)
 {
diff --git a/src/core/moves.h b/src/core/moves.h
index e56d5c8..11ac34e 100644
--- a/src/core/moves.h
+++ b/src/core/moves.h
@@ -15,7 +15,7 @@ STATIC cube_t move(cube_t, uint8_t);
 STATIC cube_t premove(cube_t, uint8_t);
 STATIC uint8_t inverse_move(uint8_t);
 STATIC void sortparallel_moves(size_t n, uint8_t [n]);
-STATIC bool are_lastmoves_singlecw(size_t n, uint8_t [n]);
+STATIC bool are_lastmoves_singlecw(size_t n, const uint8_t [n]);
 
 STATIC cube_t applymoves(cube_t, const char *);
 
@@ -236,7 +236,7 @@ sortparallel_moves(size_t n, uint8_t moves[n])
 }
 
 STATIC bool
-are_lastmoves_singlecw(size_t n, uint8_t moves[n])
+are_lastmoves_singlecw(size_t n, const uint8_t moves[n])
 {
         bool two;
 
diff --git a/src/solvers/coord/common.h b/src/solvers/coord/common.h
index 8553658..4cfc36f 100644
--- a/src/solvers/coord/common.h
+++ b/src/solvers/coord/common.h
@@ -1,13 +1,7 @@
-coord_t *all_coordinates[] = {
-        &coordinate_eo,
-        NULL
-};
-
 STATIC void append_coord_name(const coord_t *, char *);
-STATIC coord_t *parse_coord(size_t n, const char [n]);
-STATIC uint8_t parse_axis(size_t n, const char [n]);
-STATIC void parse_coord_and_axis(size_t n, const char [n], coord_t **, uint8_t *);
-STATIC int64_t dataid_coord(const char *, char [static NISSY_DATAID_SIZE]);
+STATIC bool solution_lastqt_cw(const solution_moves_t [static 1]);
+STATIC bool coord_can_switch(
+    const coord_t [static 1], const void *, size_t n, const uint8_t [n]);
 
 STATIC void
 append_coord_name(const coord_t *coord, char *str)
@@ -21,66 +15,40 @@ append_coord_name(const coord_t *coord, char *str)
         str[j] = '\0';
 }
 
-STATIC coord_t *
-parse_coord(size_t n, const char coord[n])
+STATIC bool
+solution_lastqt_cw(const solution_moves_t s[static 1])
 {
-        int i;
-
-        for (i = 0; all_coordinates[i] != NULL; i++)
-                if (!strncmp(all_coordinates[i]->name, coord, n))
-                        return all_coordinates[i];
-
-        return NULL;
-}
-
-STATIC uint8_t
-parse_axis(size_t n, const char axis[n])
-{
-        if (!strncmp(axis, "UD", n) || !strncmp(axis, "DU", n)) {
-                return AXIS_UD;
-        } else if (!strncmp(axis, "RL", n) || !strncmp(axis, "LR", n)) {
-                return AXIS_RL;
-        } else if (!strncmp(axis, "FB", n) || !strncmp(axis, "BF", n)) {
-                return AXIS_FB;
-        }
-
-        return UINT8_ERROR;
+        return are_lastmoves_singlecw(s->nmoves, s->moves) &&
+            are_lastmoves_singlecw(s->npremoves, s->premoves);
 }
 
-STATIC void
-parse_coord_and_axis(
+STATIC bool
+coord_can_switch(
+        const coord_t coord[static 1],
+        const void *data,
         size_t n,
-        const char str[n],
-        coord_t **coord,
-        uint8_t *axis
+        const uint8_t moves[n]
 )
 {
-        size_t i;
-
-        for (i = 0; i < n; i++)
-                if (str[i] == '_')
-                        break;
-
-        if (coord != NULL)
-                *coord = parse_coord(i, str);
+        /*
+        This function checks that the last move (or two moves, if parallel)
+        have a non-trivial effect on the coordinate of the solved cube. This
+        works in general for all coordinates that have been used so far, but
+        in more general cases that have not been considered yet it may fail.
+        */
 
-        if (axis != NULL)
-                *axis = i == n ? UINT8_ERROR : parse_axis(n-i-1, str+i+1);
-}
-
-STATIC int64_t
-dataid_coord(const char *ca, char dataid[static NISSY_DATAID_SIZE])
-{
-        coord_t *c;
+        uint64_t i;
 
-        parse_coord_and_axis(strlen(ca), ca, &c, NULL);
+        if (n == 0)
+                return true;
 
-        if (c == NULL) {
-                LOG("dataid_coord: cannot parse coordinate from '%s'\n", ca);
-                return NISSY_ERROR_INVALID_SOLVER;
-        }
+        i = coord->coord(move(SOLVED_CUBE, moves[n-1]), data);
+        if (i == 0)
+                return false;
 
-        strcpy(dataid, c->name);
+        if (n == 1 || !parallel(moves[n-1], moves[n-2]))
+                return true;
 
-        return NISSY_OK;
+        i = coord->coord(move(SOLVED_CUBE, moves[n-1]), data);
+        return i != 0;
 }
diff --git a/src/solvers/coord/coord.h b/src/solvers/coord/coord.h
index 6ca68c5..f42739d 100644
--- a/src/solvers/coord/coord.h
+++ b/src/solvers/coord/coord.h
@@ -1,5 +1,7 @@
 #include "types_macros.h"
-#include "eo.h"
 #include "common.h"
+#include "eo.h"
+#include "list.h"
+#include "utils.h"
 #include "gendata.h"
 #include "solve.h"
diff --git a/src/solvers/coord/eo.h b/src/solvers/coord/eo.h
index 46a6f70..ef9b27a 100644
--- a/src/solvers/coord/eo.h
+++ b/src/solvers/coord/eo.h
@@ -15,7 +15,7 @@ STATIC coord_t coordinate_eo = {
                 [AXIS_RL] = TRANS_URr,
                 [AXIS_FB] = TRANS_UFr,
         },
-        .is_admissible = &are_lastmoves_singlecw,
+        .is_admissible = &solution_lastqt_cw,
 };
 
 STATIC uint64_t
diff --git a/src/solvers/coord/list.h b/src/solvers/coord/list.h
new file mode 100644
index 0000000..32c94a4
--- /dev/null
+++ b/src/solvers/coord/list.h
@@ -0,0 +1,4 @@
+coord_t *all_coordinates[] = {
+        &coordinate_eo,
+        NULL
+};
diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h
index c056adc..c3fbd02 100644
--- a/src/solvers/coord/solve.h
+++ b/src/solvers/coord/solve.h
@@ -1,66 +1,191 @@
 typedef struct {
         cube_t cube;
+        cube_t inverse;
         uint8_t target_depth;
         solution_moves_t *solution_moves;
         solution_settings_t *solution_settings;
+        solution_list_t *solution_list;
+        uint8_t nissflag;
+        bool lastisnormal;
         coord_t *coord;
         const void *coord_data;
         const uint8_t *ptable;
-        solution_list_t *solution_list;
 } dfsarg_solve_coord_t;
 
-STATIC int64_t solve_coord(cube_t, coord_t *, uint8_t, uint8_t, uint8_t,
-    uint8_t, uint64_t, int8_t, int, uint64_t, const void *, size_t, char *);
+STATIC int64_t solve_coord(cube_t, coord_t [static 1], uint8_t, uint8_t,
+    uint8_t, uint8_t, uint64_t, int8_t, int, uint64_t, const void *,
+    size_t n, char [n]);
 STATIC int64_t solve_coord_dispatch(cube_t, const char *, uint8_t, uint8_t,
-    uint8_t, uint64_t, int8_t, int, uint64_t, const void *, size_t, char *);
-STATIC int64_t solve_coord_dfs(dfsarg_solve_coord_t *);
+    uint8_t, uint64_t, int8_t, int, uint64_t, const void *, size_t n, char [n]);
+STATIC bool coord_solution_admissible(const dfsarg_solve_coord_t [static 1]);
+STATIC bool solve_coord_dfs_stop(const dfsarg_solve_coord_t [static 1]);
+STATIC bool coord_continue_onnormal(const dfsarg_solve_coord_t [static 1]);
+STATIC bool coord_continue_oninverse(const dfsarg_solve_coord_t [static 1]);
+STATIC int64_t solve_coord_dfs(dfsarg_solve_coord_t [static 1]);
+
+STATIC bool
+coord_solution_admissible(const dfsarg_solve_coord_t arg[static 1])
+{
+        uint8_t n;
+
+        n = arg->solution_moves->nmoves + arg->solution_moves->npremoves;
+        if (arg->target_depth != n)
+                return false;
+
+        return arg->coord->is_admissible == NULL ||
+            arg->coord->is_admissible(arg->solution_moves);
+}
+
+STATIC bool
+solve_coord_dfs_stop(const dfsarg_solve_coord_t arg[static 1])
+{
+        bool hasnissed;
+        uint8_t n, pval;
+        uint64_t coord;
+        const cube_t *c;
+
+        n = arg->solution_moves->nmoves + arg->solution_moves->npremoves;
+        if (n >= arg->target_depth)
+                return true;
+
+        hasnissed = arg->solution_moves->nmoves > 0 &&
+            arg->solution_moves->npremoves > 0;
+        if (!hasnissed && (arg->nissflag & NISSY_NISSFLAG_MIXED))
+                return false;
+
+        c = arg->lastisnormal ? &arg->cube : &arg->inverse;
+
+        coord = arg->coord->coord(*c, arg->coord_data);
+        pval = get_coord_pval(arg->coord, arg->ptable, coord);
+
+        return n + pval > arg->target_depth;
+}
+
+STATIC bool
+coord_continue_onnormal(const dfsarg_solve_coord_t arg[static 1])
+{
+        uint8_t f, nn, ni, th;
+
+        f = arg->nissflag;
+        nn = arg->solution_moves->nmoves;
+        ni = arg->solution_moves->npremoves;
+        th = DIV_ROUND_UP(arg->target_depth, 2);
+
+        if (nn + ni == 0)
+                return f & (NISSY_NISSFLAG_NORMAL | NISSY_NISSFLAG_MIXED);
+
+        if (arg->lastisnormal)
+                return (f & NISSY_NISSFLAG_NORMAL) ||
+                    ((f & NISSY_NISSFLAG_MIXED) && (ni > 0 || nn <= th));
+
+        return (f & NISSY_NISSFLAG_MIXED) && nn == 0 && ni < th &&
+            coord_can_switch(arg->coord, arg->coord_data,
+                ni, arg->solution_moves->premoves);
+}
+
+STATIC bool
+coord_continue_oninverse(const dfsarg_solve_coord_t arg[static 1])
+{
+        uint8_t f, nn, ni, th;
+
+        f = arg->nissflag;
+        nn = arg->solution_moves->nmoves;
+        ni = arg->solution_moves->npremoves;
+        th = DIV_ROUND_UP(arg->target_depth, 2);
+
+        if (nn + ni == 0)
+                return f & (NISSY_NISSFLAG_INVERSE | NISSY_NISSFLAG_MIXED);
+
+        if (!arg->lastisnormal)
+                return (f & NISSY_NISSFLAG_INVERSE) ||
+                    ((f & NISSY_NISSFLAG_MIXED) && (nn > 0 || ni < th));
+
+        return (f & NISSY_NISSFLAG_MIXED) && ni == 0 && nn <= th &&
+            coord_can_switch(arg->coord, arg->coord_data,
+                nn, arg->solution_moves->moves);
+}
 
 STATIC int64_t
-solve_coord_dfs(dfsarg_solve_coord_t *arg)
+solve_coord_dfs(dfsarg_solve_coord_t arg[static 1])
 {
-        uint8_t m, pval;
+        bool lastbackup;
+        uint8_t m, l, nnbackup, nibackup;
         uint32_t mm;
         uint64_t coord;
         int64_t n, ret;
-        cube_t backup_cube;
+        cube_t backup_cube, backup_inverse;
 
         coord = arg->coord->coord(arg->cube, arg->coord_data);
-
         if (coord == 0) {
-                if (arg->solution_moves->nmoves != arg->target_depth ||
-                    (arg->coord->is_admissible != NULL &&
-                        !arg->coord->is_admissible(arg->solution_moves->nmoves,
-                            arg->solution_moves->moves)))
+                if (!coord_solution_admissible(arg))
                         return 0;
                 return appendsolution(arg->solution_moves,
                     arg->solution_settings, arg->solution_list);
         }
 
-        pval = get_coord_pval(arg->coord, arg->ptable, coord);
-        if (arg->solution_moves->nmoves + pval > arg->target_depth)
+        if (solve_coord_dfs_stop(arg))
                 return 0;
 
         backup_cube = arg->cube;
+        backup_inverse = arg->inverse;
+        lastbackup = arg->lastisnormal;
+        nnbackup = arg->solution_moves->nmoves;
+        nibackup = arg->solution_moves->npremoves;
 
         ret = 0;
-        mm = allowednextmove_mask(
-            arg->solution_moves->nmoves, arg->solution_moves->moves);
-        arg->solution_moves->nmoves++;
-        for (m = 0; m < NMOVES; m++) {
-                if (!(mm & (1 << m)))
-                        continue;
+        if (coord_continue_onnormal(arg)) {
+                l = arg->solution_moves->nmoves;
+                mm = allowednextmove_mask(l, arg->solution_moves->moves);
+                arg->solution_moves->nmoves++;
+                arg->lastisnormal = true;
 
-                arg->solution_moves->moves[arg->solution_moves->nmoves-1] = m;
-                arg->cube = move(backup_cube, m);
-                n = solve_coord_dfs(arg);
-                if (n < 0)
-                        return n;
-                ret += n;
+                for (m = 0; m < NMOVES; m++) {
+                        if (!(mm & (UINT32_C(1) << (uint32_t)m)))
+                                continue;
+
+                        arg->solution_moves->moves[l] = m;
+                        arg->cube = move(backup_cube, m);
+                        arg->inverse = premove(backup_inverse, m);
+                        n = solve_coord_dfs(arg);
+                        if (n < 0)
+                                return n;
+                        ret += n;
+                        arg->solution_moves->npremoves = nibackup;
+                }
+
+                arg->solution_moves->nmoves--;
         }
+
+        arg->lastisnormal = lastbackup;
+
+        if (coord_continue_oninverse(arg)) {
+                l = arg->solution_moves->npremoves;
+                mm = allowednextmove_mask(l, arg->solution_moves->premoves);
+                arg->solution_moves->npremoves++;
+                arg->lastisnormal = false;
+                
+                for (m = 0; m < NMOVES; m++) {
+                        if (!(mm & (UINT32_C(1) << (uint32_t)m)))
+                                continue;
+
+                        arg->solution_moves->premoves[l] = m;
+                        arg->inverse = move(backup_inverse, m);
+                        arg->cube = premove(backup_cube, m);
+                        n = solve_coord_dfs(arg);
+                        if (n < 0)
+                                return n;
+                        ret += n;
+                        arg->solution_moves->nmoves = nnbackup;
+                }
+
+                arg->solution_moves->npremoves--;
+        }
+
         arg->cube = backup_cube;
-        arg->solution_moves->nmoves--;
+        arg->inverse = backup_inverse;
+        arg->lastisnormal = lastbackup;
 
-        return 0;
+        return ret;
 }
 
 STATIC int64_t
@@ -76,7 +201,7 @@ solve_coord_dispatch(
         uint64_t data_size,
         const void *data,
         size_t solutions_size,
-        char *sols
+        char sols[solutions_size]
 )
 {
         coord_t *coord;
@@ -103,7 +228,7 @@ solve_coord_dispatch(
 STATIC int64_t
 solve_coord(
         cube_t cube,
-        coord_t *coord,
+        coord_t coord [static 1],
         uint8_t axis,
         uint8_t nissflag,
         uint8_t minmoves,
@@ -114,7 +239,7 @@ solve_coord(
         uint64_t data_size,
         const void *data,
         size_t solutions_size,
-        char *sols
+        char sols[solutions_size]
 )
 {
         int8_t d;
@@ -160,12 +285,22 @@ solve_coord(
 
         arg = (dfsarg_solve_coord_t) {
                 .cube = c,
+                .inverse = inverse(c),
                 .coord = coord,
                 .coord_data = coord_data,
                 .ptable = ptable,
                 .solution_moves = &solution_moves,
                 .solution_settings = &solution_settings,
                 .solution_list = &solution_list,
+                .nissflag = nissflag,
+
+                /*
+                Since no move has been done yet, this field should be
+                neither true nor false; using its value now is logically
+                undefined behavior.
+                TODO: find a more elegant solution
+                */
+                .lastisnormal = true,
         };
 
         if (coord->coord(c, coord_data) == 0) {
diff --git a/src/solvers/coord/types_macros.h b/src/solvers/coord/types_macros.h
index f2d436c..9eaeca0 100644
--- a/src/solvers/coord/types_macros.h
+++ b/src/solvers/coord/types_macros.h
@@ -11,5 +11,5 @@ typedef struct {
         uint32_t moves_mask;
         uint64_t trans_mask;
         uint8_t axistrans[3];
-        bool (*is_admissible)(size_t n, uint8_t [n]);
+        bool (*is_admissible)(const solution_moves_t[static 1]);
 } coord_t;
diff --git a/src/solvers/coord/utils.h b/src/solvers/coord/utils.h
new file mode 100644
index 0000000..ab4aded
--- /dev/null
+++ b/src/solvers/coord/utils.h
@@ -0,0 +1,68 @@
+STATIC coord_t *parse_coord(size_t n, const char [n]);
+STATIC uint8_t parse_axis(size_t n, const char [n]);
+STATIC void parse_coord_and_axis(size_t n, const char [n], coord_t **, uint8_t *);
+STATIC int64_t dataid_coord(const char *, char [static NISSY_DATAID_SIZE]);
+
+STATIC coord_t *
+parse_coord(size_t n, const char coord[n])
+{
+        int i;
+
+        for (i = 0; all_coordinates[i] != NULL; i++)
+                if (!strncmp(all_coordinates[i]->name, coord, n))
+                        return all_coordinates[i];
+
+        return NULL;
+}
+
+STATIC uint8_t
+parse_axis(size_t n, const char axis[n])
+{
+        if (!strncmp(axis, "UD", n) || !strncmp(axis, "DU", n)) {
+                return AXIS_UD;
+        } else if (!strncmp(axis, "RL", n) || !strncmp(axis, "LR", n)) {
+                return AXIS_RL;
+        } else if (!strncmp(axis, "FB", n) || !strncmp(axis, "BF", n)) {
+                return AXIS_FB;
+        }
+
+        return UINT8_ERROR;
+}
+
+STATIC void
+parse_coord_and_axis(
+        size_t n,
+        const char str[n],
+        coord_t **coord,
+        uint8_t *axis
+)
+{
+        size_t i;
+
+        for (i = 0; i < n; i++)
+                if (str[i] == '_')
+                        break;
+
+        if (coord != NULL)
+                *coord = parse_coord(i, str);
+
+        if (axis != NULL)
+                *axis = i == n ? UINT8_ERROR : parse_axis(n-i-1, str+i+1);
+}
+
+STATIC int64_t
+dataid_coord(const char *ca, char dataid[static NISSY_DATAID_SIZE])
+{
+        coord_t *c;
+
+        parse_coord_and_axis(strlen(ca), ca, &c, NULL);
+
+        if (c == NULL) {
+                LOG("dataid_coord: cannot parse coordinate from '%s'\n", ca);
+                return NISSY_ERROR_INVALID_SOLVER;
+        }
+
+        strcpy(dataid, c->name);
+
+        return NISSY_OK;
+}