From 47a65b676d1de889706517f05659f0bb659782c9 Mon Sep 17 00:00:00 2001 From: enricotenuti Date: Thu, 29 Aug 2024 19:07:48 +0200 Subject: nissbranch ver1 --- src/core/moves.h | 162 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 162 insertions(+) (limited to 'src/core/moves.h') diff --git a/src/core/moves.h b/src/core/moves.h index 7da6405..726a452 100644 --- a/src/core/moves.h +++ b/src/core/moves.h @@ -1,8 +1,23 @@ +/* probably these can be placed in constants file */ +#define NONISS 0x00 +#define NISS 0x01 +#define INVERSEBRANCH 0x03 +#define BRANCH 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 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 +43,40 @@ allowednextmove(uint8_t *moves, uint8_t n) return axis[1] != axis[2] || base[0] != base[2]; } +static uint32_t +disable_moves(uint32_t current_result, uint8_t base_index) +{ + return current_result & ~((1 << base_index) | (1 << (base_index + 1)) | (1 << (base_index + 2))); +} + +_static uint32_t +allowednextmoveH48(uint8_t *moves, uint8_t n, uint32_t h48branch) +{ + uint32_t result = ALLMOVES; + if (h48branch & BRANCH) + 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 >= 9) + result = disable_moves(result, (base1 * 3) - 9); + + 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 +94,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; +} -- cgit v1.3 From 0a45da13ca06f7884872160a6756a04d1eb849c5 Mon Sep 17 00:00:00 2001 From: enricotenuti Date: Thu, 29 Aug 2024 19:28:13 +0200 Subject: constants fix --- src/core/moves.h | 8 ++++---- src/solvers/h48/solve.h | 7 +++---- 2 files changed, 7 insertions(+), 8 deletions(-) (limited to 'src/core/moves.h') diff --git a/src/core/moves.h b/src/core/moves.h index 726a452..b28822a 100644 --- a/src/core/moves.h +++ b/src/core/moves.h @@ -1,8 +1,8 @@ /* probably these can be placed in constants file */ -#define NONISS 0x00 -#define NISS 0x01 +#define NORMAL 0x00 +#define INVERSE 0x01 #define INVERSEBRANCH 0x03 -#define BRANCH 0x02 +#define NORMALBRANCH 0x02 #define ALLMOVES 0x3FFFF #define NOHALFTURNS 0x2DB6D @@ -53,7 +53,7 @@ _static uint32_t allowednextmoveH48(uint8_t *moves, uint8_t n, uint32_t h48branch) { uint32_t result = ALLMOVES; - if (h48branch & BRANCH) + if (h48branch & NORMALBRANCH) result &= NOHALFTURNS; if (n < 1) return result; diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h index 751df8f..ed06a85 100644 --- a/src/solvers/h48/solve.h +++ b/src/solvers/h48/solve.h @@ -66,7 +66,7 @@ solve_h48_stop(dfsarg_solveh48_t *arg) uint32_t data, data_inv; int8_t bound; - arg->nissbranch = NONISS; + arg->nissbranch = NORMAL; bound = get_h48_cdata(arg->cube, arg->cocsepdata, &data); if (bound + arg->nmoves + arg->npremoves > arg->depth) return true; @@ -86,7 +86,7 @@ solve_h48_stop(dfsarg_solveh48_t *arg) if (bound + arg->nmoves + arg->npremoves > arg->depth) return true; if (bound + arg->nmoves + arg->npremoves == arg->depth) - arg->nissbranch = BRANCH; + arg->nissbranch = NORMALBRANCH; return false; } @@ -115,7 +115,7 @@ solve_h48_dfs(dfsarg_solveh48_t *arg) nextarg = *arg; ret = 0; uint32_t allowed; - if(arg->nissbranch & 0x01) { + if(arg->nissbranch & INVERSE) { allowed = allowednextmoveH48(arg->premoves, arg->npremoves, arg->nissbranch); for (m = 0; m < 18; m++) { if(allowed & (1 << m)) { @@ -139,7 +139,6 @@ solve_h48_dfs(dfsarg_solveh48_t *arg) } } - return ret; } -- cgit v1.3 From 754e632241859b224497ee4e0239670d5d90759f Mon Sep 17 00:00:00 2001 From: enricotenuti Date: Fri, 30 Aug 2024 12:03:03 +0200 Subject: allowedH48 tests --- src/core/moves.h | 4 +-- test/082_allowednext_h48/00_empty_U.in | 3 ++ test/082_allowednext_h48/00_empty_U.out | 1 + test/082_allowednext_h48/01_F.in | 4 +++ test/082_allowednext_h48/01_F.out | 1 + test/082_allowednext_h48/02_U2.in | 3 ++ test/082_allowednext_h48/02_U2.out | 1 + test/082_allowednext_h48/03_R_L.in | 5 +++ test/082_allowednext_h48/03_R_L.out | 1 + test/082_allowednext_h48/04_D.in | 3 ++ test/082_allowednext_h48/04_D.out | 1 + test/082_allowednext_h48/05_U_F_B2.in | 5 +++ test/082_allowednext_h48/05_U_F_B2.out | 1 + test/082_allowednext_h48/06_empty_bound.in | 2 ++ test/082_allowednext_h48/06_empty_bound.out | 1 + test/082_allowednext_h48/07_F_bound.in | 3 ++ test/082_allowednext_h48/07_F_bound.out | 1 + test/082_allowednext_h48/08_U_D_bound_inverse.in | 4 +++ test/082_allowednext_h48/08_U_D_bound_inverse.out | 1 + test/082_allowednext_h48/09_R_false_bound.in | 3 ++ test/082_allowednext_h48/09_R_false_bound.out | 1 + test/082_allowednext_h48/allowednext_h48_tests.c | 38 +++++++++++++++++++++++ 22 files changed, 85 insertions(+), 2 deletions(-) create mode 100644 test/082_allowednext_h48/00_empty_U.in create mode 100644 test/082_allowednext_h48/00_empty_U.out create mode 100644 test/082_allowednext_h48/01_F.in create mode 100644 test/082_allowednext_h48/01_F.out create mode 100644 test/082_allowednext_h48/02_U2.in create mode 100644 test/082_allowednext_h48/02_U2.out create mode 100644 test/082_allowednext_h48/03_R_L.in create mode 100644 test/082_allowednext_h48/03_R_L.out create mode 100644 test/082_allowednext_h48/04_D.in create mode 100644 test/082_allowednext_h48/04_D.out create mode 100644 test/082_allowednext_h48/05_U_F_B2.in create mode 100644 test/082_allowednext_h48/05_U_F_B2.out create mode 100644 test/082_allowednext_h48/06_empty_bound.in create mode 100644 test/082_allowednext_h48/06_empty_bound.out create mode 100644 test/082_allowednext_h48/07_F_bound.in create mode 100644 test/082_allowednext_h48/07_F_bound.out create mode 100644 test/082_allowednext_h48/08_U_D_bound_inverse.in create mode 100644 test/082_allowednext_h48/08_U_D_bound_inverse.out create mode 100644 test/082_allowednext_h48/09_R_false_bound.in create mode 100644 test/082_allowednext_h48/09_R_false_bound.out create mode 100644 test/082_allowednext_h48/allowednext_h48_tests.c (limited to 'src/core/moves.h') diff --git a/src/core/moves.h b/src/core/moves.h index b28822a..9753993 100644 --- a/src/core/moves.h +++ b/src/core/moves.h @@ -62,8 +62,8 @@ allowednextmoveH48(uint8_t *moves, uint8_t n, uint32_t h48branch) uint8_t axis1 = moveaxis(moves[n-1]); result = disable_moves(result, base1 * 3); - if (base1 >= 9) - result = disable_moves(result, (base1 * 3) - 9); + if (base1 % 2) + result = disable_moves(result, (base1 - 1) * 3); if (n == 1) return result; diff --git a/test/082_allowednext_h48/00_empty_U.in b/test/082_allowednext_h48/00_empty_U.in new file mode 100644 index 0000000..28271a6 --- /dev/null +++ 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 new file mode 100644 index 0000000..8607955 --- /dev/null +++ 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 new file mode 100644 index 0000000..e7ae375 --- /dev/null +++ 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 new file mode 100644 index 0000000..5d6f843 --- /dev/null +++ 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 new file mode 100644 index 0000000..2c5ee5f --- /dev/null +++ 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 new file mode 100644 index 0000000..a9a5adb --- /dev/null +++ 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 new file mode 100644 index 0000000..b6c0625 --- /dev/null +++ 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 new file mode 100644 index 0000000..a4aa4b2 --- /dev/null +++ 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 new file mode 100644 index 0000000..83da556 --- /dev/null +++ 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 new file mode 100644 index 0000000..fe91843 --- /dev/null +++ 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 new file mode 100644 index 0000000..67e090f --- /dev/null +++ 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 new file mode 100644 index 0000000..5d6f843 --- /dev/null +++ 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 new file mode 100644 index 0000000..389e262 --- /dev/null +++ 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 new file mode 100644 index 0000000..eb601fc --- /dev/null +++ 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 new file mode 100644 index 0000000..b3ae33d --- /dev/null +++ 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 new file mode 100644 index 0000000..0dc8997 --- /dev/null +++ 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 new file mode 100644 index 0000000..707f7e0 --- /dev/null +++ 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 new file mode 100644 index 0000000..6f47cf0 --- /dev/null +++ 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 new file mode 100644 index 0000000..0b1d441 --- /dev/null +++ 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 new file mode 100644 index 0000000..121bfeb --- /dev/null +++ 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 new file mode 100644 index 0000000..4cee695 --- /dev/null +++ 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); +} -- cgit v1.3 From 4abb800c4b4f3a509c07821ade8d34e3699bdf10 Mon Sep 17 00:00:00 2001 From: enricotenuti Date: Fri, 30 Aug 2024 17:47:48 +0200 Subject: format fix --- src/core/moves.h | 7 ++++--- src/solvers/h48/solve.h | 31 +++++++++++++++---------------- 2 files changed, 19 insertions(+), 19 deletions(-) (limited to 'src/core/moves.h') diff --git a/src/core/moves.h b/src/core/moves.h index 9753993..8f9c8f5 100644 --- a/src/core/moves.h +++ b/src/core/moves.h @@ -12,6 +12,7 @@ _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); @@ -43,10 +44,10 @@ allowednextmove(uint8_t *moves, uint8_t n) return axis[1] != axis[2] || base[0] != base[2]; } -static uint32_t +_static_inline uint32_t disable_moves(uint32_t current_result, uint8_t base_index) { - return current_result & ~((1 << base_index) | (1 << (base_index + 1)) | (1 << (base_index + 2))); + return current_result & ~(7 << base_index); } _static uint32_t @@ -144,7 +145,7 @@ move(cube_t c, uint8_t m) _static cube_t premove(cube_t c, uint8_t m) { - switch (m) { + switch (m) { case _move_U: return _premove(U3, c); case _move_U2: diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h index ed06a85..bbe59e5 100644 --- a/src/solvers/h48/solve.h +++ b/src/solvers/h48/solve.h @@ -29,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]); @@ -38,26 +37,26 @@ _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; - char *solution = *arg->nextsol; + int strl; + char *solution = *arg->nextsol; - strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol); - *arg->nextsol += strl; + strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol); + *arg->nextsol += strl; - if (arg->npremoves) { - **arg->nextsol = ' '; - (*arg->nextsol)++; + if (arg->npremoves) { + **arg->nextsol = ' '; + (*arg->nextsol)++; uint8_t* invertedpremoves = invertpremoves(arg->premoves, arg->npremoves); - strl = writemoves(invertedpremoves, arg->npremoves, *arg->nextsol); + strl = writemoves(invertedpremoves, arg->npremoves, *arg->nextsol); free(invertedpremoves); - *arg->nextsol += strl; - } - LOG("Solution found: %s\n", solution); + *arg->nextsol += strl; + } + LOG("Solution found: %s\n", solution); - **arg->nextsol = '\n'; - (*arg->nextsol)++; - (*arg->nsols)++; + **arg->nextsol = '\n'; + (*arg->nextsol)++; + (*arg->nsols)++; } _static_inline bool -- cgit v1.3