commit b0053277e385bee23336d1fe6b69a12f49f9172f parent b6c1ff6cfdfe0f4ce602fe83e54c3112a1c95690 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue, 1 Apr 2025 09:33:26 +0200 simplified allowedmoves logic Diffstat:
27 files changed, 116 insertions(+), 114 deletions(-)
diff --git a/src/core/moves.h b/src/core/moves.h @@ -1,15 +1,13 @@ #define MOVE(M, c) compose(c, MOVE_CUBE_ ## M) #define PREMOVE(M, c) compose(MOVE_CUBE_ ## M, c) -STATIC_INLINE bool allowednextmove(size_t n, const uint8_t [n]); -STATIC_INLINE uint32_t allowednextmove_mask(size_t n, const uint8_t [n]); +STATIC_INLINE bool allowednextmove(uint8_t, uint8_t); STATIC bool allowedmoves(size_t n, const uint8_t [n]); STATIC_INLINE uint8_t movebase(uint8_t); STATIC_INLINE uint8_t moveaxis(uint8_t); STATIC_INLINE bool isbase(uint8_t); STATIC_INLINE bool parallel(uint8_t, 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); @@ -38,60 +36,24 @@ STATIC cube_t applymoves(cube_t, const char *); ARG_ACTION \ } -STATIC bool -allowednextmove(size_t n, const uint8_t moves[n]) +STATIC_INLINE bool +allowednextmove(uint8_t m1, uint8_t m2) { - return n == 0 || allowednextmove_mask(n-1, moves) & (1 << moves[n-1]); -} - -STATIC uint32_t -allowednextmove_mask(size_t n, const uint8_t moves[n]) -{ - uint32_t result; - uint8_t base1, base2, axis1, axis2; - - result = MM_ALLMOVES; - - if (n == 0) - return result; - - base1 = movebase(moves[n-1]); - 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; - - base2 = movebase(moves[n-2]); - axis2 = moveaxis(moves[n-2]); - - if(axis1 == axis2) - result = disable_moves(result, base2 * 3); - - return result; + return allowedmask[movebase(m1)] & (UINT32_C(1) << m2); } STATIC bool -allowedmoves(size_t n, const uint8_t moves[n]) +allowedmoves(size_t n, const uint8_t m[n]) { uint8_t j; - for (j = 2; j < n; j++) - if (!allowednextmove(j, moves)) + for (j = 1; j < n; j++) + if (!allowednextmove(m[j-1], m[j])) return false; return true; } -STATIC_INLINE uint32_t -disable_moves(uint32_t current_result, uint8_t base_index) -{ - return current_result & ~MM_SIDE(base_index); -} - STATIC_INLINE uint8_t movebase(uint8_t move) { diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h @@ -135,7 +135,12 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1]) ret = 0; if (coord_continue_onnormal(arg)) { l = arg->solution_moves->nmoves; - mm = allowednextmove_mask(l, arg->solution_moves->moves); + if (l == 0) { + mm = MM_ALLMOVES; + } else { + m = arg->solution_moves->moves[l-1]; + mm = allowedmask[movebase(m)]; + } arg->solution_moves->nmoves++; arg->lastisnormal = true; @@ -160,7 +165,12 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1]) if (coord_continue_oninverse(arg)) { l = arg->solution_moves->npremoves; - mm = allowednextmove_mask(l, arg->solution_moves->premoves); + if (l == 0) { + mm = MM_ALLMOVES; + } else { + m = arg->solution_moves->premoves[l-1]; + mm = allowedmask[movebase(m)]; + } arg->solution_moves->npremoves++; arg->lastisnormal = false; diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h @@ -526,7 +526,7 @@ gendata_h48k2_dfs(h48k2_dfs_arg_t arg[static 1]) /* Depth d+3 */ for (m[2] = 0; m[2] < 18; m[2]++) { markarg.depth = d+3; - if (!allowednextmove(3, m)) { + if (!allowednextmove(m[1], m[2])) { m[2] += 2; continue; } @@ -541,7 +541,7 @@ gendata_h48k2_dfs(h48k2_dfs_arg_t arg[static 1]) /* Depth d+4 */ for (m[3] = 0; m[3] < 18; m[3]++) { markarg.depth = d+4; - if (!allowednextmove(4, m)) { + if (!allowednextmove(m[2], m[3])) { m[3] += 2; continue; } diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h @@ -176,10 +176,16 @@ solve_h48_dfs(dfsarg_solve_h48_t arg[static 1]) ulbi = arg->use_lb_inverse; ret = 0; - mm_normal = allowednextmove_mask(arg->solution_moves->nmoves, - arg->solution_moves->moves) & arg->movemask_normal; - mm_inverse = allowednextmove_mask(arg->solution_moves->npremoves, - arg->solution_moves->premoves) & arg->movemask_inverse; + mm_normal = arg->movemask_normal; + if (arg->solution_moves->nmoves > 0) { + m = arg->solution_moves->moves[arg->solution_moves->nmoves-1]; + mm_normal &= allowedmask[movebase(m)]; + } + mm_inverse = arg->movemask_inverse; + if (arg->solution_moves->npremoves > 0) { + m = arg->solution_moves->premoves[arg->solution_moves->npremoves-1]; + mm_inverse &= allowedmask[movebase(m)]; + } if (popcount_u32(mm_normal) <= popcount_u32(mm_inverse)) { arg->solution_moves->nmoves++; for (m = 0; m < 18; m++) { @@ -299,7 +305,12 @@ solve_h48_maketasks( return NISSY_OK; } - mm = allowednextmove_mask(maketasks_arg->nmoves, maketasks_arg->moves); + if (maketasks_arg->nmoves == 0) { + mm = MM_ALLMOVES; + } else { + m = maketasks_arg->moves[maketasks_arg->nmoves-1]; + mm = allowedmask[movebase(m)]; + } maketasks_arg->nmoves++; backup_cube = maketasks_arg->cube; diff --git a/src/solvers/solutions.h b/src/solvers/solutions.h @@ -128,7 +128,7 @@ appendsolution( /* This is a bit ugly: we have to sort now and then again - later, because the allowednext check would fail with + later, because the allowedmoves check would fail with improperly sorted parallel moves, but then transforming could swap the pairs the wrong way around. TODO: maybe fix this diff --git a/src/utils/constants.h b/src/utils/constants.h @@ -102,7 +102,17 @@ STATIC int64_t binomial[12][12] = { #define MM_ALLMOVES UINT32_C(0x3FFFF) #define MM_NOHALFTURNS UINT32_C(0x2DB6D) -#define MM_SIDE(m) (UINT32_C(7) << (uint32_t)(m)) +#define MM_SINGLE(m) (UINT32_C(1) << (uint32_t)(m)) +#define MM_FACE(m) (UINT32_C(7) << (uint32_t)(m)) +#define MM_EO (\ + MM_FACE(MOVE_U) | MM_FACE(MOVE_D) |\ + MM_FACE(MOVE_R) | MM_FACE(MOVE_L) |\ + MM_SINGLE(MOVE_F2) | MM_SINGLE(MOVE_B2)) +#define MM_DR (\ + MM_FACE(MOVE_U) | MM_FACE(MOVE_D) |\ + MM_SINGLE(MOVE_R2) | MM_SINGLE(MOVE_L2) |\ + MM_SINGLE(MOVE_F2) | MM_SINGLE(MOVE_B2)) +#define MM_HTR (MM_ALLMOVES & ~MM_NOHALFTURNS) #define TM_ALLTRANS UINT64_C(0xFFFFFFFFFFFF) #define TM_SINGLE(t) (UINT64_C(1) << (uint64_t)(t)) @@ -151,6 +161,15 @@ STATIC int64_t binomial[12][12] = { #define EFLIP UINT8_C(0x10) #define UINT8_ERROR UINT8_MAX +STATIC const uint32_t allowedmask[] = { + UINT32_C(0x3FFF8), + UINT32_C(0x3FFC0), + UINT32_C(0x3FE3F), + UINT32_C(0x3F03F), + UINT32_C(0x38FFF), + UINT32_C(0x00FFF) +}; + STATIC const char *cornerstr[] = { [CORNER_UFR] = "UFR", [CORNER_UBL] = "UBL", diff --git a/test/080_allowedmoves/00_empty.in b/test/080_allowedmoves/00_empty.in @@ -0,0 +1 @@ +0 diff --git a/test/080_allowednext/00_empty_U.out b/test/080_allowedmoves/00_empty.out diff --git a/test/080_allowedmoves/01_onemove.in b/test/080_allowedmoves/01_onemove.in @@ -0,0 +1,2 @@ +1 +B' diff --git a/test/080_allowednext/02_U_F.out b/test/080_allowedmoves/01_onemove.out diff --git a/test/080_allowednext/01_F_F2.in b/test/080_allowedmoves/02_F_F2.in diff --git a/test/080_allowednext/01_F_F2.out b/test/080_allowedmoves/02_F_F2.out diff --git a/test/080_allowednext/02_U_F.in b/test/080_allowedmoves/03_U_F.in diff --git a/test/080_allowednext/04_longer_true.out b/test/080_allowedmoves/03_U_F.out diff --git a/test/080_allowednext/03_R_L_R.in b/test/080_allowedmoves/04_R_L_R.in diff --git a/test/080_allowednext/03_R_L_R.out b/test/080_allowedmoves/04_R_L_R.out diff --git a/test/080_allowedmoves/05_longer_true.in b/test/080_allowedmoves/05_longer_true.in @@ -0,0 +1,12 @@ +11 +F2 +B +U +D' +R +L2 +F +U' +D +F +L diff --git a/test/080_allowednext/00_empty_U.out b/test/080_allowedmoves/05_longer_true.out diff --git a/test/080_allowedmoves/06_longer_false.in b/test/080_allowedmoves/06_longer_false.in @@ -0,0 +1,12 @@ +8 +D +F' +B2 +L' +F' +R' +L2 +R +B +U2 +D diff --git a/test/080_allowednext/05_longer_false.out b/test/080_allowedmoves/06_longer_false.out diff --git a/test/080_allowednext/06_D_U_false_order.in b/test/080_allowedmoves/07_D_U_false_order.in diff --git a/test/080_allowednext/06_D_U_false_order.out b/test/080_allowedmoves/07_D_U_false_order.out diff --git a/test/080_allowedmoves/allowedmoves_tests.c b/test/080_allowedmoves/allowedmoves_tests.c @@ -0,0 +1,31 @@ +#include "../test.h" + +bool allowedmoves(size_t n, const uint8_t [n]); + +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; + + 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; + } + + printf("%s\n", allowedmoves(n, m) ? "true" : "false"); +} diff --git a/test/080_allowednext/00_empty_U.in b/test/080_allowednext/00_empty_U.in @@ -1,2 +0,0 @@ -0 -U diff --git a/test/080_allowednext/04_longer_true.in b/test/080_allowednext/04_longer_true.in @@ -1,12 +0,0 @@ -11 -F2 -B -D2 -D' -L -R2 -U -U' -D -F -L diff --git a/test/080_allowednext/05_longer_false.in b/test/080_allowednext/05_longer_false.in @@ -1,9 +0,0 @@ -8 -D -B2 -F' -L' -F' -L' -R2 -L diff --git a/test/080_allowednext/allowednext_tests.c b/test/080_allowednext/allowednext_tests.c @@ -1,35 +0,0 @@ -#include "../test.h" - -bool allowednextmove(size_t n, const uint8_t [n]); - -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; - - 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\nNext: %s\n", - n > 2 ? moves[m[n-3]] : "-", - n > 1 ? moves[m[n-2]] : "-", - n > 0 ? moves[m[n-1]] : "-"); - printf("%s\n", allowednextmove(n, m) ? "true" : "false"); -}