commit 1983bacfbb84e2a410ebe663ac1fa7c1b22eb096 parent 30526a688c8c8e9ffed34a07e959322f75bc639b Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue, 27 Aug 2024 21:44:19 +0200 Merge branch 'master' of tronto.net:h48 Diffstat:
15 files changed, 219 insertions(+), 43 deletions(-)
diff --git a/shell.c b/shell.c @@ -183,21 +183,21 @@ struct { ), COMMAND( "datasize", - "datasize" _flag_solver " SOLVER " _flag_options " OPTIONS", + "datasize " _flag_solver " SOLVER " _flag_options " OPTIONS", "Return the size in bytes of the data table used by " "SOLVER when called with the given OPTIONS.", datasize_exec ), COMMAND( "gendata", - "gendata" _flag_solver " SOLVER " _flag_options " OPTIONS", + "gendata " _flag_solver " SOLVER " _flag_options " OPTIONS", "Generate the data table used by " "SOLVER when called with the given OPTIONS.", gendata_exec ), COMMAND( "solve", - "solve" _flag_solver " SOLVER " _flag_options " OPTIONS " + "solve " _flag_solver " SOLVER " _flag_options " OPTIONS " "[" _flag_minmoves " n] [" _flag_maxmoves " N] " _flag_cube " CUBE", "Solve the given CUBE using SOLVER with the given OPTIONS, " diff --git a/src/nissy.c b/src/nissy.c @@ -26,23 +26,31 @@ struct { _static int parse_h48_options(const char *buf, uint8_t *h, uint8_t *k, uint8_t *maxdepth) { + bool h_valid, k_valid, maxdepth_valid; int i; /* TODO temporarily, options are in the form "h;k;maxdepth" */ if (h != NULL) *h = atoi(buf); + h_valid = h == NULL || *h <= 11; + for (i = 0; buf[i] != ';'; i++) if (buf[i] == 0) goto parse_h48_options_error; + if (k != NULL) *k = atoi(&buf[i+1]); + k_valid = k == NULL || (*k == 2 || *k == 4); + for (i = i+1; buf[i] != ';'; i++) if (buf[i] == 0) goto parse_h48_options_error; + if (maxdepth != NULL) *maxdepth = atoi(&buf[i+1]); + maxdepth_valid = maxdepth == NULL || *maxdepth <= 20; - return (*h <= 11 && (*k == 2 || *k == 4) && *maxdepth <= 20) ? 0 : 1; + return h_valid && k_valid && maxdepth_valid ? 0 : 1; parse_h48_options_error: *h = 0; @@ -202,7 +210,7 @@ nissy_gendata( if (!strcmp(solver, "h48")) { p = parse_h48_options(options, &arg.h, &arg.k, &arg.maxdepth); if (p != 0) { - LOG("gendata: ould not parse options\n"); + LOG("gendata: could not parse options\n"); ret = -1; } else { ret = gendata_h48(&arg); diff --git a/src/solvers/h48/gendata_cocsep.h b/src/solvers/h48/gendata_cocsep.h @@ -18,13 +18,13 @@ typedef struct { uint8_t *visited; uint64_t *selfsim; cube_t *rep; -} dfsarg_cocsep_t; +} cocsep_dfs_arg_t; _static_inline bool get_visited(const uint8_t *, int64_t); _static_inline void set_visited(uint8_t *, int64_t); _static size_t gendata_cocsep(void *, uint64_t *, cube_t *); -_static uint32_t gendata_cocsep_dfs(dfsarg_cocsep_t *); +_static uint32_t gendata_cocsep_dfs(cocsep_dfs_arg_t *); _static_inline int8_t get_h48_cdata(cube_t, uint32_t *, uint32_t *); @@ -45,7 +45,7 @@ gendata_cocsep(void *buf, uint64_t *selfsim, cube_t *rep) uint32_t *buf32, *info, cc; uint16_t n; uint8_t i, j, visited[COCSEP_VISITEDSIZE]; - dfsarg_cocsep_t arg; + cocsep_dfs_arg_t arg; if (buf == NULL) goto gendata_cocsep_return_size; @@ -56,7 +56,7 @@ gendata_cocsep(void *buf, uint64_t *selfsim, cube_t *rep) if (selfsim != NULL) memset(selfsim, 0, sizeof(uint64_t) * COCSEP_CLASSES); - arg = (dfsarg_cocsep_t) { + arg = (cocsep_dfs_arg_t) { .cube = solved, .n = &n, .buf32 = buf32, @@ -92,14 +92,14 @@ gendata_cocsep_return_size: } _static uint32_t -gendata_cocsep_dfs(dfsarg_cocsep_t *arg) +gendata_cocsep_dfs(cocsep_dfs_arg_t *arg) { uint8_t m; uint32_t cc, class, ttrep, depth, olddepth, tinv; uint64_t t; int64_t i, j; cube_t d; - dfsarg_cocsep_t nextarg; + cocsep_dfs_arg_t nextarg; i = coord_cocsep(arg->cube); olddepth = (uint8_t)(arg->buf32[i] & 0xFF); @@ -135,7 +135,7 @@ gendata_cocsep_dfs(dfsarg_cocsep_t *arg) return cc; } - memcpy(&nextarg, arg, sizeof(dfsarg_cocsep_t)); + memcpy(&nextarg, arg, sizeof(cocsep_dfs_arg_t)); nextarg.depth++; for (m = 0, cc = 0; m < 18; m++) { nextarg.cube = move(arg->cube, m); diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h @@ -1,6 +1,6 @@ -#define H48_COORDMAX_NOEO (COCSEP_CLASSES * (size_t)_12c4 * (size_t)_8c4) -#define H48_COORDMAX(h) (H48_COORDMAX_NOEO << (size_t)(h)) -#define H48_TABLESIZE(h, k) (H48_COORDMAX((h)) / ((size_t)8 / (size_t)(k))) +#define H48_COORDMAX_NOEO ((int64_t)(COCSEP_CLASSES * _12c4 * _8c4)) +#define H48_COORDMAX(h) ((int64_t)(H48_COORDMAX_NOEO << (int64_t)(h))) +#define H48_TABLESIZE(h, k) ((size_t)H48_COORDMAX((h)) / ((size_t)8 / (size_t)(k))) #define H48_COEFF(k) (UINT32_C(32) / (uint32_t)(k)) #define H48_INDEX(i, k) ((uint32_t)(i) / H48_COEFF(k)) @@ -55,7 +55,23 @@ typedef struct { uint64_t *selfsim; int64_t done; cube_t *crep; -} bfsarg_esep_t; +} h48h0k4_bfs_arg_t; + +typedef struct { + cube_t cube; + uint8_t moves[4]; + uint8_t h; + uint8_t k; + uint8_t base; + uint8_t depth; + uint8_t shortdepth; + uint8_t maxdepth; + uint32_t *cocsepdata; + uint32_t *h48data; + uint64_t *selfsim; + cube_t *crep; + h48map_t *shortcubes; +} h48k2_dfs_arg_t; _static_inline uint8_t get_esep_pval(const uint32_t *, int64_t, uint8_t); _static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t, uint8_t); @@ -63,10 +79,11 @@ _static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t, uint8_t); _static uint64_t gen_h48short(gendata_h48short_arg_t *); _static size_t gendata_h48(gendata_h48_arg_t *); _static size_t gendata_h48h0k4(gendata_h48_arg_t *); -_static int64_t gendata_h48h0k4_bfs(bfsarg_esep_t *); -_static int64_t gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *); -_static int64_t gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *); +_static int64_t gendata_h48h0k4_bfs(h48h0k4_bfs_arg_t *); +_static int64_t gendata_h48h0k4_bfs_fromdone(h48h0k4_bfs_arg_t *); +_static int64_t gendata_h48h0k4_bfs_fromnew(h48h0k4_bfs_arg_t *); _static size_t gendata_h48k2(gendata_h48_arg_t *); +_static void gendata_h48k2_dfs(h48k2_dfs_arg_t *arg); _static_inline int8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint8_t, uint32_t *); @@ -150,31 +167,17 @@ _static size_t gendata_h48h0k4(gendata_h48_arg_t *arg) { uint32_t j; - bfsarg_esep_t bfsarg; + h48h0k4_bfs_arg_t bfsarg; int64_t sc, cc, esep_max; -/* - uint64_t selfsim[COCSEP_CLASSES]; - cube_t crep[COCSEP_CLASSES]; - size_t cocsepsize, infosize; -*/ if (arg->buf == NULL) goto gendata_h48h0k4_return_size; -/* - cocsepsize = gendata_cocsep(buf, selfsim, crep); - infosize = 88; - - cocsepdata = (uint32_t *)buf; - buf32 = cocsepdata + cocsepsize / 4; - info = buf32 + (H48_TABLESIZE(0, 4) / sizeof(uint32_t)); - memset(buf32, 0xFF, H48_TABLESIZE(0, 4)); -*/ esep_max = (int64_t)H48_COORDMAX(0); sc = coord_h48(solved, arg->cocsepdata, 0); set_esep_pval(arg->h48data, sc, 4, 0); arg->info[1] = 1; - bfsarg = (bfsarg_esep_t) { + bfsarg = (h48h0k4_bfs_arg_t) { .cocsepdata = arg->cocsepdata, .buf32 = arg->h48data, .selfsim = arg->selfsim, @@ -205,7 +208,7 @@ gendata_h48h0k4_return_size: } _static int64_t -gendata_h48h0k4_bfs(bfsarg_esep_t *arg) +gendata_h48h0k4_bfs(h48h0k4_bfs_arg_t *arg) { const uint8_t breakpoint = 10; /* Hand-picked optimal */ @@ -216,7 +219,7 @@ gendata_h48h0k4_bfs(bfsarg_esep_t *arg) } _static int64_t -gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg) +gendata_h48h0k4_bfs_fromdone(h48h0k4_bfs_arg_t *arg) { uint8_t c, m, x; uint32_t cc; @@ -246,7 +249,7 @@ gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg) } _static int64_t -gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *arg) +gendata_h48h0k4_bfs_fromnew(h48h0k4_bfs_arg_t *arg) { uint8_t c, m, x; uint32_t cc; @@ -298,9 +301,13 @@ gendata_h48k2(gendata_h48_arg_t *arg) [11] = 10 }; - uint64_t nshort; + uint8_t t; + int64_t j; + uint64_t nshort, i; h48map_t shortcubes; + kvpair_t kv; gendata_h48short_arg_t shortarg; + h48k2_dfs_arg_t dfsarg; DBG_ASSERT(base[arg->h] == 8, 0, "Only implemented for h <= 3 (base 8)\n"); @@ -317,17 +324,84 @@ gendata_h48k2(gendata_h48_arg_t *arg) .map = &shortcubes }; nshort = gen_h48short(&shortarg); - LOG("Found %" PRIu64 "\n", nshort); + LOG("Cubes in <= %" PRIu8 " moves: %" PRIu64 "\n", shortdepth, nshort); + + dfsarg = (h48k2_dfs_arg_t){ + .h = arg->h, + .k = arg->k, + .base = base[arg->h], + .depth = shortdepth, + .shortdepth = shortdepth, + .maxdepth = arg->maxdepth, + .cocsepdata = arg->cocsepdata, + .h48data = arg->h48data, + .selfsim = arg->selfsim, + .crep = arg->crep, + .shortcubes = &shortcubes + }; - /* TODO: loop over map, set all found to 0, do 2 moves each */ - LOG("The rest is not implemented yet\n"); + i = 0; + for (kv = h48map_nextkvpair(&shortcubes, &i); + i != shortcubes.capacity; + kv = h48map_nextkvpair(&shortcubes, &i) + ) { + /* TODO maybe over all sim? */ + dfsarg.cube = invcoord_h48(kv.key, arg->crep, 11); + gendata_h48k2_dfs(&dfsarg); + } h48map_destroy(&shortcubes); + /* TODO: move info update to dfs? */ + memset(arg->info, 0, 5 * sizeof(arg->info[0])); + arg->info[0] = base[arg->k]; + for (j = 0; j < H48_COORDMAX(arg->h); j++) { + t = get_esep_pval(arg->h48data, j, 2); + arg->info[1 + t]++; + } + gendata_h48k2_return_size: return H48_TABLESIZE(arg->h, 2); } +_static void +gendata_h48k2_dfs(h48k2_dfs_arg_t *arg) +{ + uint8_t nmoves; + uint64_t val; + int64_t coord, fullcoord; + h48k2_dfs_arg_t nextarg; + uint8_t m; + + fullcoord = coord_h48(arg->cube, arg->cocsepdata, 11); + coord = fullcoord >> (int64_t)(11 - arg->h); + + val = h48map_value(arg->shortcubes, fullcoord); + + if (arg->depth >= arg->base && arg->depth <= arg->base + 2) + set_esep_pval( + arg->h48data, coord, arg->k, arg->depth - arg->base); + + if ((val < arg->shortdepth) || + (arg->depth > arg->shortdepth && val != MAP_UNSET) || + (arg->depth >= arg->maxdepth || arg->depth >= arg->base + 2)) + return; + + /* TODO: avoid copy, change arg and undo changes after recursion */ + nextarg = *arg; + nextarg.depth = arg->depth + 1; + nmoves = nextarg.depth - arg->shortdepth; + for (m = 0; m < 18; m++) { + nextarg.moves[nmoves - 1] = m; + if (!allowednextmove(nextarg.moves, nmoves)) { + m += 2; + continue; + } + nextarg.cube = move(arg->cube, m); + gendata_h48k2_dfs(&nextarg); + } +} + _static_inline uint8_t get_esep_pval(const uint32_t *buf32, int64_t i, uint8_t k) { diff --git a/src/solvers/h48/h48.h b/src/solvers/h48/h48.h @@ -1,5 +1,5 @@ #include "coordinate.h" #include "map.h" #include "gendata_cocsep.h" -#include "gendata_full.h" +#include "gendata_h48.h" #include "solve.h" diff --git a/test/113_gen_h48short/00_depth_1.in b/test/112_gen_h48short/00_depth_1.in diff --git a/test/113_gen_h48short/00_depth_1.out b/test/112_gen_h48short/00_depth_1.out diff --git a/test/113_gen_h48short/01_depth_3.in b/test/112_gen_h48short/01_depth_3.in diff --git a/test/113_gen_h48short/01_depth_3.out b/test/112_gen_h48short/01_depth_3.out diff --git a/test/113_gen_h48short/gen_h48short.c b/test/112_gen_h48short/gen_h48short.c diff --git a/test/112_gendata_h48/00_h_0.in b/test/120_gendata_h48h0k4/00_h_0.in diff --git a/test/112_gendata_h48/00_h_0.out b/test/120_gendata_h48h0k4/00_h_0.out diff --git a/test/112_gendata_h48/gendata_h48_tests.c b/test/120_gendata_h48h0k4/gendata_h48h0k4_tests.c diff --git a/tools/001_gendata_h48/gendata_h48.c b/tools/001_gendata_h48h0k4/gendata_h48h0k4.c diff --git a/tools/003_solve_small/solve_small.c b/tools/003_solve_small/solve_small.c @@ -0,0 +1,94 @@ +#include <pthread.h> +#include <time.h> +#include "../timerun.h" +#include "../../src/nissy.h" + +#define OPTIONS "0;4;20" + +const char *filename = "tables/h48h0k4"; +char *buf; +char *scrambles[] = { + "R D' R2 D R U2 R' D' R U2 R D R'", /* 12 optimal */ + "RLUD RLUD RLUD", /* 12 optimal */ + NULL +}; + +void run(void) { + int i; + int64_t n; + char sol[100], cube[22]; + + printf("Solved the following scrambles:\n\n"); + for (i = 0; scrambles[i] != NULL; i++) { + printf("%s\n", scrambles[i]); + fprintf(stderr, "Solving scramble %s\n", scrambles[i]); + if (nissy_frommoves(scrambles[i], cube) == -1) { + fprintf(stderr, "Invalid scramble, " + "continuing with next scramble\n"); + continue; + } + n = nissy_solve( + cube, "h48", OPTIONS, "", 0, 20, 1, -1, buf, sol); + if (n == 0) + fprintf(stderr, "No solution found, " + "continuing with next scramble\n"); + } + printf("\n"); +} + +int getdata(int64_t size) { + int64_t s; + FILE *f; + + buf = malloc(size); + + if ((f = fopen(filename, "rb")) == NULL) { + fprintf(stderr, "Table file not found, generating them." + " This can take a while.\n"); + s = nissy_gendata("h48", OPTIONS, buf); + if (s != size) { + fprintf(stderr, "Error generating table"); + if (s != -1) + fprintf(stderr, " (got %" PRId64 " bytes)", s); + fprintf(stderr, "\n"); + return 1; + } + if ((f = fopen(filename, "wb")) == NULL) { + fprintf(stderr, "Could not write tables to file %s" + ", will be regenerated next time.\n", filename); + } else { + fwrite(buf, size, 1, f); + fclose(f); + } + } else { + fprintf(stderr, "Reading tables from file %s\n", filename); + fread(buf, size, 1, f); + fclose(f); + } + + return 0; +} + +int main(void) { + int64_t size; + + srand(time(NULL)); + + nissy_setlogger(log_stderr); + size = nissy_datasize("h48", OPTIONS); + if (size == -1) { + printf("h48 stats: error in datasize\n"); + return 1; + } + + if (getdata(size) != 0) { + printf("Error getting table, stopping\n"); + free(buf); + return 1; + } + + timerun(run, "small solver benchmark"); + + free(buf); + return 0; +}