commit ffb67c9dcd22c4c3258b9ef78301e404e7d9a796 parent 9e698917cb5b332cdbf1969ddfe3840239106c8d Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Thu, 5 Oct 2023 15:28:45 +0200 Split isconsistent() and issolvable() Diffstat:
23 files changed, 134 insertions(+), 104 deletions(-)
diff --git a/README.md b/README.md @@ -4,7 +4,9 @@ Work in progress. TODO: -* transformations +* finish second half of transformations +* implement writecubesrc() to make it easy to implement transformations +* implement transformations * setup benchmarks * coordinates: co, eo, epsep, cpsep_sym, cocpsep_sym, cphtr_sym, cocphtr_sym * pruning tables (1 bit per entry + fallback) diff --git a/src/constants.h b/src/constants.h @@ -19,53 +19,53 @@ #define B3 17U /* Regular transformations (rotations) */ -#define UF_i 0 -#define UL_i 1 -#define UB_i 2 -#define UR_i 3 -#define DF_i 4 -#define DL_i 5 -#define DB_i 6 -#define DR_i 7 -#define RU_i 8 -#define RF_i 9 -#define RD_i 10 -#define RB_i 11 -#define LU_i 12 -#define LF_i 13 -#define LD_i 14 -#define LB_i 15 -#define FU_i 16 -#define FR_i 16 -#define FD_i 18 -#define FL_i 19 -#define BU_i 20 -#define BR_i 21 -#define BD_i 22 -#define BL_i 23 +#define UFr 0 +#define ULr 1 +#define UBr 2 +#define URr 3 +#define DFr 4 +#define DLr 5 +#define DBr 6 +#define DRr 7 +#define RUr 8 +#define RFr 9 +#define RDr 10 +#define RBr 11 +#define LUr 12 +#define LFr 13 +#define LDr 14 +#define LBr 15 +#define FUr 16 +#define FRr 16 +#define FDr 18 +#define FLr 19 +#define BUr 20 +#define BRr 21 +#define BDr 22 +#define BLr 23 /* Mirrored transformations */ -#define UF_m 24 -#define UL_m 25 -#define UB_m 26 -#define UR_m 27 -#define DF_m 28 -#define DL_m 29 -#define DB_m 30 -#define DR_m 31 -#define RU_m 32 -#define RF_m 33 -#define RD_m 34 -#define RB_m 35 -#define LU_m 36 -#define LF_m 37 -#define LD_m 38 -#define LB_m 39 -#define FU_m 40 -#define FR_m 41 -#define FD_m 42 -#define FL_m 43 -#define BU_m 44 -#define BR_m 45 -#define BD_m 46 -#define BL_m 47 +#define UFm 24 +#define ULm 25 +#define UBm 26 +#define URm 27 +#define DFm 28 +#define DLm 29 +#define DBm 30 +#define DRm 31 +#define RUm 32 +#define RFm 33 +#define RDm 34 +#define RBm 35 +#define LUm 36 +#define LFm 37 +#define LDm 38 +#define LBm 39 +#define FUm 40 +#define FRm 41 +#define FDm 42 +#define FLm 43 +#define BUm 44 +#define BRm 45 +#define BDm 46 +#define BLm 47 diff --git a/src/cube.h b/src/cube.h @@ -11,7 +11,10 @@ extern cube_t solvedcube; cube_t readcube(char *); void writecube(cube_t, char *); -bool isconsistent(cube_t); +/* Writes a cube in C source code format */ +void writecubesrc(cube_t, char *); + +bool issolvable(cube_t); bool equal(cube_t, cube_t); bool issolved(cube_t); bool iserror(cube_t); diff --git a/src/cube_array.c b/src/cube_array.c @@ -149,6 +149,7 @@ cube_t solvedcube = { static cube_t errorcube = { .e = {0}, .c = {0} }; +static bool isconsistent(cube_t); static uint8_t readco(char *); static uint8_t readcp(char *); static uint8_t readeo(char *); @@ -402,58 +403,41 @@ permsign(uint8_t *a, int n) return ret % 2; } -bool -isconsistent(cube_t cube) +static bool +isconsistent(cube_t c) { - int8_t p, psum, eosum, co, cosum; + uint8_t i, p, e; bool found[12]; - int i; - psum = 0; for (i = 0; i < 12; i++) found[i] = false; for (i = 0; i < 12; i++) { - p = cube.e[i] & _pbits; + p = c.e[i] & _pbits; + e = c.e[i] & ~_pbits; if (p >= 12) goto inconsistent_ep; + if (e != 0 && e != _eobit) + goto inconsistent_eo; found[p] = true; } for (i = 0; i < 12; i++) if (!found[i]) goto inconsistent_ep; - psum = permsign(cube.e, 12); for (i = 0; i < 8; i++) found[i] = false; for (i = 0; i < 8; i++) { - p = cube.c[i] & _pbits; + p = c.c[i] & _pbits; + e = c.c[i] & ~_pbits; if (p >= 8) goto inconsistent_cp; + if (e != 0 && e != _ctwist_cw && e != _ctwist_ccw) + goto inconsistent_co; found[p] = true; } for (i = 0; i < 8; i++) if (!found[i]) - goto inconsistent_cp; - psum += permsign(cube.c, 8); - - if (psum % 2 != 0) - goto inconsistent_parity; - - eosum = 0; - for (i = 0; i < 12; i++) - eosum += (cube.e[i] & _eobit) >> _eoshift; - if (eosum % 2 != 0) - goto inconsistent_eo; - - cosum = 0; - for (i = 0; i < 8; i++) { - co = (cube.c[i] & _cobits) >> _coshift; - if (co > 2) goto inconsistent_co; - cosum += co; - } - if (cosum % 3 != 0) - goto inconsistent_co; return true; @@ -461,28 +445,70 @@ inconsistent_ep: #ifdef DEBUG fprintf(stderr, "Inconsistent EP\n"); #endif - goto inconsistent_return; + return false; inconsistent_cp: #ifdef DEBUG fprintf(stderr, "Inconsistent CP\n"); #endif - goto inconsistent_return; -inconsistent_parity: -#ifdef DEBUG - fprintf(stderr, "Inconsistent parity\n"); -#endif - goto inconsistent_return; + return false; inconsistent_eo: #ifdef DEBUG fprintf(stderr, "Inconsistent EO\n"); #endif - goto inconsistent_return; + return false; inconsistent_co: #ifdef DEBUG fprintf(stderr, "Inconsistent CO\n"); #endif - goto inconsistent_return; -inconsistent_return: + return false; +} + +bool +issolvable(cube_t cube) +{ + int8_t i, eo, co; + +#ifdef DEBUG + if (!isconsistent(cube)) + goto issolvable_inconsistent; +#endif + + if (permsign(cube.e, 12) != permsign(cube.c, 8)) + goto issolvable_parity; + + eo = 0; + for (i = 0; i < 12; i++) + eo += (cube.e[i] & _eobit) >> _eoshift; + if (eo % 2 != 0) + goto issolvable_eo; + + co = 0; + for (i = 0; i < 8; i++) + co += (cube.c[i] & _cobits) >> _coshift; + if (co % 3 != 0) + goto issolvable_co; + + return true; + +issolvable_inconsistent: +#ifdef DEBUG + fprintf(stderr, "issolvable: cube is inconsistent\n"); +#endif + return false; +issolvable_parity: +#ifdef DEBUG + fprintf(stderr, "EP and CP parities are different\n"); +#endif + return false; +issolvable_eo: +#ifdef DEBUG + fprintf(stderr, "Odd number of flipped edges\n"); +#endif + return false; +issolvable_co: +#ifdef DEBUG + fprintf(stderr, "Sum of corner orientation is not multiple of 3\n"); +#endif return false; } diff --git a/test/00_basic/all.out b/test/00_basic/all.out @@ -1,6 +1,6 @@ -Solved is consistent +Solved is solvable Solved is solved -Zero is NOT consistent +Zero is NOT solvable Zero is NOT solved Solved and Solved are equal Solved and Zero are NOT equal diff --git a/test/00_basic/basic_tests.c b/test/00_basic/basic_tests.c @@ -7,7 +7,7 @@ void check(cube_t cube, char *name) { - printf("%s is%s consistent\n", name, isconsistent(cube) ? "" : " NOT"); + printf("%s is%s solvable\n", name, issolvable(cube) ? "" : " NOT"); printf("%s is%s solved\n", name, issolved(cube) ? "" : " NOT"); } diff --git a/test/01_io/04_inconsistent_ep.out b/test/01_io/04_inconsistent_ep.out @@ -1 +0,0 @@ -Cube is inconsistent diff --git a/test/01_io/04_inconsistent_ep.in b/test/01_io/04_unsolvable_ep.in diff --git a/test/01_io/04_unsolvable_ep.out b/test/01_io/04_unsolvable_ep.out @@ -0,0 +1 @@ +Cube is not solvable diff --git a/test/01_io/05_inconsistent_eo.out b/test/01_io/05_inconsistent_eo.out @@ -1 +0,0 @@ -Cube is inconsistent diff --git a/test/01_io/05_inconsistent_eo.in b/test/01_io/05_unsolvable_eo.in diff --git a/test/01_io/05_unsolvable_eo.out b/test/01_io/05_unsolvable_eo.out @@ -0,0 +1 @@ +Cube is not solvable diff --git a/test/01_io/06_inconsistent_cp.out b/test/01_io/06_inconsistent_cp.out @@ -1 +0,0 @@ -Cube is inconsistent diff --git a/test/01_io/06_inconsistent_cp.in b/test/01_io/06_unsolvable_cp.in diff --git a/test/01_io/06_unsolvable_cp.out b/test/01_io/06_unsolvable_cp.out @@ -0,0 +1 @@ +Cube is not solvable diff --git a/test/01_io/07_inconsistent_co.out b/test/01_io/07_inconsistent_co.out @@ -1 +0,0 @@ -Cube is inconsistent diff --git a/test/01_io/07_inconsistent_co.in b/test/01_io/07_unsolvable_co.in diff --git a/test/01_io/07_unsolvable_co.out b/test/01_io/07_unsolvable_co.out @@ -0,0 +1 @@ +Cube is not solvable diff --git a/test/01_io/io_tests.c b/test/01_io/io_tests.c @@ -17,8 +17,8 @@ int main() { if (iserror(cube)) { printf("Error reading cube\n"); - } else if (!isconsistent(cube)) { - printf("Cube is inconsistent\n"); + } else if (!issolvable(cube)) { + printf("Cube is not solvable\n"); } else { writecube(cube, str); printf("%s\n", str); diff --git a/test/02_move/move_tests.c b/test/02_move/move_tests.c @@ -29,8 +29,8 @@ int main() { if (iserror(cube)) { printf("Error moving cube\n"); - } else if (!isconsistent(cube)) { - printf("Moved cube is inconsistent\n"); + } else if (!issolvable(cube)) { + printf("Moved cube is not solvable\n"); } else { writecube(cube, str); printf("%s\n", str); diff --git a/test/03_inverse/inverse_tests.c b/test/03_inverse/inverse_tests.c @@ -16,8 +16,8 @@ int main() { if (iserror(inv)) { printf("Error inverting cube\n"); - } else if (!isconsistent(inv)) { - printf("Inverted cube is inconsistent\n"); + } else if (!issolvable(inv)) { + printf("Inverted cube is not solvable\n"); } else { writecube(inv, str); printf("%s\n", str); diff --git a/test/04_compose/compose_tests.c b/test/04_compose/compose_tests.c @@ -19,8 +19,8 @@ int main() { if (iserror(c3)) { printf("Error composing cubes\n"); - } else if (!isconsistent(c3)) { - printf("Composed cube is inconsistent\n"); + } else if (!issolvable(c3)) { + printf("Composed cube is not solvable\n"); } else { writecube(c3, str); printf("%s\n", str); diff --git a/utils/solved.txt b/utils/solved.txt @@ -1,2 +1 @@ - UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0