From 18c9a8b8905304cf5f8fc15825769046a3144866 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sun, 18 Aug 2024 14:26:45 +0200 Subject: Reorganized folder structure --- src/solvers/generic/generic.h | 157 ++++++++++++++++ src/solvers/h48/coordinate.h | 68 +++++++ src/solvers/h48/gendata.h | 425 ++++++++++++++++++++++++++++++++++++++++++ src/solvers/h48/h48.h | 4 + src/solvers/h48/map.h | 104 +++++++++++ src/solvers/h48/solve.h | 242 ++++++++++++++++++++++++ src/solvers/solvers.h | 2 + 7 files changed, 1002 insertions(+) create mode 100644 src/solvers/generic/generic.h create mode 100644 src/solvers/h48/coordinate.h create mode 100644 src/solvers/h48/gendata.h create mode 100644 src/solvers/h48/h48.h create mode 100644 src/solvers/h48/map.h create mode 100644 src/solvers/h48/solve.h create mode 100644 src/solvers/solvers.h (limited to 'src/solvers') diff --git a/src/solvers/generic/generic.h b/src/solvers/generic/generic.h new file mode 100644 index 0000000..41d995a --- /dev/null +++ b/src/solvers/generic/generic.h @@ -0,0 +1,157 @@ +typedef struct { + cube_t cube; + uint8_t depth; + int64_t maxsols; + char **nextsol; + int64_t *nsols; + uint8_t nmoves; + uint8_t moves[20]; + uint8_t (*estimate)(cube_t); +} dfsarg_generic_t; + +_static void solve_generic_appendsolution(dfsarg_generic_t *); +_static int solve_generic_dfs(dfsarg_generic_t *); +_static int64_t solve_generic(cube_t, const char *, int8_t, int8_t, int64_t, + int8_t, char *, uint8_t (*)(cube_t)); +_static uint8_t estimate_simple(cube_t); +_static int64_t solve_simple(cube_t, int8_t, int8_t, int64_t, int8_t, char *); + +_static void +solve_generic_appendsolution(dfsarg_generic_t *arg) +{ + int strl; + + strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol); + LOG("Solution found: %s\n", *arg->nextsol); + *arg->nextsol += strl; + **arg->nextsol = '\n'; + (*arg->nextsol)++; + (*arg->nsols)++; +} + +_static int +solve_generic_dfs(dfsarg_generic_t *arg) +{ + dfsarg_generic_t nextarg; + uint8_t m, bound; + int64_t ret; + + if (!allowednextmove(arg->moves, arg->nmoves)) + return 0; + + if (arg->nmoves > 0) + arg->cube = move(arg->cube, arg->moves[arg->nmoves-1]); + + bound = arg->estimate(arg->cube); + if (*arg->nsols == arg->maxsols || bound + arg->nmoves > arg->depth) + return 0; + + if (bound == 0) { + if (arg->nmoves != arg->depth) + return 0; + solve_generic_appendsolution(arg); + return 1; + } + + nextarg = *arg; + nextarg.nmoves = arg->nmoves + 1; + for (m = 0, ret = 0; m < 18; m++) { + nextarg.cube = arg->cube; + nextarg.moves[arg->nmoves] = m; + ret += solve_generic_dfs(&nextarg); + } + + return ret; +} + +_static int64_t +solve_generic( + cube_t cube, + const char *nisstype, + /* TODO: handle NISS */ + int8_t minmoves, + int8_t maxmoves, + int64_t maxsols, + int8_t optimal, + char *sols, + uint8_t (*estimate)(cube_t) + /* TODO: add validator */ + /* TODO: maybe add data for estimate */ + /* TODO: add moveset (and allowednext?) */ +) +{ + dfsarg_generic_t arg; + int64_t ret, tmp, first; + + if (issolved(cube)) { + LOG("solve: cube is already solved\n"); + sols[0] = '\n'; + sols[1] = 0; + return 1; + } + + if (estimate == NULL) { + LOG("solve: 'estimate' is NULL\n"); + return -1; + } + + arg = (dfsarg_generic_t) { + .cube = cube, + .maxsols = maxsols, + .nextsol = &sols, + .nsols = &ret, + .nmoves = 0, + .moves = {0}, + .estimate = estimate, + }; + + ret = 0; + first = -1; + for (arg.depth = minmoves; arg.depth <= maxmoves; arg.depth++) { + tmp = solve_generic_dfs(&arg); + if (tmp != 0) + first = arg.depth; + + LOG("Found %" PRId64 " solution%s at depth %" PRIu8 "\n", + tmp, tmp == 1 ? "" : "s", arg.depth); + + if (ret >= maxsols) + break; + + if (optimal >= 0 && first >= 0 && arg.depth - first == optimal) + break; + } + + DBG_ASSERT(ret <= maxsols, ret, + "solve: found more than 'maxsols' solutions\n"); + + return ret; +} + +_static uint8_t +estimate_simple(cube_t cube) +{ + return issolved(cube) ? 0 : 1; +} + +_static int64_t +solve_simple( + cube_t cube, + int8_t minmoves, + int8_t maxmoves, + int64_t maxsols, + int8_t optimal, + char *solutions +) +{ + return solve_generic( + cube, + "", + minmoves, + maxmoves, + maxsols, + optimal, + solutions, + &estimate_simple + ); +} diff --git a/src/solvers/h48/coordinate.h b/src/solvers/h48/coordinate.h new file mode 100644 index 0000000..47b805d --- /dev/null +++ b/src/solvers/h48/coordinate.h @@ -0,0 +1,68 @@ +#define H48_ESIZE(h) ((_12c4 * _8c4) << (int64_t)(h)) + +#define COCLASS_MASK (UINT32_C(0xFFFF) << UINT32_C(16)) +#define COCLASS(x) (((x) & COCLASS_MASK) >> UINT32_C(16)) +#define TTREP_MASK (UINT32_C(0xFF) << UINT32_C(8)) +#define TTREP(x) (((x) & TTREP_MASK) >> UINT32_C(8)) + +_static_inline int64_t coord_h48(cube_t, const uint32_t *, uint8_t); +_static_inline int64_t coord_h48_edges(cube_t, int64_t, uint8_t, uint8_t); +_static_inline cube_t invcoord_h48(int64_t, const cube_t *, uint8_t); + +_static_inline int64_t +coord_h48(cube_t c, const uint32_t *cocsepdata, uint8_t h) +{ + int64_t cocsep, coclass; + uint32_t data; + uint8_t ttrep; + + DBG_ASSERT(h <= 11, -1, "coord_h48: h must be between 0 and 11\n"); + + cocsep = coord_cocsep(c); + data = cocsepdata[cocsep]; + coclass = (int64_t)COCLASS(data); + ttrep = (int64_t)TTREP(data); + + return coord_h48_edges(c, coclass, ttrep, h); +} + +_static_inline int64_t +coord_h48_edges(cube_t c, int64_t coclass, uint8_t ttrep, uint8_t h) +{ + cube_t d; + int64_t esep, eo, edges; + + d = transform_edges(c, ttrep); + esep = coord_esep(d); + eo = coord_eo(d); + edges = (esep << 11) + eo; + + return (coclass * H48_ESIZE(11) + edges) >> (11 - (int64_t)h); +} + +/* +This function does not necessarily return a cube whose coordinate is +the given value, because it works up to symmetry. This means that the +returned cube is a transformed cube of one that gives the correct value. +*/ +_static_inline cube_t +invcoord_h48(int64_t i, const cube_t *crep, uint8_t h) +{ + cube_t ret; + int64_t hh, coclass, ee, esep, eo; + + DBG_ASSERT(h <= 11, zero, + "invcoord_h48: h must be between 0 and 11\n"); + + hh = (int64_t)h; + coclass = i / H48_ESIZE(h); + ee = i % H48_ESIZE(h); + esep = ee >> hh; + eo = (ee & ((1 << hh) - 1)) << (11 - hh); + + ret = invcoord_esep(esep); + copy_corners(&ret, crep[coclass]); + set_eo(&ret, eo); + + return ret; +} diff --git a/src/solvers/h48/gendata.h b/src/solvers/h48/gendata.h new file mode 100644 index 0000000..d6bf85b --- /dev/null +++ b/src/solvers/h48/gendata.h @@ -0,0 +1,425 @@ +#define COCSEP_CLASSES ((size_t)3393) +#define COCSEP_TABLESIZE ((size_t)_3p7 << (size_t)7) +#define COCSEP_VISITEDSIZE ((COCSEP_TABLESIZE + (size_t)7) / (size_t)8) +#define COCSEP_FULLSIZE ((size_t)4 * (COCSEP_TABLESIZE + (size_t)12)) + +#define ESEP_NOEO (COCSEP_CLASSES * (size_t)_12c4 * (size_t)_8c4) +#define ESEP_MAX(h) (ESEP_NOEO << (size_t)(h)) +#define ESEP_TABLESIZE(h, k) (ESEP_MAX((h)) / ((size_t)8 / (size_t)(k))) + +#define ESEP_IND(i) ((uint32_t)(i) / UINT32_C(8)) +#define ESEP_SHIFT(i) (UINT32_C(4) * ((uint32_t)(i) % UINT32_C(8))) +#define ESEP_MASK(i) ((_bit_u32(4) - (uint32_t)(1)) << ESEP_SHIFT(i)) +#define VISITED_IND(i) ((uint32_t)(i) / UINT32_C(8)) +#define VISITED_MASK(i) (UINT32_C(1) << ((uint32_t)(i) % UINT32_C(8))) + +#define CBOUND_MASK UINT32_C(0xFF) +#define CBOUND(x) ((x) & CBOUND_MASK) + +#define MAXLEN 20 + +/* +TODO: This loop over similar h48 coordinates can be improved by only +transforming edges, but we need to compose transformations (i.e. conjugate +_t by _ttrep). +*/ +#define _foreach_h48sim(_cube, _cocsepdata, _selfsim, _h, _action) \ + int64_t _cocsep = coord_cocsep(_cube); \ + uint8_t _ttrep = TTREP(_cocsepdata[_cocsep]); \ + uint8_t _inverse_ttrep = inverse_trans(_ttrep); \ + int64_t _coclass = COCLASS(_cocsepdata[_cocsep]); \ + cube_t _rep = transform(_cube, _ttrep); \ + uint64_t _sim = _selfsim[_coclass]; \ + for (uint8_t _t = 0; _t < 48 && _sim; _t++, _sim >>= 1) { \ + if (!(_sim & 1)) continue; \ + _cube = transform(_rep, _t); \ + _cube = transform(_cube, _inverse_ttrep); \ + _action \ + } + +typedef struct { + cube_t cube; + uint8_t depth; + uint8_t maxdepth; + uint16_t *n; + uint32_t *buf32; + uint8_t *visited; + uint64_t *selfsim; + cube_t *rep; +} dfsarg_cocsep_t; + +/* TODO keep or not? */ +typedef struct { + cube_t cube; + int8_t nmoves; + int8_t depth; + uint8_t moves[MAXLEN]; + uint32_t *cocsepdata; + h48map_t *visited; +} dfsarg_genh48set_t; + +typedef struct { + uint8_t depth; + uint32_t *cocsepdata; + uint32_t *buf32; + uint64_t *selfsim; + int64_t done; + cube_t *crep; +} bfsarg_esep_t; + +_static_inline bool get_visited(const uint8_t *, int64_t); +_static_inline void set_visited(uint8_t *, int64_t); +_static_inline uint8_t get_esep_pval(const uint32_t *, int64_t); +_static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t); + +_static size_t gendata_cocsep(void *, uint64_t *, cube_t *); +_static uint32_t gendata_cocsep_dfs(dfsarg_cocsep_t *); +_static uint64_t gen_h48short( + uint8_t, const uint32_t *, const cube_t *, const uint64_t *, h48map_t *); +_static size_t gendata_h48h0k4(void *, uint8_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_inline int8_t get_h48_cdata(cube_t, uint32_t *, uint32_t *); +_static_inline int8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint32_t *); + +/* +Each element of the cocsep table is a uint32_t used as follows: + - Lowest 8-bit block: pruning value + - Second-lowest 8-bit block: "ttrep" (transformation to representative) + - Top 16-bit block: symcoord value +After the data as described above, more auxiliary information is appended: + - A uint32_t representing the number of symmetry classes + - A uint32_t representing the highest value of the pruning table + - One uint32_t for each "line" of the pruning table, representing the number + of positions having that pruning value. +*/ +_static size_t +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; + + if (buf == NULL) + goto gendata_cocsep_return_size; + + buf32 = (uint32_t *)buf; + info = buf32 + COCSEP_TABLESIZE; + memset(buf32, 0xFF, sizeof(uint32_t) * COCSEP_TABLESIZE); + if (selfsim != NULL) + memset(selfsim, 0, sizeof(uint64_t) * COCSEP_CLASSES); + + arg = (dfsarg_cocsep_t) { + .cube = solved, + .n = &n, + .buf32 = buf32, + .visited = visited, + .selfsim = selfsim, + .rep = rep + }; + for (i = 0, n = 0, cc = 0; i < 10; i++) { + LOG("cocsep: generating depth %" PRIu8 "\n", i); + memset(visited, 0, COCSEP_VISITEDSIZE); + arg.depth = 0; + arg.maxdepth = i; + cc = gendata_cocsep_dfs(&arg); + info[i+2] = cc; + LOG("found %" PRIu32 "\n", cc); + } + + info[0] = (uint32_t)n; + info[1] = 9; /* Known max pruning value */ + DBG_ASSERT(n == COCSEP_CLASSES, 0, + "cocsep: computed %" PRIu16 " symmetry classes, " + "expected %zu\n", n, COCSEP_CLASSES); + + LOG("cocsep data computed\n"); + LOG("Symmetry classes: %" PRIu32 "\n", info[0]); + LOG("Maximum pruning value: %" PRIu32 "\n", info[1]); + LOG("Pruning value distribution:\n"); + for (j = 0; j < 10; j++) + LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, info[j+2]); + +gendata_cocsep_return_size: + return COCSEP_FULLSIZE; +} + +_static uint32_t +gendata_cocsep_dfs(dfsarg_cocsep_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; + + i = coord_cocsep(arg->cube); + olddepth = (uint8_t)(arg->buf32[i] & 0xFF); + if (olddepth < arg->depth || get_visited(arg->visited, i)) + return 0; + set_visited(arg->visited, i); + + if (arg->depth == arg->maxdepth) { + if ((arg->buf32[i] & 0xFF) != 0xFF) + return 0; + + if (arg->rep != NULL) + arg->rep[*arg->n] = arg->cube; + for (t = 0, cc = 0; t < 48; t++) { + d = transform_corners(arg->cube, t); + j = coord_cocsep(d); + if (i == j && arg->selfsim != NULL) + arg->selfsim[*arg->n] |= UINT64_C(1) << t; + if (COCLASS(arg->buf32[j]) != UINT32_C(0xFFFF)) + continue; + set_visited(arg->visited, j); + tinv = inverse_trans(t); + olddepth = arg->buf32[j] & 0xFF; + cc += olddepth == 0xFF; + + class = (uint32_t)(*arg->n) << UINT32_C(16); + ttrep = (uint32_t)tinv << UINT32_C(8); + depth = (uint32_t)arg->depth; + arg->buf32[j] = class | ttrep | depth; + } + (*arg->n)++; + + return cc; + } + + memcpy(&nextarg, arg, sizeof(dfsarg_cocsep_t)); + nextarg.depth++; + for (m = 0, cc = 0; m < 18; m++) { + nextarg.cube = move(arg->cube, m); + cc += gendata_cocsep_dfs(&nextarg); + } + + return cc; +} + +_static uint64_t +gen_h48short( + uint8_t n, + const uint32_t *cocsepdata, + const cube_t *crep, + const uint64_t *selfsim, + h48map_t *map +) { + uint8_t i, m; + int64_t coord; + uint64_t j, oldn; + kvpair_t kv; + cube_t cube, d; + + cube = solvedcube(); + coord = coord_h48(cube, cocsepdata, 11); + h48map_insertmin(map, coord, 0); + oldn = 0; + LOG("Short h48: generating depth 0\nfound %" PRIu8 "\n", map->n-oldn); + for (i = 0; i < n; i++) { + LOG("Short h48: generating depth %" PRIu8 "\n", i+1); + j = 0; + oldn = map->n; + for (kv = h48map_nextkvpair(map, &j); + j != map->capacity; + kv = h48map_nextkvpair(map, &j) + ) { + if (kv.val != i) + continue; + cube = invcoord_h48(kv.key, crep, 11); + for (m = 0; m < 18; m++) { + d = move(cube, m); + _foreach_h48sim(d, cocsepdata, selfsim, 11, + coord = coord_h48(d, cocsepdata, 11); + h48map_insertmin(map, coord, i+1); + ) + } + } + LOG("found %" PRIu8 "\n", map->n-oldn); + } + + return map->n; +} + +/* +TODO description +generating fixed table with h=0, k=4 +*/ +_static size_t +gendata_h48h0k4(void *buf, uint8_t maxdepth) +{ + uint32_t j, *buf32, *info, *cocsepdata; + bfsarg_esep_t arg; + int64_t sc, cc, esep_max; + uint64_t selfsim[COCSEP_CLASSES]; + cube_t crep[COCSEP_CLASSES]; + size_t cocsepsize, infosize; + + /* TODO: move info at start of tables (all tables!) */ + infosize = 4 * maxdepth; + cocsepsize = gendata_cocsep(buf, selfsim, crep); + infosize = 88; + + if (buf == NULL) + goto gendata_h48h0k4_return_size; + + esep_max = (int64_t)ESEP_MAX(0); + cocsepdata = (uint32_t *)buf; + buf32 = cocsepdata + cocsepsize / 4; + info = buf32 + (ESEP_TABLESIZE(0, 4) / sizeof(uint32_t)); + memset(buf32, 0xFF, ESEP_TABLESIZE(0, 4)); + + sc = coord_h48(solved, cocsepdata, 0); + set_esep_pval(buf32, sc, 0); + info[1] = 1; + arg = (bfsarg_esep_t) { + .cocsepdata = cocsepdata, + .buf32 = buf32, + .selfsim = selfsim, + .crep = crep + }; + for ( + arg.done = 1, arg.depth = 1, cc = 0; + arg.done < esep_max && arg.depth <= maxdepth; + arg.depth++ + ) { + LOG("esep: generating depth %" PRIu8 "\n", arg.depth); + cc = gendata_h48h0k4_bfs(&arg); + arg.done += cc; + info[arg.depth+1] = cc; + LOG("found %" PRId64 "\n", cc); + } + + info[0] = arg.depth-1; + + LOG("h48 pruning table computed\n"); + LOG("Maximum pruning value: %" PRIu32 "\n", info[0]); + LOG("Pruning value distribution:\n"); + for (j = 0; j <= info[0]; j++) + LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, info[j+1]); + +gendata_h48h0k4_return_size: + return cocsepsize + ESEP_TABLESIZE(0, 4) + infosize; +} + +_static int64_t +gendata_h48h0k4_bfs(bfsarg_esep_t *arg) +{ + const uint8_t breakpoint = 10; /* Hand-picked optimal */ + + if (arg->depth < breakpoint) + return gendata_h48h0k4_bfs_fromdone(arg); + else + return gendata_h48h0k4_bfs_fromnew(arg); +} + +_static int64_t +gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg) +{ + uint8_t c, m, x; + uint32_t cc; + int64_t i, j, k; + cube_t cube, moved; + + for (i = 0, cc = 0; i < (int64_t)ESEP_MAX(0); i++) { + c = get_esep_pval(arg->buf32, i); + if (c != arg->depth - 1) + continue; + cube = invcoord_h48(i, arg->crep, 0); + for (m = 0; m < 18; m++) { + moved = move(cube, m); + j = coord_h48(moved, arg->cocsepdata, 0); + if (get_esep_pval(arg->buf32, j) <= arg->depth) + continue; + _foreach_h48sim(moved, arg->cocsepdata, arg->selfsim, 0, + k = coord_h48(moved, arg->cocsepdata, 0); + x = get_esep_pval(arg->buf32, k); + set_esep_pval(arg->buf32, k, arg->depth); + cc += x != arg->depth; + ) + } + } + + return cc; +} + +_static int64_t +gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *arg) +{ + uint8_t c, m, x; + uint32_t cc; + int64_t i, j; + cube_t cube, moved; + + for (i = 0, cc = 0; i < (int64_t)ESEP_MAX(0); i++) { + c = get_esep_pval(arg->buf32, i); + if (c != 0xF) + continue; + cube = invcoord_h48(i, arg->crep, 0); + for (m = 0; m < 18; m++) { + moved = move(cube, m); + j = coord_h48(moved, arg->cocsepdata, 0); + x = get_esep_pval(arg->buf32, j); + if (x >= arg->depth) + continue; + _foreach_h48sim(cube, arg->cocsepdata, arg->selfsim, 0, + j = coord_h48(cube, arg->cocsepdata, 0); + x = get_esep_pval(arg->buf32, j); + set_esep_pval(arg->buf32, j, arg->depth); + cc += x == 0xF; + ) + break; /* Enough to find one, skip the rest */ + } + } + + return cc; +} + +_static_inline bool +get_visited(const uint8_t *a, int64_t i) +{ + return a[VISITED_IND(i)] & VISITED_MASK(i); +} + +_static_inline void +set_visited(uint8_t *a, int64_t i) +{ + a[VISITED_IND(i)] |= VISITED_MASK(i); +} + +_static_inline uint8_t +get_esep_pval(const uint32_t *buf32, int64_t i) +{ + return (buf32[ESEP_IND(i)] & ESEP_MASK(i)) >> ESEP_SHIFT(i); +} + +_static_inline void +set_esep_pval(uint32_t *buf32, int64_t i, uint8_t val) +{ + buf32[ESEP_IND(i)] = + (buf32[ESEP_IND(i)] & (~ESEP_MASK(i))) | (val << ESEP_SHIFT(i)); +} + +_static_inline int8_t +get_h48_cdata(cube_t cube, uint32_t *cocsepdata, uint32_t *cdata) +{ + int64_t coord; + + coord = coord_cocsep(cube); + *cdata = cocsepdata[coord]; + + return CBOUND(*cdata); +} + +_static_inline int8_t +get_h48_bound(cube_t cube, uint32_t cdata, uint8_t h, uint32_t *h48data) +{ + int64_t coord; + + coord = coord_h48_edges(cube, COCLASS(cdata), TTREP(cdata), h); + return get_esep_pval(h48data, coord); +} diff --git a/src/solvers/h48/h48.h b/src/solvers/h48/h48.h new file mode 100644 index 0000000..d33ad63 --- /dev/null +++ b/src/solvers/h48/h48.h @@ -0,0 +1,4 @@ +#include "coordinate.h" +#include "map.h" +#include "gendata.h" +#include "solve.h" diff --git a/src/solvers/h48/map.h b/src/solvers/h48/map.h new file mode 100644 index 0000000..82e5a2c --- /dev/null +++ b/src/solvers/h48/map.h @@ -0,0 +1,104 @@ +#define MAP_UNSET UINT64_C(0xFFFFFFFFFFFFFFFF) +#define MAP_KEYMASK UINT64_C(0xFFFFFFFFFF) +#define MAP_KEYSHIFT UINT64_C(40) + +typedef struct { + uint64_t n; + uint64_t capacity; + uint64_t randomizer; + uint64_t *table; +} h48map_t; + +typedef struct { + uint64_t key; + uint64_t val; +} kvpair_t; + +_static void h48map_create(h48map_t *, uint64_t, uint64_t); +_static void h48map_clear(h48map_t *); +_static void h48map_destroy(h48map_t *); +_static uint64_t h48map_lookup(h48map_t *, uint64_t); +_static void h48map_insertmin(h48map_t *, uint64_t, uint64_t); +_static uint64_t h48map_value(h48map_t *, uint64_t); +_static kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *); + +_static void +h48map_create(h48map_t *map, uint64_t capacity, uint64_t randomizer) +{ + map->capacity = capacity; + map->randomizer = randomizer; + + map->table = malloc(map->capacity * sizeof(int64_t)); + h48map_clear(map); +} + +_static void +h48map_clear(h48map_t *map) +{ + memset(map->table, 0xFF, map->capacity * sizeof(uint64_t)); + map->n = 0; +} + +_static void +h48map_destroy(h48map_t *map) +{ + free(map->table); +} + +_static_inline uint64_t +h48map_lookup(h48map_t *map, uint64_t x) +{ + uint64_t hash, i; + + hash = ((x % map->capacity) * map->randomizer) % map->capacity; + for (i = hash; + map->table[i] != MAP_UNSET && (map->table[i] & MAP_KEYMASK) != x; + i = (i+1) % map->capacity + ) ; + + return i; +} + +_static_inline void +h48map_insertmin(h48map_t *map, uint64_t key, uint64_t val) +{ + uint64_t i, oldval, min; + + i = h48map_lookup(map, key); + oldval = map->table[i] >> MAP_KEYSHIFT; + min = _min(val, oldval); + + map->n += map->table[i] == MAP_UNSET; + map->table[i] = (key & MAP_KEYMASK) | (min << MAP_KEYSHIFT); +} + +_static_inline uint64_t +h48map_value(h48map_t *map, uint64_t key) +{ + return map->table[h48map_lookup(map, key)] >> MAP_KEYSHIFT; +} + +_static kvpair_t +h48map_nextkvpair(h48map_t *map, uint64_t *p) +{ + kvpair_t kv; + uint64_t pair; + + kv.key = MAP_UNSET; + kv.val = MAP_UNSET; + + DBG_ASSERT(*p < map->capacity, kv, + "Error looping over map: given index %" PRIu64 " is out of " + "range [0,%" PRIu64 "]", *p, map->capacity); + + for ( ; *p < map->capacity; (*p)++) { + if (map->table[*p] != MAP_UNSET) { + pair = map->table[(*p)++]; + kv.key = pair & MAP_KEYMASK; + kv.val = pair >> MAP_KEYSHIFT; + return kv; + } + } + + return kv; +} diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h new file mode 100644 index 0000000..8531a40 --- /dev/null +++ b/src/solvers/h48/solve.h @@ -0,0 +1,242 @@ +typedef struct { + cube_t cube; + cube_t inverse; + int8_t nmoves; + int8_t depth; + uint8_t moves[MAXLEN]; + int64_t *nsols; + int64_t maxsolutions; + uint8_t h; + uint32_t *cocsepdata; + uint32_t *h48data; + char **nextsol; +} dfsarg_solveh48_t; + +typedef struct { + cube_t cube; + int8_t nmoves; + int8_t depth; + uint8_t moves[MAXLEN]; + uint32_t *cocsepdata; + uint32_t *h48data; + char *s; +} dfsarg_solveh48stats_t; + +_static void solve_h48_appendsolution(dfsarg_solveh48_t *); +_static_inline bool solve_h48_stop(dfsarg_solveh48_t *); +_static int64_t solve_h48_dfs(dfsarg_solveh48_t *); +_static int64_t solve_h48( + cube_t, int8_t, int8_t, int8_t, uint8_t, const void *, char *); + +_static int64_t solve_h48stats_dfs(dfsarg_solveh48stats_t *); +_static int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]); + +_static void +solve_h48_appendsolution(dfsarg_solveh48_t *arg) +{ + int strl; + + strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol); + LOG("Solution found: %s\n", *arg->nextsol); + *arg->nextsol += strl; + **arg->nextsol = '\n'; + (*arg->nextsol)++; + (*arg->nsols)++; +} + +_static_inline bool +solve_h48_stop(dfsarg_solveh48_t *arg) +{ + uint32_t data, data_inv; + int8_t bound; + + bound = get_h48_cdata(arg->cube, arg->cocsepdata, &data); + if (bound + arg->nmoves > arg->depth) + return true; + + bound = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv); + if (bound + arg->nmoves > arg->depth) + return true; + +/* + bound = get_h48_bound(arg->cube, data, arg->h, arg->h48data); +LOG("Using pval %" PRId8 "\n", bound); + if (bound + arg->nmoves > arg->depth) + return true; + + bound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->h48data); + if (bound + arg->nmoves > arg->depth) + return true; +*/ + + return false; +} + +_static int64_t +solve_h48_dfs(dfsarg_solveh48_t *arg) +{ + dfsarg_solveh48_t nextarg; + int64_t ret; + uint8_t m; + + if (*arg->nsols == arg->maxsolutions) + return 0; + + if (solve_h48_stop(arg)) + return 0; + + if (issolved(arg->cube)) { + if (arg->nmoves != arg->depth) + return 0; + solve_h48_appendsolution(arg); + return 1; + } + + /* TODO: avoid copy, change arg and undo changes after recursion */ + nextarg = *arg; + nextarg.nmoves = arg->nmoves + 1; + ret = 0; + for (m = 0; m < 18; m++) { + nextarg.moves[arg->nmoves] = m; + if (!allowednextmove(nextarg.moves, nextarg.nmoves)) { + /* If a move is not allowed, neither are its 180 + * and 270 degree variations */ + m += 2; + continue; + } + nextarg.cube = move(arg->cube, m); + nextarg.inverse = inverse(nextarg.cube); /* TODO: use premove */ + ret += solve_h48_dfs(&nextarg); + } + + return ret; +} + +_static int64_t +solve_h48( + cube_t cube, + int8_t minmoves, + int8_t maxmoves, + int8_t maxsolutions, + uint8_t h, + const void *data, + char *solutions +) +{ + int64_t nsols; + dfsarg_solveh48_t arg; + + arg = (dfsarg_solveh48_t) { + .cube = cube, + .inverse = inverse(cube), + .nsols = &nsols, + .maxsolutions = maxsolutions, + .h = h, + .cocsepdata = (uint32_t *)data, + .h48data = ((uint32_t *)data) + COCSEP_FULLSIZE / 4, + .nextsol = &solutions + }; + + nsols = 0; + for (arg.depth = minmoves; + arg.depth <= maxmoves && nsols < maxsolutions; + arg.depth++) + { + LOG("Found %" PRId64 " solutions, searching at depth %" + PRId8 "\n", nsols, arg.depth); + arg.nmoves = 0; + solve_h48_dfs(&arg); + } + + return nsols; +} + +/* +The h48stats solver computes how many moves it takes to solve to +each of the 12 h48 coordinates, one for each value of h from 0 to 11. +The solutions array is filled with the length of the solutions. The +solution array is therefore not a printable string. +*/ +_static int64_t +solve_h48stats_dfs(dfsarg_solveh48stats_t *arg) +{ + const int64_t limit = 11; + + int8_t bound, u; + uint8_t m; + uint32_t d; + int64_t coord, h; + dfsarg_solveh48stats_t nextarg; + + /* Check cocsep lower bound (corners only) */ + bound = get_h48_cdata(arg->cube, arg->cocsepdata, &d); + if (bound + arg->nmoves > arg->depth) + return 0; + + /* Check h48 lower bound for h=0 (esep, but no eo) */ + coord = coord_h48_edges(arg->cube, COCLASS(d), TTREP(d), 0); + bound = get_esep_pval(arg->h48data, coord); + if (bound + arg->nmoves > arg->depth) + return 0; + + /* Update all other values, if solved */ + coord = coord_h48_edges(arg->cube, COCLASS(d), TTREP(d), 11); + for (h = 0; h <= limit; h++) { + u = coord >> (11-h) == 0 && arg->s[h] == 99; + arg->s[h] = u * arg->nmoves + (1-u) * arg->s[h]; + } + + if (arg->s[limit] != 99) + return 0; + + nextarg = *arg; + nextarg.nmoves = arg->nmoves + 1; + for (m = 0; m < 18; m++) { + nextarg.moves[arg->nmoves] = m; + if (!allowednextmove(nextarg.moves, nextarg.nmoves)) { + /* If a move is not allowed, neither are its 180 + * and 270 degree variations */ + m += 2; + continue; + } + nextarg.cube = move(arg->cube, m); + solve_h48stats_dfs(&nextarg); + } + + return 0; +} + +_static int64_t +solve_h48stats( + cube_t cube, + int8_t maxmoves, + const void *data, + char solutions[static 12] +) +{ + int i; + size_t cocsepsize; + dfsarg_solveh48stats_t arg; + + cocsepsize = gendata_cocsep(NULL, NULL, NULL); + + arg = (dfsarg_solveh48stats_t) { + .cube = cube, + .cocsepdata = (uint32_t *)data, + .h48data = ((uint32_t *)data) + (cocsepsize/4), + .s = solutions + }; + + for (i = 0; i < 12; i++) + solutions[i] = (char)99; + + for (arg.depth = 0; + arg.depth <= maxmoves && solutions[11] == 99; + arg.depth++) + { + arg.nmoves = 0; + solve_h48stats_dfs(&arg); + } + + return 0; +} diff --git a/src/solvers/solvers.h b/src/solvers/solvers.h new file mode 100644 index 0000000..66c9b27 --- /dev/null +++ b/src/solvers/solvers.h @@ -0,0 +1,2 @@ +#include "generic/generic.h" +#include "h48/h48.h" -- cgit v1.3