From 11e6aeeaf5f08839c6effb8f68710081acf491bf Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sun, 9 Mar 2025 07:43:37 +0100 Subject: Working (?) version of coordinate solver --- TODO_COORDINATES | 15 +++++++- shell/shell.c | 28 +++++++++++--- src/nissy.c | 21 ++++++++--- src/nissy.h | 4 ++ src/solvers/coord/common.h | 46 +++++++++++++++++++++++ src/solvers/coord/coord.h | 4 +- src/solvers/coord/coord_common.h | 46 ----------------------- src/solvers/coord/coord_types_macros.h | 14 ------- src/solvers/coord/gendata.h | 30 +++++++-------- src/solvers/coord/solve.h | 69 +++++++++++++++++++++++++--------- src/solvers/coord/types_macros.h | 14 +++++++ src/solvers/h48/solve.h | 7 ++-- test/120_gendata_eo/gendata_eo_tests.c | 4 +- test/test.h | 2 +- 14 files changed, 191 insertions(+), 113 deletions(-) create mode 100644 src/solvers/coord/common.h delete mode 100644 src/solvers/coord/coord_common.h delete mode 100644 src/solvers/coord/coord_types_macros.h create mode 100644 src/solvers/coord/types_macros.h diff --git a/TODO_COORDINATES b/TODO_COORDINATES index 8d75ed6..6634623 100644 --- 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 index 5a2d283..2853350 100644 --- 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 @@ -654,6 +664,14 @@ set_str_cube(int argc, char **argv, args_t *args) return true; } +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) { diff --git a/src/nissy.c b/src/nissy.c index ffda4b3..ed1d3f4 100644 --- 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 index 6c5a3e6..9c26292 100644 --- 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/common.h b/src/solvers/coord/common.h new file mode 100644 index 0000000..d827665 --- /dev/null +++ b/src/solvers/coord/common.h @@ -0,0 +1,46 @@ +coord_t *all_coordinates[] = { + &coordinate_eo, + NULL +}; + +STATIC void append_coord_name(const coord_t *, char *); +STATIC coord_t *parse_coord(const char *, int); +STATIC uint8_t parse_axis(const char *, int); + +STATIC void +append_coord_name(const coord_t *coord, char *str) +{ + int i, j; + + i = 0; + j = strlen(str); + while (coord->name[i]) str[j++] = coord->name[i++]; + + str[j] = '\0'; +} + +STATIC coord_t * +parse_coord(const char *coord, int 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(const char *axis, int 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; +} diff --git a/src/solvers/coord/coord.h b/src/solvers/coord/coord.h index fc241cb..6ca68c5 100644 --- 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/coord_common.h b/src/solvers/coord/coord_common.h deleted file mode 100644 index d827665..0000000 --- a/src/solvers/coord/coord_common.h +++ /dev/null @@ -1,46 +0,0 @@ -coord_t *all_coordinates[] = { - &coordinate_eo, - NULL -}; - -STATIC void append_coord_name(const coord_t *, char *); -STATIC coord_t *parse_coord(const char *, int); -STATIC uint8_t parse_axis(const char *, int); - -STATIC void -append_coord_name(const coord_t *coord, char *str) -{ - int i, j; - - i = 0; - j = strlen(str); - while (coord->name[i]) str[j++] = coord->name[i++]; - - str[j] = '\0'; -} - -STATIC coord_t * -parse_coord(const char *coord, int 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(const char *axis, int 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; -} diff --git a/src/solvers/coord/coord_types_macros.h b/src/solvers/coord/coord_types_macros.h deleted file mode 100644 index 594f594..0000000 --- a/src/solvers/coord/coord_types_macros.h +++ /dev/null @@ -1,14 +0,0 @@ -#define COORD_INDEX(i) ((i)/2) -#define COORD_SHIFT(i) (UINT8_C(4) * (uint8_t)((i) % 2)) -#define COORD_MASK(i) (UINT8_C(0xF) << COORD_SHIFT(i)) - -typedef struct { - char name[255]; - uint64_t (*coord)(cube_t, const void *); - cube_t (*cube)(uint64_t, const void *); - size_t (*gendata)(void *); - uint64_t max; - uint32_t moves_mask; - uint64_t trans_mask; - uint8_t axistrans[3]; -} coord_t; diff --git a/src/solvers/coord/gendata.h b/src/solvers/coord/gendata.h index 3d385e9..d366466 100644 --- 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 index e954aac..190ac1f 100644 --- 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/types_macros.h b/src/solvers/coord/types_macros.h new file mode 100644 index 0000000..594f594 --- /dev/null +++ b/src/solvers/coord/types_macros.h @@ -0,0 +1,14 @@ +#define COORD_INDEX(i) ((i)/2) +#define COORD_SHIFT(i) (UINT8_C(4) * (uint8_t)((i) % 2)) +#define COORD_MASK(i) (UINT8_C(0xF) << COORD_SHIFT(i)) + +typedef struct { + char name[255]; + uint64_t (*coord)(cube_t, const void *); + cube_t (*cube)(uint64_t, const void *); + size_t (*gendata)(void *); + uint64_t max; + uint32_t moves_mask; + uint64_t trans_mask; + uint8_t axistrans[3]; +} coord_t; diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h index 44f6a89..182beee 100644 --- 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 index 3a6ac07..46a0606 100644 --- 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 index e144527..4b281e0 100644 --- 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 -- cgit v1.3