commit a2b868261d0504c95b1091db0ce014fd567281c3 parent 81daed66c3415827de7ab6a15c081a8f696f7a95 Author: Enrico Tenuti <123324975+enricotenuti@users.noreply.github.com> Date: Thu, 29 Aug 2024 19:03:11 +0200 Merge branch 'sebastianotronto:master' into master Diffstat:
12 files changed, 205 insertions(+), 37 deletions(-)
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/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; +}