commit ff4bde84872ec0b93f0f097f5a56bd5e7cbb0311 parent eb20084ec94e9043e55a98717128a4ba1e6215cb Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Fri, 30 Aug 2024 17:52:55 +0200 Merge pull request #2 from enricotenuti/master nissbranch ver1 Diffstat:
25 files changed, 304 insertions(+), 70 deletions(-)
diff --git a/.gitignore b/.gitignore @@ -8,6 +8,7 @@ tables/* test/*/runtest test/run test/run.DSYM +run.DSYM test/last.* tools/results .vscode diff --git a/src/core/cube.h b/src/core/cube.h @@ -13,11 +13,13 @@ _static cube_t frommoves(const char *); _static void getcube_fix(int64_t *, int64_t *, int64_t *, int64_t *); _static cube_t getcube(int64_t, int64_t, int64_t, int64_t); -_static cube_t move(cube_t, uint8_t); _static cube_t transform_edges(cube_t, uint8_t); _static cube_t transform_corners(cube_t, uint8_t); _static cube_t transform(cube_t, uint8_t); +/* declared in moves.h */ +_static cube_t move(cube_t, uint8_t); + _static cube_t cubefromarray(uint8_t c[static 8], uint8_t e[static 12]) { @@ -239,52 +241,6 @@ applytrans(cube_t cube, const char *buf) return transform(cube, t); } -_static cube_t -move(cube_t c, uint8_t m) -{ - switch (m) { - case _move_U: - return _move(U, c); - case _move_U2: - return _move(U2, c); - case _move_U3: - return _move(U3, c); - case _move_D: - return _move(D, c); - case _move_D2: - return _move(D2, c); - case _move_D3: - return _move(D3, c); - case _move_R: - return _move(R, c); - case _move_R2: - return _move(R2, c); - case _move_R3: - return _move(R3, c); - case _move_L: - return _move(L, c); - case _move_L2: - return _move(L2, c); - case _move_L3: - return _move(L3, c); - case _move_F: - return _move(F, c); - case _move_F2: - return _move(F2, c); - case _move_F3: - return _move(F3, c); - case _move_B: - return _move(B, c); - case _move_B2: - return _move(B2, c); - case _move_B3: - return _move(B3, c); - default: - LOG("move error, unknown move\n"); - return zero; - } -} - /* TODO transform is now relegated to a separated file because it is too long. It would be nice to make it shorter without loosing performance. diff --git a/src/core/moves.h b/src/core/moves.h @@ -1,7 +1,23 @@ +/* probably these can be placed in constants file */ +#define NORMAL 0x00 +#define INVERSE 0x01 +#define INVERSEBRANCH 0x03 +#define NORMALBRANCH 0x02 +#define ALLMOVES 0x3FFFF +#define NOHALFTURNS 0x2DB6D + _static_inline bool allowednextmove(uint8_t *, uint8_t); +_static uint32_t allowednextmoveH48(uint8_t *, uint8_t, uint32_t); + _static_inline uint8_t inverse_trans(uint8_t); _static_inline uint8_t movebase(uint8_t); _static_inline uint8_t moveaxis(uint8_t); +_static_inline uint32_t disable_moves(uint32_t, uint8_t); + +_static cube_t move(cube_t, uint8_t); +_static cube_t premove(cube_t, uint8_t); +_static uint8_t inverse_move(uint8_t); +_static uint8_t* invertpremoves(uint8_t *, uint8_t); _static bool allowednextmove(uint8_t *moves, uint8_t n) @@ -28,6 +44,40 @@ allowednextmove(uint8_t *moves, uint8_t n) return axis[1] != axis[2] || base[0] != base[2]; } +_static_inline uint32_t +disable_moves(uint32_t current_result, uint8_t base_index) +{ + return current_result & ~(7 << base_index); +} + +_static uint32_t +allowednextmoveH48(uint8_t *moves, uint8_t n, uint32_t h48branch) +{ + uint32_t result = ALLMOVES; + if (h48branch & NORMALBRANCH) + result &= NOHALFTURNS; + if (n < 1) + return result; + + uint8_t base1 = movebase(moves[n-1]); + uint8_t axis1 = moveaxis(moves[n-1]); + + result = disable_moves(result, base1 * 3); + if (base1 % 2) + result = disable_moves(result, (base1 - 1) * 3); + + if (n == 1) + return result; + + uint8_t base2 = movebase(moves[n-2]); + uint8_t axis2 = moveaxis(moves[n-2]); + + if(axis1 == axis2) + result = disable_moves(result, base2 * 3); + + return result; +} + _static_inline uint8_t inverse_trans(uint8_t t) { @@ -45,3 +95,116 @@ moveaxis(uint8_t move) { return move / 6; } + +_static cube_t +move(cube_t c, uint8_t m) +{ + switch (m) { + case _move_U: + return _move(U, c); + case _move_U2: + return _move(U2, c); + case _move_U3: + return _move(U3, c); + case _move_D: + return _move(D, c); + case _move_D2: + return _move(D2, c); + case _move_D3: + return _move(D3, c); + case _move_R: + return _move(R, c); + case _move_R2: + return _move(R2, c); + case _move_R3: + return _move(R3, c); + case _move_L: + return _move(L, c); + case _move_L2: + return _move(L2, c); + case _move_L3: + return _move(L3, c); + case _move_F: + return _move(F, c); + case _move_F2: + return _move(F2, c); + case _move_F3: + return _move(F3, c); + case _move_B: + return _move(B, c); + case _move_B2: + return _move(B2, c); + case _move_B3: + return _move(B3, c); + default: + LOG("move error, unknown move\n"); + return zero; + } +} + +_static cube_t +premove(cube_t c, uint8_t m) +{ + switch (m) { + case _move_U: + return _premove(U3, c); + case _move_U2: + return _premove(U2, c); + case _move_U3: + return _premove(U, c); + case _move_D: + return _premove(D3, c); + case _move_D2: + return _premove(D2, c); + case _move_D3: + return _premove(D, c); + case _move_R: + return _premove(R3, c); + case _move_R2: + return _premove(R2, c); + case _move_R3: + return _premove(R, c); + case _move_L: + return _premove(L3, c); + case _move_L2: + return _premove(L2, c); + case _move_L3: + return _premove(L, c); + case _move_F: + return _premove(F3, c); + case _move_F2: + return _premove(F2, c); + case _move_F3: + return _premove(F, c); + case _move_B: + return _premove(B3, c); + case _move_B2: + return _premove(B2, c); + case _move_B3: + return _premove(B, c); + default: + LOG("move error, unknown move\n"); + return zero; + } +} + +_static uint8_t +inverse_move(uint8_t m) +{ + return m - 2 * (m % 3) + 2; +} + +_static uint8_t* +invertpremoves(uint8_t *moves, uint8_t nmoves) +{ + uint8_t i; + uint8_t *ret = malloc(nmoves * sizeof(uint8_t)); + + for (i = 0; i < nmoves; i++) + ret[i] = inverse_move(moves[i]); + + // invert elements in the array + for (i = 0; i < nmoves / 2; i++) + _swap(ret[i], ret[nmoves - i - 1]); + return ret; +} diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h @@ -11,6 +11,9 @@ typedef struct { uint32_t *cocsepdata; uint32_t *h48data; char **nextsol; + uint8_t nissbranch; + int8_t npremoves; + uint8_t premoves[MAXLEN]; } dfsarg_solveh48_t; typedef struct { @@ -26,8 +29,7 @@ typedef struct { _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, uint8_t, const void *, char *); +_static int64_t solve_h48(cube_t, int8_t, int8_t, int8_t, uint8_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]); @@ -36,10 +38,22 @@ _static void solve_h48_appendsolution(dfsarg_solveh48_t *arg) { int strl; + char *solution = *arg->nextsol; strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol); - LOG("Solution found: %s\n", *arg->nextsol); - *arg->nextsol += strl; + *arg->nextsol += strl; + + if (arg->npremoves) { + **arg->nextsol = ' '; + (*arg->nextsol)++; + + uint8_t* invertedpremoves = invertpremoves(arg->premoves, arg->npremoves); + strl = writemoves(invertedpremoves, arg->npremoves, *arg->nextsol); + free(invertedpremoves); + *arg->nextsol += strl; + } + LOG("Solution found: %s\n", solution); + **arg->nextsol = '\n'; (*arg->nextsol)++; (*arg->nsols)++; @@ -51,24 +65,27 @@ solve_h48_stop(dfsarg_solveh48_t *arg) uint32_t data, data_inv; int8_t bound; + arg->nissbranch = NORMAL; bound = get_h48_cdata(arg->cube, arg->cocsepdata, &data); - if (bound + arg->nmoves > arg->depth) + if (bound + arg->nmoves + arg->npremoves > arg->depth) return true; bound = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv); - if (bound + arg->nmoves > arg->depth) + if (bound + arg->nmoves + arg->npremoves > arg->depth) return true; -/* bound = get_h48_bound(arg->cube, data, arg->h, arg->k, arg->h48data); -LOG("Using pval %" PRId8 "\n", bound); - if (bound + arg->nmoves > arg->depth) + // LOG("Using pval %" PRId8 "\n", bound); + if (bound + arg->nmoves + arg->npremoves > arg->depth) return true; + if (bound + arg->nmoves + arg->npremoves == arg->depth) + arg->nissbranch = INVERSEBRANCH; bound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->k, arg->h48data); - if (bound + arg->nmoves > arg->depth) + if (bound + arg->nmoves + arg->npremoves > arg->depth) return true; -*/ + if (bound + arg->nmoves + arg->npremoves == arg->depth) + arg->nissbranch = NORMALBRANCH; return false; } @@ -87,7 +104,7 @@ solve_h48_dfs(dfsarg_solveh48_t *arg) return 0; if (issolved(arg->cube)) { - if (arg->nmoves != arg->depth) + if (arg->nmoves + arg->npremoves != arg->depth) return 0; solve_h48_appendsolution(arg); return 1; @@ -95,19 +112,30 @@ solve_h48_dfs(dfsarg_solveh48_t *arg) /* 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; + uint32_t allowed; + if(arg->nissbranch & INVERSE) { + allowed = allowednextmoveH48(arg->premoves, arg->npremoves, arg->nissbranch); + for (m = 0; m < 18; m++) { + if(allowed & (1 << m)) { + nextarg.npremoves = arg->npremoves + 1; + nextarg.premoves[arg->npremoves] = m; + nextarg.inverse = move(arg->inverse, m); + nextarg.cube = premove(arg->cube, m); + ret += solve_h48_dfs(&nextarg); + } + } + } else { + allowed = allowednextmoveH48(arg->moves, arg->nmoves, arg->nissbranch); + for (m = 0; m < 18; m++) { + if (allowed & (1 << m)) { + nextarg.nmoves = arg->nmoves + 1; + nextarg.moves[arg->nmoves] = m; + nextarg.cube = move(arg->cube, m); + nextarg.inverse = premove(arg->inverse, m); + ret += solve_h48_dfs(&nextarg); + } } - nextarg.cube = move(arg->cube, m); - nextarg.inverse = inverse(nextarg.cube); /* TODO: use premove */ - ret += solve_h48_dfs(&nextarg); } return ret; @@ -148,6 +176,7 @@ solve_h48( LOG("Found %" PRId64 " solutions, searching at depth %" PRId8 "\n", nsols, arg.depth); arg.nmoves = 0; + arg.npremoves = 0; solve_h48_dfs(&arg); } diff --git a/test/082_allowednext_h48/00_empty_U.in b/test/082_allowednext_h48/00_empty_U.in @@ -0,0 +1,3 @@ +0 +0 + diff --git a/test/082_allowednext_h48/00_empty_U.out b/test/082_allowednext_h48/00_empty_U.out @@ -0,0 +1 @@ +0x3FFFF diff --git a/test/082_allowednext_h48/01_F.in b/test/082_allowednext_h48/01_F.in @@ -0,0 +1,4 @@ +0 +1 +F + diff --git a/test/082_allowednext_h48/01_F.out b/test/082_allowednext_h48/01_F.out @@ -0,0 +1 @@ +0x38FFF diff --git a/test/082_allowednext_h48/02_U2.in b/test/082_allowednext_h48/02_U2.in @@ -0,0 +1,3 @@ +0 +1 +U diff --git a/test/082_allowednext_h48/02_U2.out b/test/082_allowednext_h48/02_U2.out @@ -0,0 +1 @@ +0x3FFF8 diff --git a/test/082_allowednext_h48/03_R_L.in b/test/082_allowednext_h48/03_R_L.in @@ -0,0 +1,5 @@ +0 +2 +R +L' + diff --git a/test/082_allowednext_h48/03_R_L.out b/test/082_allowednext_h48/03_R_L.out @@ -0,0 +1 @@ +0x3F03F diff --git a/test/082_allowednext_h48/04_D.in b/test/082_allowednext_h48/04_D.in @@ -0,0 +1,3 @@ +0 +1 +D diff --git a/test/082_allowednext_h48/04_D.out b/test/082_allowednext_h48/04_D.out @@ -0,0 +1 @@ +0x3FFC0 diff --git a/test/082_allowednext_h48/05_U_F_B2.in b/test/082_allowednext_h48/05_U_F_B2.in @@ -0,0 +1,5 @@ +0 +2 +U +F + diff --git a/test/082_allowednext_h48/05_U_F_B2.out b/test/082_allowednext_h48/05_U_F_B2.out @@ -0,0 +1 @@ +0x38FFF diff --git a/test/082_allowednext_h48/06_empty_bound.in b/test/082_allowednext_h48/06_empty_bound.in @@ -0,0 +1,2 @@ +2 +0 diff --git a/test/082_allowednext_h48/06_empty_bound.out b/test/082_allowednext_h48/06_empty_bound.out @@ -0,0 +1 @@ +0x2DB6D diff --git a/test/082_allowednext_h48/07_F_bound.in b/test/082_allowednext_h48/07_F_bound.in @@ -0,0 +1,3 @@ +2 +1 +F diff --git a/test/082_allowednext_h48/07_F_bound.out b/test/082_allowednext_h48/07_F_bound.out @@ -0,0 +1 @@ +0x28B6D diff --git a/test/082_allowednext_h48/08_U_D_bound_inverse.in b/test/082_allowednext_h48/08_U_D_bound_inverse.in @@ -0,0 +1,4 @@ +3 +2 +U +D2 +\ No newline at end of file diff --git a/test/082_allowednext_h48/08_U_D_bound_inverse.out b/test/082_allowednext_h48/08_U_D_bound_inverse.out @@ -0,0 +1 @@ +0x2DB40 diff --git a/test/082_allowednext_h48/09_R_false_bound.in b/test/082_allowednext_h48/09_R_false_bound.in @@ -0,0 +1,3 @@ +1 +1 +R +\ No newline at end of file diff --git a/test/082_allowednext_h48/09_R_false_bound.out b/test/082_allowednext_h48/09_R_false_bound.out @@ -0,0 +1 @@ +0x3FE3F diff --git a/test/082_allowednext_h48/allowednext_h48_tests.c b/test/082_allowednext_h48/allowednext_h48_tests.c @@ -0,0 +1,38 @@ +#include "../test.h" + +uint32_t allowednextmoveH48(uint8_t *, uint8_t, uint32_t); + +static char *moves[] = { + "U", "U2", "U'", + "D", "D2", "D'", + "R", "R2", "R'", + "L", "L2", "L'", + "F", "F2", "F'", + "B", "B2", "B'", +}; + +void run(void) { + char movestr[STRLENMAX]; + uint8_t m[100]; + int n, i, j, bound; + + fgets(movestr, STRLENMAX, stdin); + bound = atoi(movestr); + + fgets(movestr, STRLENMAX, stdin); + n = atoi(movestr); + + for (i = 0; i < n; i++) { + fgets(movestr, STRLENMAX, stdin); + movestr[strcspn(movestr, "\n")] = 0; + for (j = 0; j < 18; j++) + if (!strcmp(movestr, moves[j])) + m[i] = j; + } + + fprintf(stderr, "Last two: %s, %s\n", + n > 1 ? moves[m[n-2]] : "-", + n > 0 ? moves[m[n-1]] : "-"); + uint32_t allowed = allowednextmoveH48(m, n, bound); + printf("0x%05X\n", allowed); +}