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/coord/solve.h | 147 ++++++++++++++++------------------------------ 1 file changed, 51 insertions(+), 96 deletions(-) (limited to 'src/solvers/coord') diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h index fa160f8..c056adc 100644 --- a/src/solvers/coord/solve.h +++ b/src/solvers/coord/solve.h @@ -1,70 +1,20 @@ typedef struct { cube_t cube; - uint8_t depth; - uint8_t nmoves; - uint8_t moves[MAXLEN]; + uint8_t target_depth; + solution_moves_t *solution_moves; + solution_settings_t *solution_settings; coord_t *coord; const void *coord_data; const uint8_t *ptable; - uint8_t trans; - int64_t *nsols; - int64_t maxsolutions; - int optimal; - uint8_t *shortest_sol; - size_t solutions_size; - size_t *solutions_used; - char **solutions; + 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, int, int, uint64_t, const void *, size_t, char *); + uint8_t, uint64_t, int8_t, int, uint64_t, const void *, size_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 *, size_t, char *); -STATIC int64_t solve_coord_appendsolution(dfsarg_solve_coord_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 *); -STATIC int64_t -solve_coord_appendsolution(dfsarg_solve_coord_t *arg) -{ - uint8_t i, t, tmoves[MAXLEN]; - int64_t strl; - uint64_t l; - char *m; - - if (*arg->nsols >= arg->maxsolutions || - arg->nmoves > *arg->shortest_sol + arg->optimal || - (arg->coord->is_admissible != NULL && - !arg->coord->is_admissible(arg->nmoves, arg->moves))) - return 0; - - t = inverse_trans(arg->trans); - for (i = 0; i < arg->nmoves; i++) - tmoves[i] = transform_move(arg->moves[i], t); - - sortparallel(arg->nmoves, tmoves); - - l = arg->solutions_size - *arg->solutions_used; - m = *arg->solutions + *arg->solutions_used; - strl = writemoves(arg->nmoves, tmoves, l, m); - if (strl < 0) - goto solve_coord_appendsolution_error; - - *arg->solutions_used += MAX(0, strl-1); - - if (!appendchar( - arg->solutions_size, *arg->solutions, 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 int64_t solve_coord_dfs(dfsarg_solve_coord_t *arg) { @@ -77,25 +27,30 @@ solve_coord_dfs(dfsarg_solve_coord_t *arg) coord = arg->coord->coord(arg->cube, arg->coord_data); if (coord == 0) { - if (arg->nmoves != arg->depth) + 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))) return 0; - return solve_coord_appendsolution(arg); + return appendsolution(arg->solution_moves, + arg->solution_settings, arg->solution_list); } pval = get_coord_pval(arg->coord, arg->ptable, coord); - if (arg->nmoves + pval > arg->depth) + if (arg->solution_moves->nmoves + pval > arg->target_depth) return 0; backup_cube = arg->cube; ret = 0; - mm = allowednextmove_mask(arg->nmoves, arg->moves); - arg->nmoves++; - for (m = 0; m < 18; m++) { + 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->moves[arg->nmoves-1] = m; + arg->solution_moves->moves[arg->solution_moves->nmoves-1] = m; arg->cube = move(backup_cube, m); n = solve_coord_dfs(arg); if (n < 0) @@ -103,7 +58,7 @@ solve_coord_dfs(dfsarg_solve_coord_t *arg) ret += n; } arg->cube = backup_cube; - arg->nmoves--; + arg->solution_moves->nmoves--; return 0; } @@ -116,7 +71,7 @@ solve_coord_dispatch( uint8_t minmoves, uint8_t maxmoves, uint64_t maxsolutions, - int optimal, + int8_t optimal, int threads, uint64_t data_size, const void *data, @@ -154,7 +109,7 @@ solve_coord( uint8_t minmoves, uint8_t maxmoves, uint64_t maxsolutions, - int optimal, + int8_t optimal, int threads, uint64_t data_size, const void *data, @@ -163,14 +118,19 @@ solve_coord( ) { int8_t d; - uint8_t t, shortest_sol; - int64_t nsols, ndepth; - size_t solutions_used; + uint8_t t; + int64_t ndepth; cube_t c; const void *coord_data; const uint8_t *ptable; dfsarg_solve_coord_t arg; tableinfo_t info; + solution_moves_t solution_moves; + solution_settings_t solution_settings; + solution_list_t solution_list; + + if (!solution_list_init(&solution_list, solutions_size, sols)) + goto solve_coord_error_buffer; if (readtableinfo(data_size, data, &info) != NISSY_OK) goto solve_coord_error_data; @@ -185,64 +145,59 @@ solve_coord( ptable = (uint8_t *)data + info.next + INFOSIZE; } - nsols = 0; - solutions_used = 0; - shortest_sol = MAXLEN + 1; t = coord->axistrans[axis]; c = transform(cube, t); + solution_moves_reset(&solution_moves); + + solution_settings = (solution_settings_t) { + .tmask = TM_SINGLE(inverse_trans(t)), + .unniss = false, + .maxmoves = maxmoves, + .maxsolutions = maxsolutions, + .optimal = optimal, + }; + arg = (dfsarg_solve_coord_t) { .cube = c, .coord = coord, .coord_data = coord_data, .ptable = ptable, - .trans = t, - .nsols = &nsols, - .maxsolutions = (int64_t)maxsolutions, - .optimal = optimal, - .shortest_sol = &shortest_sol, - .solutions_size = solutions_size, - .solutions_used = &solutions_used, - .solutions = &sols, + .solution_moves = &solution_moves, + .solution_settings = &solution_settings, + .solution_list = &solution_list, }; if (coord->coord(c, coord_data) == 0) { - if (minmoves == 0) { - nsols = 1; - if (!appendchar(solutions_size, sols, &solutions_used, '\n')) + if (minmoves == 0 && !appendsolution( + &solution_moves, &solution_settings, &solution_list)) goto solve_coord_error_buffer; - } goto solve_coord_done; } for ( d = MAX(minmoves, 1); - d <= maxmoves && nsols < (int64_t)maxsolutions - && !(nsols != 0 && d > shortest_sol + optimal); + !solutions_done(&solution_list, &solution_settings, d); d++ ) { if (d >= 10) - LOG("Found %" PRId64 " solutions, searching at depth %" - PRId8 "\n", nsols, d); + LOG("Found %" PRIu64 " solutions, searching at depth %" + PRId8 "\n", solution_list.nsols, d); - arg.depth = d; - arg.nmoves = 0; + arg.target_depth = d; + solution_moves_reset(arg.solution_moves); ndepth = solve_coord_dfs(&arg); - /* TODO: improve error handling? */ if (ndepth < 0) { LOG("Error %" PRId64 "\n", ndepth); return ndepth; } - nsols += ndepth; + solution_list.nsols += (uint64_t)ndepth; } solve_coord_done: - if (!appendchar(solutions_size, sols, &solutions_used, '\0')) - goto solve_coord_error_buffer; - - return nsols; + return (int64_t)solution_list.nsols; solve_coord_error_data: LOG("solve_coord: error reading table\n"); -- cgit v1.3