commit 11e6aeeaf5f08839c6effb8f68710081acf491bf
parent 110e079f81277b40ec76be0b86b074a632496109
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Sun, 9 Mar 2025 07:43:37 +0100
Working (?) version of coordinate solver
Diffstat:
12 files changed, 131 insertions(+), 53 deletions(-)
diff --git a/TODO_COORDINATES b/TODO_COORDINATES
@@ -1,4 +1,16 @@
-- solver (from TODOs in appending solution)
+- coord solver
+ - add new parameter to solve(): options (char *)
+ - fix all usages
+ x tests
+ x shell
+ - tools
+ - python bindings
+ - document what to do when changing interface?
+ - where do I document which solvers take which parameters?
+ now that I am implementing more solvers I need an extra
+ document in doc/
+ - in nissy.c, check for minmoves, maxmoves and nissflag (must be in range)
+ - add a dispatcher in solvers.h?
- test solver for EO
- add NISS (and add tests for NISS EO)
- make solve parallelized
@@ -7,3 +19,4 @@
- make gendata parallelized
- refactor common parts of coord and h48 solvers
+- move parse_h48 to h48 module?
diff --git a/shell/shell.c b/shell/shell.c
@@ -17,6 +17,7 @@
#define FLAG_PERM "-perm"
#define FLAG_COMMAND "-command"
#define FLAG_STR_CUBE "-cubestr"
+#define FLAG_SOLVE_OPTS "-options"
#define FLAG_FORMAT "-format"
#define FLAG_FORMAT_IN "-fin"
#define FLAG_FORMAT_OUT "-fout"
@@ -44,6 +45,7 @@ typedef struct {
char cube_perm[22];
char *str_command;
char *str_cube;
+ char *str_options;
char *str_format;
char *str_format_in;
char *str_format_out;
@@ -79,6 +81,7 @@ static bool set_cube(int, char **, args_t *);
static bool set_cube_perm(int, char **, args_t *);
static bool set_str_command(int, char **, args_t *);
static bool set_str_cube(int, char **, args_t *);
+static bool set_str_options(int, char **, args_t *);
static bool set_str_format(int, char **, args_t *);
static bool set_str_format_in(int, char **, args_t *);
static bool set_str_format_out(int, char **, args_t *);
@@ -105,6 +108,7 @@ struct {
OPTION(FLAG_PERM, 1, set_cube_perm),
OPTION(FLAG_COMMAND, 1, set_str_command),
OPTION(FLAG_STR_CUBE, 1, set_str_cube),
+ OPTION(FLAG_SOLVE_OPTS, 1, set_str_options),
OPTION(FLAG_FORMAT, 1, set_str_format),
OPTION(FLAG_FORMAT_IN, 1, set_str_format_in),
OPTION(FLAG_FORMAT_OUT, 1, set_str_format_out),
@@ -197,6 +201,7 @@ struct {
"solve",
"solve " FLAG_SOLVER " SOLVER"
"[" FLAG_MINMOVES " n] [" FLAG_MAXMOVES " N] "
+ "[" FLAG_SOLVE_OPTS " options] "
FLAG_CUBE " CUBE"
FLAG_THREADS " T",
"Solve the given CUBE using SOLVER, "
@@ -208,6 +213,7 @@ struct {
"solve_scramble",
"solve_scramble " FLAG_SOLVER " SOLVER"
"[" FLAG_MINMOVES " n] [" FLAG_MAXMOVES " N] "
+ "[" FLAG_SOLVE_OPTS " options] "
FLAG_MOVES " MOVES",
"Solve the given SCRAMBLE using SOLVER, "
"using at least n and at most N moves. "
@@ -473,15 +479,15 @@ solve_exec(args_t *args)
fclose(file);
if (read != 1) {
fprintf(stderr, "Error reading data from file: "
- "fread() returned %zu instead of 1 when attempting to"
+ "fread() returned %zu instead of 1 when attempting to "
"read %" PRId64 " bytes from file %s\n", read, size, path);
- return -2;
+ goto solve_exec_error;
}
ret = nissy_solve(
- args->cube, args->str_solver, nissflag, args->minmoves,
- args->maxmoves, args->maxsolutions, args->optimal, args->threads,
- size, buf, SOLUTIONS_BUFFER_SIZE, solutions, stats);
+ args->cube, args->str_solver, args->str_options, nissflag,
+ args->minmoves, args->maxmoves, args->maxsolutions, args->optimal,
+ args->threads, size, buf, SOLUTIONS_BUFFER_SIZE, solutions, stats);
free(buf);
@@ -491,6 +497,10 @@ solve_exec(args_t *args)
printf("%s", solutions);
return 0;
+
+solve_exec_error:
+ free(buf);
+ return -2;
}
static int64_t
@@ -655,6 +665,14 @@ set_str_cube(int argc, char **argv, args_t *args)
}
static bool
+set_str_options(int argc, char **argv, args_t *args)
+{
+ args->str_options = argv[0];
+
+ return true;
+}
+
+static bool
set_str_format(int argc, char **argv, args_t *args)
{
args->str_format = argv[0];
diff --git a/src/nissy.c b/src/nissy.c
@@ -451,14 +451,16 @@ nissy_gendata_unsafe(
return NISSY_ERROR_DATA;
}
- arg.buf_size = data_size;
- arg.buf = data;
if (!strncmp(solver, "h48", 3)) {
+ arg.buf_size = data_size;
+ arg.buf = data;
parse_ret = parse_h48_solver(solver, &arg.h, &arg.k);
arg.maxdepth = 20;
if (parse_ret != NISSY_OK)
return parse_ret;
return gendata_h48(&arg);
+ } else if (!strncmp(solver, "coord_", 6)) {
+ return gendata_coord_dispatch(solver+6, data);
} else {
LOG("gendata: unknown solver %s\n", solver);
return NISSY_ERROR_INVALID_SOLVER;
@@ -501,6 +503,7 @@ long long
nissy_solve(
const char cube[static NISSY_SIZE_B32],
const char *solver,
+ const char *options,
unsigned nissflag,
unsigned minmoves,
unsigned maxmoves,
@@ -536,6 +539,8 @@ nissy_solve(
return NISSY_ERROR_UNSOLVABLE_CUBE;
}
+/* TODO: checks for minmoves, maxmoves, nissflag */
+
if (maxsols == 0) {
LOG("solve: 'maxsols' is 0, returning no solution\n");
return 0;
@@ -562,11 +567,15 @@ nissy_solve(
if (!strncmp(solver, "h48", 3)) {
parse_ret = parse_h48_solver(solver, &h, &k);
- if (parse_ret == NISSY_OK)
- return solve_h48(c, minmoves, maxmoves, maxsols, opt,
- t, data_size, data, sols_size, sols, stats);
- else
+ if (parse_ret != NISSY_OK)
return parse_ret;
+/* TODO give warning if options is not NULL or empty? */
+ return solve_h48(c, minmoves, maxmoves, maxsols,
+ opt, t, data_size, data, sols_size, sols, stats);
+ } else if (!strncmp(solver, "coord_", 6)) {
+ return solve_coord_dispatch(c, solver + 6, options, nissflag,
+ minmoves, maxmoves, maxsols, opt, t, data_size, data,
+ sols_size, sols);
} else {
LOG("solve: unknown solver '%s'\n", solver);
return NISSY_ERROR_INVALID_SOLVER;
diff --git a/src/nissy.h b/src/nissy.h
@@ -257,6 +257,9 @@ Solve the given cube using the given solver and options.
Parameters:
cube - The cube to solver, in B32 format.
solver - The name of the solver.
+ options - Extra options for the solver. Some solver require additional
+ parameters, some do not. For example, a coordinate solver
+ may require an "axis" (UD, FB, RL) as a parameter.
nissflag - The flags for NISS (linear, inverse, mixed, or combinations).
minmoves - The minimum number of moves for a solution.
maxmoves - The maximum number of moves for a solution.
@@ -290,6 +293,7 @@ long long
nissy_solve(
const char cube[static NISSY_SIZE_B32],
const char *solver,
+ const char *options,
unsigned nissflag,
unsigned minmoves,
unsigned maxmoves,
diff --git a/src/solvers/coord/coord_common.h b/src/solvers/coord/common.h
diff --git a/src/solvers/coord/coord.h b/src/solvers/coord/coord.h
@@ -1,5 +1,5 @@
-#include "coord_types_macros.h"
+#include "types_macros.h"
#include "eo.h"
-#include "coord_common.h"
+#include "common.h"
#include "gendata.h"
#include "solve.h"
diff --git a/src/solvers/coord/gendata.h b/src/solvers/coord/gendata.h
@@ -1,26 +1,26 @@
-STATIC size_t gendata_coordinate(const coord_t *, void *);
-STATIC size_t gendata_coordinate_name(const char *, void *);
-STATIC tableinfo_t genptable_coordinate(const coord_t *, const void *, uint8_t *);
+STATIC size_t gendata_coord(const coord_t *, void *);
+STATIC int64_t gendata_coord_dispatch(const char *, void *);
+STATIC tableinfo_t genptable_coord(const coord_t *, const void *, uint8_t *);
STATIC uint8_t get_coord_pval(const coord_t *, const uint8_t *, uint64_t);
STATIC void set_coord_pval(const coord_t *, uint8_t *, uint64_t, uint8_t);
-STATIC size_t
-gendata_coordinate_name(const char *name, void *buf)
+STATIC int64_t
+gendata_coord_dispatch(const char *coordstr, void *buf)
{
coord_t *coord;
- coord = parse_coord(name, strlen(name));
+ coord = parse_coord(coordstr, strlen(coordstr));
+
if (coord == NULL) {
- LOG("Cannot generate data for coordinate '%s': not found\n",
- name);
- return 0;
+ LOG("Could not parse coordinate '%s'\n", coord);
+ return NISSY_ERROR_INVALID_SOLVER;
}
- return gendata_coordinate(coord, buf);
+ return (int64_t)gendata_coord(coord, buf);
}
STATIC size_t
-gendata_coordinate(const coord_t *coord, void *buf)
+gendata_coord(const coord_t *coord, void *buf)
{
uint64_t coord_dsize, tablesize, ninfo;
void *pruningbuf, *coord_data;
@@ -33,7 +33,7 @@ gendata_coordinate(const coord_t *coord, void *buf)
tablesize = DIV_ROUND_UP(coord->max, 2);
if (buf == NULL)
- goto gendata_coordinate_return_size;
+ goto gendata_coord_return_size;
if (ninfo == 2) {
coord_data_info = (tableinfo_t) {
@@ -62,15 +62,15 @@ gendata_coordinate(const coord_t *coord, void *buf)
}
table = ((uint8_t *)pruningbuf) + INFOSIZE;
- pruning_info = genptable_coordinate(coord, coord_data, table);
+ pruning_info = genptable_coord(coord, coord_data, table);
writetableinfo(&pruning_info, INFOSIZE + tablesize, pruningbuf);
-gendata_coordinate_return_size:
+gendata_coord_return_size:
return ninfo * INFOSIZE + coord_dsize + tablesize;
}
STATIC tableinfo_t
-genptable_coordinate(const coord_t *coord, const void *data, uint8_t *table)
+genptable_coord(const coord_t *coord, const void *data, uint8_t *table)
{
uint64_t tablesize, i, j, d, tot;
tableinfo_t info;
diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h
@@ -20,8 +20,9 @@ typedef struct {
STATIC int64_t solve_coord(cube_t, coord_t *, uint8_t, uint8_t, uint8_t,
uint8_t, uint64_t, int, int, uint64_t, const void *, uint64_t, char *);
-STATIC int64_t solve_coord_dispatch(cube_t, const char *, uint8_t, uint8_t,
- uint8_t, uint64_t, int, int, uint64_t, const void *, uint64_t, char *);
+STATIC int64_t solve_coord_dispatch(cube_t, const char *, const char *,
+ uint8_t, uint8_t, uint8_t, uint64_t, int, int, uint64_t, const void *,
+ uint64_t, char *);
STATIC bool solve_coord_appendchar(char *, uint64_t, uint64_t *, char);
STATIC int64_t solve_coord_appendsolution(dfsarg_solve_coord_t *);
STATIC int64_t solve_coord_dfs(dfsarg_solve_coord_t *);
@@ -29,7 +30,9 @@ STATIC int64_t solve_coord_dfs(dfsarg_solve_coord_t *);
STATIC int64_t
solve_coord_appendsolution(dfsarg_solve_coord_t *arg)
{
- uint8_t i, t, tmoves[MAXLEN_COORDSOL];
+ uint8_t i, t, l, tmoves[MAXLEN_COORDSOL];
+ char *m;
+ int64_t strl;
if (*arg->nsols >= arg->maxsolutions ||
arg->nmoves > *arg->shortest_sol + arg->optimal)
@@ -41,9 +44,26 @@ solve_coord_appendsolution(dfsarg_solve_coord_t *arg)
for (i = 0; i < arg->nmoves; i++)
tmoves[i] = transform_move(arg->moves[i], t);
- /* TODO append tmoves[] */
+ l = arg->solutions_size - *arg->solutions_used;
+ m = *arg->solutions + *arg->solutions_used;
+ strl = writemoves(tmoves, arg->nmoves, l, m);
+ if (strl < 0)
+ goto solve_coord_appendsolution_error;
+
+ *arg->solutions_used += MAX(0, strl-1);
+
+ if (!solve_coord_appendchar(
+ *arg->solutions, arg->solutions_size, arg->solutions_used, '\n'))
+ goto solve_coord_appendsolution_error;
+
+ (*arg->nsols)++;
+ *arg->shortest_sol = MIN(*arg->shortest_sol, arg->nmoves);
return 1;
+
+solve_coord_appendsolution_error:
+ LOG("Could not append solution to buffer: size too small\n");
+ return NISSY_ERROR_BUFFER_SIZE;
}
STATIC bool
@@ -61,8 +81,11 @@ solve_coord_appendchar(char *s, uint64_t s_size, uint64_t *s_used, char c)
STATIC int64_t
solve_coord_dfs(dfsarg_solve_coord_t *arg)
{
+ uint8_t m, pval;
+ uint32_t mm;
uint64_t coord;
- uint8_t pval;
+ int64_t n, ret;
+ cube_t backup_cube;
coord = arg->coord->coord(arg->cube, arg->coord_data);
@@ -76,8 +99,23 @@ solve_coord_dfs(dfsarg_solve_coord_t *arg)
if (arg->nmoves + pval > arg->depth)
return 0;
- /* TODO recursive call */
- /* Is allowednextmove available here? */
+ backup_cube = arg->cube;
+
+ ret = 0;
+ mm = allowednextmove_mask(arg->moves, arg->nmoves);
+ arg->nmoves++;
+ for (m = 0; m < 18; m++) {
+ if (!(mm & (1 << m)))
+ continue;
+
+ arg->moves[arg->nmoves-1] = m;
+ arg->cube = move(backup_cube, m);
+ n = solve_coord_dfs(arg);
+ if (n < 0)
+ return n;
+ ret += n;
+ }
+ arg->nmoves--;
return 0;
}
@@ -85,7 +123,8 @@ solve_coord_dfs(dfsarg_solve_coord_t *arg)
STATIC int64_t
solve_coord_dispatch(
cube_t cube,
- const char *coord_axis,
+ const char *coordstr,
+ const char *options,
uint8_t nissflag,
uint8_t minmoves,
uint8_t maxmoves,
@@ -98,23 +137,19 @@ solve_coord_dispatch(
char *sols
)
{
- int i, n;
coord_t *coord;
uint8_t axis;
- n = strlen(coord_axis);
- for (i = 0; coord_axis[i] != ' ' && coord_axis[i] != '\0'; i++) ;
-
- coord = parse_coord(coord_axis, i);
- axis = parse_axis(coord_axis + i + 1, n - i - 1);
+ coord = parse_coord(coordstr, strlen(coordstr));
+ axis = parse_axis(options, strlen(options));
if (coord == NULL) {
- LOG("Could not parse coordinate '%s'\n", coord_axis);
+ LOG("Could not parse coordinate '%s'\n", coordstr);
return NISSY_ERROR_INVALID_SOLVER;
}
if (axis == UINT8_ERROR) {
- LOG("Could not parse axis from '%s'\n", coord_axis);
+ LOG("Could not parse axis from options '%s'\n", options);
return NISSY_ERROR_INVALID_SOLVER;
}
@@ -165,8 +200,8 @@ solve_coord(
nsols = 0;
sols_used = 0;
shortest_sol = MAXLEN_COORDSOL + 1;
- c = transform(cube, t);
t = coord->axistrans[axis];
+ c = transform(cube, t);
arg = (dfsarg_solve_coord_t) {
.cube = c,
diff --git a/src/solvers/coord/coord_types_macros.h b/src/solvers/coord/types_macros.h
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
@@ -145,8 +145,7 @@ solve_h48_appendallsym(dfsarg_solve_h48_t *arg)
goto solve_h48_appendallsym_error;
(*arg->nsols)++;
- *arg->shortest_sol =
- MIN(*arg->shortest_sol, arg->nmoves + arg->npremoves);
+ *arg->shortest_sol = MIN(*arg->shortest_sol, n);
ret++;
}
@@ -291,7 +290,7 @@ solve_h48_dfs(dfsarg_solve_h48_t *arg)
if (popcount_u32(mm_normal) <= popcount_u32(mm_inverse)) {
arg->nmoves++;
for (m = 0; m < 18; m++) {
- if (!(mm_normal & (1 << m)))
+ if (!(mm_normal & (UINT32_C(1) << (uint32_t)m)))
continue;
arg->moves[arg->nmoves-1] = m;
arg->cube = move(backup_cube, m);
@@ -308,7 +307,7 @@ solve_h48_dfs(dfsarg_solve_h48_t *arg)
} else {
arg->npremoves++;
for (m = 0; m < 18; m++) {
- if(!(mm_inverse & (1 << m)))
+ if(!(mm_inverse & (UINT32_C(1) << (uint32_t)m)))
continue;
arg->premoves[arg->npremoves-1] = m;
arg->inverse = move(backup_inverse, m);
diff --git a/test/120_gendata_eo/gendata_eo_tests.c b/test/120_gendata_eo/gendata_eo_tests.c
@@ -17,7 +17,7 @@ Pruning table values (from nissy):
char buf[FULLSIZE];
-size_t gendata_coordinate_name(const char *, void *);
+size_t gendata_coord_dispatch(const char *, void *);
bool readtableinfo(uint64_t, const char *, tableinfo_t *);
void run(void) {
@@ -25,7 +25,7 @@ void run(void) {
size_t result;
tableinfo_t info;
- result = gendata_coordinate_name("EO", buf);
+ result = gendata_coord_dispatch("EO", buf);
if (readtableinfo(FULLSIZE, buf, &info) != NISSY_OK) {
printf("Error reading info from table\n");
return;
diff --git a/test/test.h b/test/test.h
@@ -14,7 +14,7 @@
#include "../src/solvers/h48/coordinate_macros.h"
#include "../src/solvers/h48/map_types_macros.h"
#include "../src/solvers/h48/gendata_types_macros.h"
-#include "../src/solvers/coord/coord_types_macros.h"
+#include "../src/solvers/coord/types_macros.h"
#define STRLENMAX 10000
