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 --- 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 ++-- 8 files changed, 132 insertions(+), 98 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 (limited to 'src/solvers') 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); -- cgit v1.3