From ffb67c9dcd22c4c3258b9ef78301e404e7d9a796 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 5 Oct 2023 15:28:45 +0200 Subject: Split isconsistent() and issolvable() --- README.md | 4 +- src/constants.h | 96 +++++++++++++++++------------------ src/cube.h | 5 +- src/cube_array.c | 102 ++++++++++++++++++++++++-------------- test/00_basic/all.out | 4 +- test/00_basic/basic_tests.c | 2 +- test/01_io/04_inconsistent_ep.in | 1 - test/01_io/04_inconsistent_ep.out | 1 - test/01_io/04_unsolvable_ep.in | 1 + test/01_io/04_unsolvable_ep.out | 1 + test/01_io/05_inconsistent_eo.in | 1 - test/01_io/05_inconsistent_eo.out | 1 - test/01_io/05_unsolvable_eo.in | 1 + test/01_io/05_unsolvable_eo.out | 1 + test/01_io/06_inconsistent_cp.in | 1 - test/01_io/06_inconsistent_cp.out | 1 - test/01_io/06_unsolvable_cp.in | 1 + test/01_io/06_unsolvable_cp.out | 1 + test/01_io/07_inconsistent_co.in | 1 - test/01_io/07_inconsistent_co.out | 1 - test/01_io/07_unsolvable_co.in | 1 + test/01_io/07_unsolvable_co.out | 1 + test/01_io/io_tests.c | 4 +- test/02_move/move_tests.c | 4 +- test/03_inverse/inverse_tests.c | 4 +- test/04_compose/compose_tests.c | 4 +- utils/solved.txt | 1 - 27 files changed, 138 insertions(+), 108 deletions(-) delete mode 100644 test/01_io/04_inconsistent_ep.in delete mode 100644 test/01_io/04_inconsistent_ep.out create mode 100644 test/01_io/04_unsolvable_ep.in create mode 100644 test/01_io/04_unsolvable_ep.out delete mode 100644 test/01_io/05_inconsistent_eo.in delete mode 100644 test/01_io/05_inconsistent_eo.out create mode 100644 test/01_io/05_unsolvable_eo.in create mode 100644 test/01_io/05_unsolvable_eo.out delete mode 100644 test/01_io/06_inconsistent_cp.in delete mode 100644 test/01_io/06_inconsistent_cp.out create mode 100644 test/01_io/06_unsolvable_cp.in create mode 100644 test/01_io/06_unsolvable_cp.out delete mode 100644 test/01_io/07_inconsistent_co.in delete mode 100644 test/01_io/07_inconsistent_co.out create mode 100644 test/01_io/07_unsolvable_co.in create mode 100644 test/01_io/07_unsolvable_co.out diff --git a/README.md b/README.md index 2b8fdb2..0b070a0 100644 --- 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 index 6a7e3f9..b2b1b77 100644 --- 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 index fcc76dc..3319b1e 100644 --- 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 index b0b5e1e..a9b9709 100644 --- 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 index aad167e..892ad22 100644 --- 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 index 8c52941..a3ae0b9 100644 --- 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.in b/test/01_io/04_inconsistent_ep.in deleted file mode 100644 index 8483962..0000000 --- a/test/01_io/04_inconsistent_ep.in +++ /dev/null @@ -1 +0,0 @@ -UB0 UF0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/01_io/04_inconsistent_ep.out b/test/01_io/04_inconsistent_ep.out deleted file mode 100644 index cb70902..0000000 --- a/test/01_io/04_inconsistent_ep.out +++ /dev/null @@ -1 +0,0 @@ -Cube is inconsistent diff --git a/test/01_io/04_unsolvable_ep.in b/test/01_io/04_unsolvable_ep.in new file mode 100644 index 0000000..8483962 --- /dev/null +++ b/test/01_io/04_unsolvable_ep.in @@ -0,0 +1 @@ +UB0 UF0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/01_io/04_unsolvable_ep.out b/test/01_io/04_unsolvable_ep.out new file mode 100644 index 0000000..e35c6e4 --- /dev/null +++ b/test/01_io/04_unsolvable_ep.out @@ -0,0 +1 @@ +Cube is not solvable diff --git a/test/01_io/05_inconsistent_eo.in b/test/01_io/05_inconsistent_eo.in deleted file mode 100644 index a92089d..0000000 --- a/test/01_io/05_inconsistent_eo.in +++ /dev/null @@ -1 +0,0 @@ -UF1 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/01_io/05_inconsistent_eo.out b/test/01_io/05_inconsistent_eo.out deleted file mode 100644 index cb70902..0000000 --- a/test/01_io/05_inconsistent_eo.out +++ /dev/null @@ -1 +0,0 @@ -Cube is inconsistent diff --git a/test/01_io/05_unsolvable_eo.in b/test/01_io/05_unsolvable_eo.in new file mode 100644 index 0000000..a92089d --- /dev/null +++ b/test/01_io/05_unsolvable_eo.in @@ -0,0 +1 @@ +UF1 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/01_io/05_unsolvable_eo.out b/test/01_io/05_unsolvable_eo.out new file mode 100644 index 0000000..e35c6e4 --- /dev/null +++ b/test/01_io/05_unsolvable_eo.out @@ -0,0 +1 @@ +Cube is not solvable diff --git a/test/01_io/06_inconsistent_cp.in b/test/01_io/06_inconsistent_cp.in deleted file mode 100644 index 2085dd5..0000000 --- a/test/01_io/06_inconsistent_cp.in +++ /dev/null @@ -1 +0,0 @@ -UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UBL0 UFR0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/01_io/06_inconsistent_cp.out b/test/01_io/06_inconsistent_cp.out deleted file mode 100644 index cb70902..0000000 --- a/test/01_io/06_inconsistent_cp.out +++ /dev/null @@ -1 +0,0 @@ -Cube is inconsistent diff --git a/test/01_io/06_unsolvable_cp.in b/test/01_io/06_unsolvable_cp.in new file mode 100644 index 0000000..2085dd5 --- /dev/null +++ b/test/01_io/06_unsolvable_cp.in @@ -0,0 +1 @@ +UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UBL0 UFR0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/01_io/06_unsolvable_cp.out b/test/01_io/06_unsolvable_cp.out new file mode 100644 index 0000000..e35c6e4 --- /dev/null +++ b/test/01_io/06_unsolvable_cp.out @@ -0,0 +1 @@ +Cube is not solvable diff --git a/test/01_io/07_inconsistent_co.in b/test/01_io/07_inconsistent_co.in deleted file mode 100644 index abd74e2..0000000 --- a/test/01_io/07_inconsistent_co.in +++ /dev/null @@ -1 +0,0 @@ -UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR1 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/01_io/07_inconsistent_co.out b/test/01_io/07_inconsistent_co.out deleted file mode 100644 index cb70902..0000000 --- a/test/01_io/07_inconsistent_co.out +++ /dev/null @@ -1 +0,0 @@ -Cube is inconsistent diff --git a/test/01_io/07_unsolvable_co.in b/test/01_io/07_unsolvable_co.in new file mode 100644 index 0000000..abd74e2 --- /dev/null +++ b/test/01_io/07_unsolvable_co.in @@ -0,0 +1 @@ +UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR1 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/01_io/07_unsolvable_co.out b/test/01_io/07_unsolvable_co.out new file mode 100644 index 0000000..e35c6e4 --- /dev/null +++ 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 index 42ef9b8..913ec1d 100644 --- 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 index ac25de3..333c8ee 100644 --- 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 index 5fab71a..c8d8d95 100644 --- 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 index ae34f6d..575c2c9 100644 --- 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 index 07cf178..dff224d 100644 --- 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 -- cgit v1.3