From d969dc0ad57d3e1e346df719cf9f2708ee87d2e7 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Wed, 23 Apr 2025 12:26:52 +0200 Subject: Almost added support for wide moves, only solve missing --- src/core/constants.h | 118 ++++++++++++++++++++++++++++++++++++++++----------- src/core/moves.h | 97 +++++++++++++++++++++++++++++++++++++++--- src/core/transform.h | 18 -------- 3 files changed, 185 insertions(+), 48 deletions(-) (limited to 'src') diff --git a/src/core/constants.h b/src/core/constants.h index e8b80ae..6505689 100644 --- a/src/core/constants.h +++ b/src/core/constants.h @@ -580,7 +580,7 @@ STATIC const char *transstr[] = { [TRANS_BLm] = "mirrored BL", }; -static uint8_t inverse_trans_table[] = { +STATIC uint8_t inverse_trans_table[] = { [TRANS_UFr] = TRANS_UFr, [TRANS_UFm] = TRANS_UFm, [TRANS_ULr] = TRANS_URr, @@ -631,7 +631,7 @@ static uint8_t inverse_trans_table[] = { [TRANS_BLm] = TRANS_LDm, }; -static uint8_t trans_move_table[][3] = { +STATIC uint8_t trans_move_table[][3] = { [TRANS_UFr] = { MOVE_U, MOVE_R, MOVE_F }, [TRANS_UFm] = { MOVE_U, MOVE_L, MOVE_F }, [TRANS_ULr] = { MOVE_U, MOVE_F, MOVE_L }, @@ -682,7 +682,7 @@ static uint8_t trans_move_table[][3] = { [TRANS_BLm] = { MOVE_B, MOVE_U, MOVE_R }, }; -static uint8_t orientation_transition_table[][3] = { +STATIC uint8_t orientation_transition_table[][3] = { [ORIENTATION_UF] = { ORIENTATION_FD, ORIENTATION_UR, ORIENTATION_LF }, [ORIENTATION_UR] = { ORIENTATION_RD, ORIENTATION_UB, ORIENTATION_FR }, [ORIENTATION_UB] = { ORIENTATION_BD, ORIENTATION_UL, ORIENTATION_RB }, @@ -709,26 +709,94 @@ static uint8_t orientation_transition_table[][3] = { [ORIENTATION_BL] = { ORIENTATION_LF, ORIENTATION_BD, ORIENTATION_DL }, }; -static struct { - uint8_t moves[3]; - uint8_t rotations[6]; -} equivalent_move_table[] = { - [MOVE_U] = { { MOVE_U, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_U2] = { { MOVE_U2, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_U3] = { { MOVE_U3, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_D] = { { MOVE_D, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_D2] = { { MOVE_D2, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_D3] = { { MOVE_D3, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_R] = { { MOVE_R, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_R2] = { { MOVE_R2, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_R3] = { { MOVE_R3, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_L] = { { MOVE_L, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_L2] = { { MOVE_L2, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_L3] = { { MOVE_L3, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_F] = { { MOVE_F, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_F2] = { { MOVE_F2, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_F3] = { { MOVE_F3, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_B] = { { MOVE_B, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_B2] = { { MOVE_B2, UINT8_MAX }, {UINT8_MAX} }, - [MOVE_B3] = { { MOVE_B3, UINT8_MAX }, {UINT8_MAX} }, +STATIC uint8_t orientation_trans[] = { + [ORIENTATION_UF] = TRANS_UFr, + [ORIENTATION_UR] = TRANS_URr, + [ORIENTATION_UB] = TRANS_UBr, + [ORIENTATION_UL] = TRANS_ULr, + [ORIENTATION_DF] = TRANS_DFr, + [ORIENTATION_DR] = TRANS_DRr, + [ORIENTATION_DB] = TRANS_DBr, + [ORIENTATION_DL] = TRANS_DLr, + [ORIENTATION_RF] = TRANS_RFr, + [ORIENTATION_RD] = TRANS_RDr, + [ORIENTATION_RB] = TRANS_RBr, + [ORIENTATION_RU] = TRANS_RUr, + [ORIENTATION_LF] = TRANS_LFr, + [ORIENTATION_LD] = TRANS_LDr, + [ORIENTATION_LB] = TRANS_LBr, + [ORIENTATION_LU] = TRANS_LUr, + [ORIENTATION_FD] = TRANS_FDr, + [ORIENTATION_FR] = TRANS_FRr, + [ORIENTATION_FU] = TRANS_FUr, + [ORIENTATION_FL] = TRANS_FLr, + [ORIENTATION_BD] = TRANS_BDr, + [ORIENTATION_BR] = TRANS_BRr, + [ORIENTATION_BU] = TRANS_BUr, + [ORIENTATION_BL] = TRANS_BLr, +}; + +typedef struct { + uint8_t move[3]; + uint8_t rotation[4]; +} equivalent_moves_t; + +STATIC equivalent_moves_t equivalent_moves_table[] = { + [MOVE_U] = {{MOVE_U, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_U2] = {{MOVE_U2, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_U3] = {{MOVE_U3, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_D] = {{MOVE_D, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_D2] = {{MOVE_D2, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_D3] = {{MOVE_D3, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_R] = {{MOVE_R, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_R2] = {{MOVE_R2, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_R3] = {{MOVE_R3, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_L] = {{MOVE_L, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_L2] = {{MOVE_L2, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_L3] = {{MOVE_L3, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_F] = {{MOVE_F, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_F2] = {{MOVE_F2, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_F3] = {{MOVE_F3, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_B] = {{MOVE_B, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_B2] = {{MOVE_B2, UINT8_MAX}, {UINT8_MAX}}, + [MOVE_B3] = {{MOVE_B3, UINT8_MAX}, {UINT8_MAX}}, + + [MOVE_Uw] = {{MOVE_D, UINT8_MAX}, {1, UINT8_MAX}}, + [MOVE_Uw2] = {{MOVE_D2, UINT8_MAX}, {1, 1, UINT8_MAX}}, + [MOVE_Uw3] = {{MOVE_D3, UINT8_MAX}, {1, 1, 1, UINT8_MAX}}, + [MOVE_Dw] = {{MOVE_U, UINT8_MAX}, {1, 1, 1, UINT8_MAX}}, + [MOVE_Dw2] = {{MOVE_U2, UINT8_MAX}, {1, 1, UINT8_MAX}}, + [MOVE_Dw3] = {{MOVE_U3, UINT8_MAX}, {1, UINT8_MAX}}, + [MOVE_Rw] = {{MOVE_L, UINT8_MAX}, {0, UINT8_MAX}}, + [MOVE_Rw2] = {{MOVE_L2, UINT8_MAX}, {0, 0, UINT8_MAX}}, + [MOVE_Rw3] = {{MOVE_L3, UINT8_MAX}, {0, 0, 0, UINT8_MAX}}, + [MOVE_Lw] = {{MOVE_R, UINT8_MAX}, {0, 0, 0, UINT8_MAX}}, + [MOVE_Lw2] = {{MOVE_R2, UINT8_MAX}, {0, 0, UINT8_MAX}}, + [MOVE_Lw3] = {{MOVE_R3, UINT8_MAX}, {0, UINT8_MAX}}, + [MOVE_Fw] = {{MOVE_B, UINT8_MAX}, {2, UINT8_MAX}}, + [MOVE_Fw2] = {{MOVE_B2, UINT8_MAX}, {2, 2, UINT8_MAX}}, + [MOVE_Fw3] = {{MOVE_B3, UINT8_MAX}, {2, 2, 2, UINT8_MAX}}, + [MOVE_Bw] = {{MOVE_F, UINT8_MAX}, {2, 2, 2, UINT8_MAX}}, + [MOVE_Bw2] = {{MOVE_F2, UINT8_MAX}, {2, 2, UINT8_MAX}}, + [MOVE_Bw3] = {{MOVE_F3, UINT8_MAX}, {2, UINT8_MAX}}, + + [MOVE_M] = {{MOVE_R, MOVE_L3, UINT8_MAX}, {0, 0, 0, UINT8_MAX}}, + [MOVE_M2] = {{MOVE_R2, MOVE_L2, UINT8_MAX}, {0, 0, UINT8_MAX}}, + [MOVE_M3] = {{MOVE_R3, MOVE_L, UINT8_MAX}, {0, UINT8_MAX}}, + [MOVE_S] = {{MOVE_F3, MOVE_B, UINT8_MAX}, {2, UINT8_MAX}}, + [MOVE_S2] = {{MOVE_F2, MOVE_B2, UINT8_MAX}, {2, 2, UINT8_MAX}}, + [MOVE_S3] = {{MOVE_F, MOVE_B3, UINT8_MAX}, {2, 2, 2, UINT8_MAX}}, + [MOVE_E] = {{MOVE_U, MOVE_D3, UINT8_MAX}, {1, 1, 1, UINT8_MAX}}, + [MOVE_E2] = {{MOVE_U2, MOVE_D2, UINT8_MAX}, {1, 1, UINT8_MAX}}, + [MOVE_E3] = {{MOVE_U3, MOVE_D, UINT8_MAX}, {1, UINT8_MAX}}, + + [MOVE_x] = {{UINT8_MAX}, {0, UINT8_MAX}}, + [MOVE_x2] = {{UINT8_MAX}, {0, 0, UINT8_MAX}}, + [MOVE_x3] = {{UINT8_MAX}, {0, 0, 0, UINT8_MAX}}, + [MOVE_y] = {{UINT8_MAX}, {1, UINT8_MAX}}, + [MOVE_y2] = {{UINT8_MAX}, {1, 1, UINT8_MAX}}, + [MOVE_y3] = {{UINT8_MAX}, {1, 1, 1, UINT8_MAX}}, + [MOVE_z] = {{UINT8_MAX}, {2, UINT8_MAX}}, + [MOVE_z2] = {{UINT8_MAX}, {2, 2, UINT8_MAX}}, + [MOVE_z3] = {{UINT8_MAX}, {2, 2, 2, UINT8_MAX}}, }; diff --git a/src/core/moves.h b/src/core/moves.h index 8ed267d..20544a3 100644 --- a/src/core/moves.h +++ b/src/core/moves.h @@ -14,8 +14,13 @@ 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 uint8_t moveopposite(uint8_t); +STATIC_INLINE uint8_t reorient_move(uint8_t, uint8_t); +STATIC_INLINE uint8_t movefollow(uint8_t); +STATIC uint8_t transform_move(uint8_t, uint8_t); STATIC cube_t move(cube_t, uint8_t); +STATIC oriented_cube_t move_extended(oriented_cube_t, uint8_t); STATIC cube_t premove(cube_t, uint8_t); STATIC uint8_t inverse_move(uint8_t); STATIC void sortparallel_moves(size_t n, uint8_t [n]); @@ -112,14 +117,14 @@ countmoves(const char *buf) { uint8_t m; uint64_t c; + int64_t count; + count = 0; FOREACH_READMOVE(buf, m, c, INT_MAX, NISSY_ERROR_INVALID_MOVES, - {} + count += m <= MOVE_Bw3 ? 1 : (m <= MOVE_E3 ? 2 : 0); ) - (void)m; /* Ignore "variable set but not used" warning */ - - return (int64_t)c; + return count; } STATIC int64_t @@ -188,6 +193,9 @@ movebase(uint8_t move) STATIC_INLINE uint8_t moveaxis(uint8_t move) { + if (move > MOVE_B3) + return UINT8_ERROR; + return move / 6; } @@ -209,6 +217,44 @@ moveopposite(uint8_t move) return movebase(move) == 2 * moveaxis(move) ? move + 3 : move - 3; } +STATIC_INLINE uint8_t +reorient_move(uint8_t m, uint8_t or) +{ + return transform_move(m, orientation_trans[or]); +} + +/* This is currently unused, but it may turn out to be useful at some point */ +STATIC_INLINE uint8_t +movefollow(uint8_t move) +{ + uint8_t b, m; + + if (move <= MOVE_B3) + return move; + + if (move <= MOVE_Bw3) + return move - MOVE_Uw; + + b = UINT8_C(3) * (move / UINT8_C(3)); + m = move - b; + switch (b) { + case MOVE_M: + return MOVE_L + m; + case MOVE_S: + return MOVE_F + m; + case MOVE_E: + return MOVE_D + m; + case MOVE_x: + return MOVE_R + m; + case MOVE_y: + return MOVE_U + m; + case MOVE_z: + return MOVE_F + m; + default: + return UINT8_ERROR; + } +} + STATIC cube_t move(cube_t c, uint8_t m) { @@ -255,6 +301,47 @@ move(cube_t c, uint8_t m) } } +STATIC uint8_t +transform_move(uint8_t m, uint8_t t) +{ + uint8_t a, base, modifier; + + a = moveaxis(m); + if (a == UINT8_ERROR) + return UINT8_ERROR; + + base = trans_move_table[t][a]; + if (movebase(m) != 2 * a) + base = moveopposite(base); + + modifier = m % 3; + if (t >= TRANS_UFm) + modifier = 2 - modifier; + + return base + modifier; +} + +STATIC oriented_cube_t +move_extended(oriented_cube_t c, uint8_t m) +{ + int i; + equivalent_moves_t eqm; + oriented_cube_t ret; + + eqm = equivalent_moves_table[m]; + ret = c; + + for (i = 0; eqm.move[i] != UINT8_MAX; i++) + ret.cube = move( + ret.cube, reorient_move(eqm.move[i], ret.orientation)); + + for (i = 0; eqm.rotation[i] != UINT8_MAX; i++) + ret.orientation = orientation_transition_table[ + ret.orientation][eqm.rotation[i]]; + + return ret; +} + /* Applies the INVERSE of m BEFORE the scramble corresponding to c */ STATIC cube_t premove(cube_t c, uint8_t m) @@ -345,7 +432,7 @@ applymoves(oriented_cube_t cube, const char *buf) "move error: inconsistent cube\n"); FOREACH_READMOVE(buf, m, c, -1, ZERO_ORIENTED_CUBE, - cube.cube = move(cube.cube, m); + cube = move_extended(cube, m); ) return cube; diff --git a/src/core/transform.h b/src/core/transform.h index 763a4ae..d1d2931 100644 --- a/src/core/transform.h +++ b/src/core/transform.h @@ -25,7 +25,6 @@ STATIC cube_t transform_corners(cube_t, uint8_t); STATIC cube_t transform(cube_t, uint8_t); STATIC oriented_cube_t applytrans(oriented_cube_t, const char *); STATIC_INLINE uint8_t inverse_trans(uint8_t); -STATIC uint8_t transform_move(uint8_t, uint8_t); STATIC uint64_t symmetry_mask(cube_t); STATIC uint8_t @@ -392,23 +391,6 @@ inverse_trans(uint8_t t) return inverse_trans_table[t]; } -STATIC uint8_t -transform_move(uint8_t m, uint8_t t) -{ - uint8_t a, base, modifier; - - a = moveaxis(m); - base = trans_move_table[t][a]; - if (movebase(m) != 2 * a) - base = moveopposite(base); - - modifier = m % 3; - if (t >= TRANS_UFm) - modifier = 2 - modifier; - - return base + modifier; -} - STATIC uint64_t symmetry_mask(cube_t cube) { -- cgit v1.3