From 0ece4b72db22139db51e8f5f37c25f24c84f3e43 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 17 Apr 2025 10:50:57 +0200 Subject: Small rework of optimal vs maxsols I wanted to make the "optimal" and "maxsolutions" options mutually exclusive, but in the end I decided there is value in keeping both (e.g. for specifying a limit to the number of solutions when asking for "all" optimal"). Now optimal cannot be negative anymore, for the same reason of maxsolutions. The interface user (shell, UI) will have to take care of handling this in a way that makes sense for the user. Usually this means setting the maximum number of solutions to UINT_MAX (or a similar very high number) when the user wants "all optimal". --- cpp/examples/solve_h48h3k2.cpp | 2 +- cpp/nissy.cpp | 16 ++++++++++++---- cpp/nissy.h | 4 ++-- python/examples/solve.py | 2 +- python/nissy_module.c | 5 ++--- shell/shell.c | 8 ++++++-- src/nissy.c | 12 +++++------- src/nissy.h | 7 +++---- src/solvers/coord/solve.h | 13 +++++++------ src/solvers/h48/solve.h | 22 ++++++++++++---------- src/solvers/solutions.h | 15 +++------------ src/solvers/solutions_types_macros.h | 2 +- 12 files changed, 55 insertions(+), 53 deletions(-) diff --git a/cpp/examples/solve_h48h3k2.cpp b/cpp/examples/solve_h48h3k2.cpp index 7f06376..f7ba235 100644 --- a/cpp/examples/solve_h48h3k2.cpp +++ b/cpp/examples/solve_h48h3k2.cpp @@ -68,7 +68,7 @@ int main() { // Solve auto solve_result = h48h3k2.solve(c, nissy::nissflag::NORMAL, - 0, maxmoves, 1, -1, 8); + 0, maxmoves, 1, 20, 8); // Write the result if (!solve_result.err.ok()) { diff --git a/cpp/nissy.cpp b/cpp/nissy.cpp index 944944b..92b10bd 100644 --- a/cpp/nissy.cpp +++ b/cpp/nissy.cpp @@ -21,8 +21,8 @@ extern "C" { long long nissy_gendata(const char *, unsigned long long, char *); long long nissy_checkdata(unsigned long long, const char *); long long nissy_solve(const char *, const char *, unsigned, unsigned, - unsigned, unsigned, int, int, unsigned long long, const char *, - unsigned, char *, long long *); + unsigned, unsigned, unsigned, unsigned, unsigned long long, + const char *, unsigned, char *, long long *); long long nissy_countmoves(const char *); long long nissy_setlogger(void (*)(const char *, void *), void *); } @@ -182,11 +182,19 @@ namespace nissy { solver::solve_result solver::solve(const cube& cube, nissflag niss, unsigned minmoves, - unsigned maxmoves, unsigned maxsols, int optimal, int threads) + unsigned maxmoves, unsigned maxsols, unsigned optimal, + unsigned threads) { + solver::solve_result result; + + if (maxsols == 0) { + result.solutions = {}; + result.err = error::OK; + return result; + } + const size_t len = 3 * (maxmoves+1) * maxsols; std::vector csols(len); - solver::solve_result result; auto err = nissy_solve(cube.to_string().c_str(), name.c_str(), niss.value, minmoves, maxmoves, maxsols, diff --git a/cpp/nissy.h b/cpp/nissy.h index db8ba5f..4b9c1c9 100644 --- a/cpp/nissy.h +++ b/cpp/nissy.h @@ -91,8 +91,8 @@ namespace nissy { error check_data(); void unload_data(); solve_result solve(const cube&, nissflag, unsigned minmoves, - unsigned maxmoves, unsigned maxsols, int optimal, - int threads); + unsigned maxmoves, unsigned maxsols, unsigned optimal, + unsigned threads); static std::variant get(const std::string&); private: diff --git a/python/examples/solve.py b/python/examples/solve.py index b939183..a60c432 100644 --- a/python/examples/solve.py +++ b/python/examples/solve.py @@ -23,7 +23,7 @@ data = bytearray(open("tables/" + solver, "rb").read()) cube = nissy.applymoves(nissy.solved_cube, "U F R2"); # Solve! -solutions = nissy.solve(cube, solver, nissy.nissflag_normal, 0, 9, 3, -1, 4, data) +solutions = nissy.solve(cube, solver, nissy.nissflag_normal, 0, 9, 3, 20, 4, data) # Print the solutions, one per line print("Found ", len(solutions), " solutions:") diff --git a/python/nissy_module.c b/python/nissy_module.c index e92cfd9..46570dc 100644 --- a/python/nissy_module.c +++ b/python/nissy_module.c @@ -324,8 +324,7 @@ PyDoc_STRVAR(solve_doc, " - minmoves: the minimum number of moves to use\n" " - maxmoves: the maximum number of moves to use\n" " - maxsolution: the maximum number of solutions to return\n" -" - optimal: the largest number of moves from the shortest solution" -"(set to -1 to ignore)\n" +" - optimal: the largest number of moves from the shortest solution\n" " - threads: the number of threads to use (0 for default)\n" " - data: a bytearray containing the data for the solver\n" "\n" @@ -343,7 +342,7 @@ solve(PyObject *self, PyObject *args) PyByteArrayObject *data; PyObject *list, *item; - if (!PyArg_ParseTuple(args, "ssIIIIiiY", &cube, &solver, &nissflag, + if (!PyArg_ParseTuple(args, "ssIIIIIIY", &cube, &solver, &nissflag, &minmoves, &maxmoves, &maxsolutions, &optimal, &threads, &data)) return NULL; diff --git a/shell/shell.c b/shell/shell.c index 1ef1a39..2a2720f 100644 --- a/shell/shell.c +++ b/shell/shell.c @@ -1,4 +1,5 @@ #include +#include #include #include #include @@ -482,6 +483,9 @@ solve_exec(args_t *args) return -1; } + if (args->maxsolutions == 0) + args->maxsolutions = args->optimal >= 0 ? UINT_MAX : 1; + buf = malloc(size); read = fread(buf, size, 1, file); fclose(file); @@ -578,8 +582,8 @@ parse_args(int argc, char **argv, args_t *args) .str_nisstype = "", .minmoves = 0, .maxmoves = 20, - .optimal = -1, - .maxsolutions = 1, + .optimal = 20, + .maxsolutions = 0, .threads = 0, }; diff --git a/src/nissy.c b/src/nissy.c index a7f8432..ba43e5d 100644 --- a/src/nissy.c +++ b/src/nissy.c @@ -534,8 +534,8 @@ nissy_solve( unsigned minmoves, unsigned maxmoves, unsigned maxsols, - int optimal, - int threads, + unsigned optimal, + unsigned threads, unsigned long long data_size, const char data[data_size], unsigned sols_size, @@ -546,7 +546,7 @@ nissy_solve( cube_t c; long long parse_ret; uint8_t h, k; - int t, opt; + int t; if (solver == NULL) { LOG("Error: 'solver' argument is NULL\n"); @@ -573,8 +573,6 @@ nissy_solve( return 0; } - opt = optimal < 0 ? MAXLEN : optimal; - t = threads == 0 ? THREADS : threads; if (t < 0) { LOG("solve: 'threads' is negative. Please provide a " @@ -597,10 +595,10 @@ nissy_solve( if (parse_ret != NISSY_OK) return parse_ret; return solve_h48(c, minmoves, maxmoves, maxsols, - opt, t, data_size, data, sols_size, sols, stats); + optimal, t, data_size, data, sols_size, sols, stats); } else if (!strncmp(solver, "coord_", 6)) { return solve_coord_dispatch(c, solver + 6, nissflag, - minmoves, maxmoves, maxsols, opt, t, data_size, data, + minmoves, maxmoves, maxsols, optimal, t, data_size, data, sols_size, sols); } else { LOG("solve: unknown solver '%s'\n", solver); diff --git a/src/nissy.h b/src/nissy.h index b13f417..c23f338 100644 --- a/src/nissy.h +++ b/src/nissy.h @@ -360,8 +360,7 @@ Parameters: minmoves - The minimum number of moves for a solution. maxmoves - The maximum number of moves for a solution. maxsols - The maximum number of solutions. - optimal - If set to a non-negative value, the maximum number of moves - above the optimal solution length. + optimal - The maximum number of moves above the optimal solution length. threads - The number of threads to use. Must be less than or equalt to the value of the compile-time constant THREADS. If set to 0, the default value THREADS will be used. @@ -393,8 +392,8 @@ nissy_solve( unsigned minmoves, unsigned maxmoves, unsigned maxsolutions, - int optimal, - int threads, + unsigned optimal, + unsigned threads, unsigned long long data_size, const char data[data_size], unsigned sols_size, diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h index 464f7bd..b289e3f 100644 --- a/src/solvers/coord/solve.h +++ b/src/solvers/coord/solve.h @@ -13,10 +13,11 @@ typedef struct { } dfsarg_solve_coord_t; 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 *, + uint8_t, uint8_t, uint64_t, uint8_t, uint8_t, 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 n, char [n]); + uint8_t, uint64_t, uint8_t, uint8_t, 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]); @@ -204,8 +205,8 @@ solve_coord_dispatch( uint8_t minmoves, uint8_t maxmoves, uint64_t maxsolutions, - int8_t optimal, - int threads, + uint8_t optimal, + uint8_t threads, uint64_t data_size, const void *data, size_t solutions_size, @@ -242,8 +243,8 @@ solve_coord( uint8_t minmoves, uint8_t maxmoves, uint64_t maxsolutions, - int8_t optimal, - int threads, + uint8_t optimal, + uint8_t threads, uint64_t data_size, const void *data, size_t solutions_size, diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h index f076f11..78b4c97 100644 --- a/src/solvers/h48/solve.h +++ b/src/solvers/h48/solve.h @@ -52,7 +52,7 @@ STATIC int64_t solve_h48_maketasks( solve_h48_task_t [static STARTING_CUBES], int [static 1]); STATIC void *solve_h48_runthread(void *); STATIC int64_t solve_h48_dfs(dfsarg_solve_h48_t [static 1]); -STATIC int64_t solve_h48(cube_t, int8_t, int8_t, uint64_t, int8_t, int8_t, +STATIC int64_t solve_h48(cube_t, uint8_t, uint8_t, uint8_t, uint8_t, uint8_t, uint64_t, const void *, size_t n, char [n], long long [static NISSY_SIZE_SOLVE_STATS]); @@ -67,7 +67,9 @@ solve_h48_stop(dfsarg_solve_h48_t arg[static 1]) n = arg->solution_moves->nmoves + arg->solution_moves->npremoves; target = arg->target_depth - n; if (target <= 0 || - arg->solution_list->nsols == arg->solution_settings->maxsolutions) + arg->solution_list->nsols >= arg->solution_settings->maxsolutions || + n > arg->solution_list->shortest_sol + + arg->solution_settings->optimal) return true; arg->movemask_normal = arg->movemask_inverse = MM_ALLMOVES; @@ -283,8 +285,8 @@ solve_h48_maketasks( if (issolved(maketasks_arg->cube)) { if (maketasks_arg->nmoves > maketasks_arg->maxmoves || maketasks_arg->nmoves < maketasks_arg->minmoves || - solve_arg->solution_list->nsols >= - solve_arg->solution_settings->maxsolutions) + solutions_done(solve_arg->solution_list, + solve_arg->solution_settings, maketasks_arg->nmoves)) return NISSY_OK; solution_moves_reset(&moves); @@ -341,11 +343,11 @@ solve_h48_maketasks( STATIC int64_t solve_h48( cube_t cube, - int8_t minmoves, - int8_t maxmoves, - uint64_t maxsolutions, - int8_t optimal, - int8_t threads, + uint8_t minmoves, + uint8_t maxmoves, + uint8_t maxsolutions, + uint8_t optimal, + uint8_t threads, uint64_t data_size, const void *data, size_t solutions_size, @@ -448,7 +450,7 @@ solve_h48( solve_h48_maketasks(&arg[0], &maketasks_arg, tasks, &ntasks); if (ntasks < 0) goto solve_h48_error_solutions_buffer; - if (sollist.nsols >= maxsolutions) + if (solutions_done(&sollist, &settings, MAX(minmoves, STARTING_MOVES))) goto solve_h48_done; for (i = 0; i < threads; i++) { diff --git a/src/solvers/solutions.h b/src/solvers/solutions.h index e65f299..95c1d1a 100644 --- a/src/solvers/solutions.h +++ b/src/solvers/solutions.h @@ -43,8 +43,6 @@ solution_list_init(solution_list_t sols[static 1], size_t n, char buf[n]) sols->size = n; sols->used = 0; sols->buf = buf; - - /* Ensure string buffer is NULL-terminated */ sols->buf[0] = '\0'; return true; @@ -215,15 +213,8 @@ solutions_done( int8_t depth ) { - if (list->nsols >= settings->maxsolutions) - return true; - - if (depth > settings->maxmoves) - return true; - if (list->nsols > 0 && settings->optimal >= 0 && - depth > list->shortest_sol + settings->optimal) - return true; - - return false; + return depth > settings->maxmoves || + depth > list->shortest_sol + settings->optimal || + list->nsols >= settings->maxsolutions; } diff --git a/src/solvers/solutions_types_macros.h b/src/solvers/solutions_types_macros.h index 06e099b..9b1431f 100644 --- a/src/solvers/solutions_types_macros.h +++ b/src/solvers/solutions_types_macros.h @@ -12,7 +12,7 @@ typedef struct { bool unniss; uint8_t maxmoves; uint64_t maxsolutions; - int8_t optimal; + uint8_t optimal; } solution_settings_t; typedef struct { -- cgit v1.3