From d45e1595ec1cffeab83ac6602b748250b66bea03 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 24 Mar 2025 23:09:26 +0100 Subject: Big cleanup for appendsolution() With this PR the appendsolution routine is extracted from the h48 solver and the new coordinate solver and made generic. This has many advantages: - less repetition (even if the two versions are different enough that *for now* it was not a big deal) - smaller h48/solve.h file, which is already a big beast - easier to test the appendsolution() routine separately --- src/solvers/solutions.h | 213 ++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 208 insertions(+), 5 deletions(-) (limited to 'src/solvers/solutions.h') diff --git a/src/solvers/solutions.h b/src/solvers/solutions.h index 1396210..802075d 100644 --- a/src/solvers/solutions.h +++ b/src/solvers/solutions.h @@ -1,14 +1,217 @@ -#define MAXLEN 20 +STATIC void solution_moves_reset(solution_moves_t [static 1]); +STATIC void solution_moves_transform(solution_moves_t [static 1], uint8_t t); +STATIC bool solution_list_init( + solution_list_t [static 1], size_t n, char [n]); +STATIC bool solution_moves_equal( + const solution_moves_t [static 1], const solution_moves_t [static 1]); +STATIC bool solution_moves_is_duplicate(size_t n, const solution_moves_t[n]); +STATIC bool appendchar(solution_list_t [static 1], char); +STATIC int64_t appendsolution(const solution_moves_t [static 1], + const solution_settings_t [static 1], solution_list_t [static 1]); +STATIC bool solutions_done(const solution_list_t [static 1], + const solution_settings_t [static 1], int8_t depth); -STATIC bool appendchar(size_t n, char [n], size_t *, char); +STATIC void +solution_moves_reset(solution_moves_t sol[static 1]) +{ + sol->nmoves = 0; + sol->npremoves = 0; +} + +STATIC void +solution_moves_transform(solution_moves_t moves[static 1], uint8_t t) +{ + uint8_t i; + + for (i = 0; i < moves->nmoves; i++) + moves->moves[i] = transform_move(moves->moves[i], t); + + for (i = 0; i < moves->npremoves; i++) + moves->premoves[i] = transform_move(moves->premoves[i], t); +} STATIC bool -appendchar(size_t n, char s[n], size_t *used, char c) +solution_list_init(solution_list_t sols[static 1], size_t n, char buf[n]) { - if (n <= *used) + if (n == 0) { + LOG("Cannot use solution buffer with size 0\n"); return false; + } + + sols->nsols = 0; + sols->shortest_sol = MAXLEN + 1; + sols->size = n; + sols->used = 0; + sols->buf = buf; - s[(*used)++] = c; + /* Ensure string buffer is NULL-terminated */ + sols->buf[0] = '\0'; return true; } + +STATIC bool +solution_moves_equal( + const solution_moves_t a[static 1], + const solution_moves_t b[static 1] +) +{ + uint8_t i; + + if (a->nmoves != b->nmoves || a->npremoves != b->npremoves) + return false; + + for (i = 0; i < a->nmoves; i++) + if (a->moves[i] != b->moves[i]) + return false; + + for (i = 0; i < a->npremoves; i++) + if (a->premoves[i] != b->premoves[i]) + return false; + + return true; +} + +STATIC bool +solution_moves_is_duplicate(size_t r, const solution_moves_t s[r]) +{ + size_t i; + + for (i = 0; i < r; i++) + if (solution_moves_equal(&s[i], &s[r])) + return true; + + return false; +} + +STATIC bool +appendchar(solution_list_t solutions[static 1], char c) +{ + if (solutions->size <= solutions->used) + return false; + + solutions->buf[solutions->used++] = c; + + return true; +} + +STATIC int64_t +appendsolution( + const solution_moves_t moves[static 1], + const solution_settings_t settings[static 1], + solution_list_t list[static 1] +) +{ + int64_t r, strl; + int i; + uint8_t t; + solution_moves_t tsol[NTRANS]; + + if (moves->nmoves + moves->npremoves > MAXLEN) + goto appendsolution_error_solution_length; + + for ( + t = 0, r = 0; + t < NTRANS && list->nsols < settings->maxsolutions; + t++ + ) { + if (!(settings->tmask & TM_SINGLE(t))) + continue; + + tsol[r] = *moves; + if (settings->unniss) { + tsol[r].nmoves += moves->npremoves; + tsol[r].npremoves = 0; + for (i = moves->npremoves-1; i >= 0; i--) + tsol[r].moves[tsol[r].nmoves - i - 1] = + inverse_move(moves->premoves[i]); + + /* + This is a bit ugly: we have to sort now and then again + later, because the allowednext check would fail with + improperly sorted parallel moves, but then transforming + could swap the pairs the wrong way around. + TODO: maybe fix this + */ + sortparallel_moves(tsol[r].nmoves, tsol[r].moves); + + /* Check if unnissed premoves cancel with normal. */ + if (!allowedmoves(tsol[r].nmoves, tsol[r].moves)) + continue; + } + solution_moves_transform(&tsol[r], t); + sortparallel_moves(tsol[r].nmoves, tsol[r].moves); + sortparallel_moves(tsol[r].npremoves, tsol[r].premoves); + + /* Skip duplicates that may appear after transforming */ + if (solution_moves_is_duplicate(r, tsol)) + continue; + + /* Write moves on normal */ + strl = writemoves(tsol[r].nmoves, tsol[r].moves, + list->size - list->used, list->buf + list->used); + if (strl < 0) + goto appendsolution_error_buffer; + list->used += (size_t)(strl-1); + + /* Write moves on inverse with NISS notation */ + if (tsol[r].npremoves > 0) { + if (!appendchar(list, ' ')) + goto appendsolution_error_buffer; + if (!appendchar(list, '(')) + goto appendsolution_error_buffer; + + strl = writemoves(tsol[r].npremoves, tsol[r].premoves, + list->size - list->used, list->buf + list->used); + if (strl < 0) + goto appendsolution_error_buffer; + list->used += (size_t)(strl-1); + + if (!appendchar(list, ')')) + goto appendsolution_error_buffer; + } + + if (!appendchar(list, '\n')) + goto appendsolution_error_buffer; + + ++list->nsols; + list->shortest_sol = MIN( + list->shortest_sol, tsol[r].nmoves + tsol[r].npremoves); + r++; + } + + list->buf[list->used] = '\0'; + return r; + +appendsolution_error_buffer: + LOG("Could not append solution to buffer: size too small\n"); + list->buf[0] = '\0'; + return NISSY_ERROR_BUFFER_SIZE; + +appendsolution_error_solution_length: + LOG("Error: solution is too long (%" PRIu8 ").\n" + "This is a bug, please report it.\n", + moves->nmoves + moves->npremoves); + list->buf[0] = '\0'; + return NISSY_ERROR_UNKNOWN; +} + +STATIC bool +solutions_done( + const solution_list_t list[static 1], + const solution_settings_t settings[static 1], + 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; +} -- cgit v1.3