commit 9154476ba6bf400c1eb379f0a3aa6caae2d06d4d
parent cc2dacd43eb7f5ed3a2917612b9a2a9232a61e59
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue, 25 Mar 2025 14:09:14 +0100
Added NISS to coord solver
Diffstat:
9 files changed, 309 insertions(+), 104 deletions(-)
diff --git 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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;
-
- 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;
+ 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;
+
+ 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
@@ -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
@@ -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;
+}
