From 0c9a5d0e5c1702d07b24eeac181f78d1689c05cc Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sun, 5 Nov 2023 19:59:45 +0100 Subject: Added coord_eo --- README.md | 48 ++++++++++++++++++++++++++++---------- cube.c | 32 +++++++++++++++++++++++++ cube.h | 2 ++ test/061_coord_eo/00_solved.in | 1 + test/061_coord_eo/00_solved.out | 1 + test/061_coord_eo/01_U.in | 1 + test/061_coord_eo/01_U.out | 1 + test/061_coord_eo/02_U2.in | 1 + test/061_coord_eo/02_U2.out | 1 + test/061_coord_eo/03_U3.in | 1 + test/061_coord_eo/03_U3.out | 1 + test/061_coord_eo/04_D.in | 1 + test/061_coord_eo/04_D.out | 1 + test/061_coord_eo/07_R.in | 1 + test/061_coord_eo/07_R.out | 1 + test/061_coord_eo/08_R2.in | 1 + test/061_coord_eo/08_R2.out | 1 + test/061_coord_eo/10_L.in | 1 + test/061_coord_eo/10_L.out | 1 + test/061_coord_eo/13_F.in | 1 + test/061_coord_eo/13_F.out | 1 + test/061_coord_eo/14_F2.in | 1 + test/061_coord_eo/14_F2.out | 1 + test/061_coord_eo/15_F3.in | 1 + test/061_coord_eo/15_F3.out | 1 + test/061_coord_eo/16_B.in | 1 + test/061_coord_eo/16_B.out | 1 + test/061_coord_eo/17_B2.in | 1 + test/061_coord_eo/17_B2.out | 1 + test/061_coord_eo/18_B3.in | 1 + test/061_coord_eo/18_B3.out | 1 + test/061_coord_eo/20_scrambled.in | 3 +++ test/061_coord_eo/20_scrambled.out | 1 + test/061_coord_eo/coord_eo_tests.c | 22 +++++++++++++++++ 34 files changed, 124 insertions(+), 12 deletions(-) create mode 100644 test/061_coord_eo/00_solved.in create mode 100644 test/061_coord_eo/00_solved.out create mode 100644 test/061_coord_eo/01_U.in create mode 100644 test/061_coord_eo/01_U.out create mode 100644 test/061_coord_eo/02_U2.in create mode 100644 test/061_coord_eo/02_U2.out create mode 100644 test/061_coord_eo/03_U3.in create mode 100644 test/061_coord_eo/03_U3.out create mode 100644 test/061_coord_eo/04_D.in create mode 100644 test/061_coord_eo/04_D.out create mode 100644 test/061_coord_eo/07_R.in create mode 100644 test/061_coord_eo/07_R.out create mode 100644 test/061_coord_eo/08_R2.in create mode 100644 test/061_coord_eo/08_R2.out create mode 100644 test/061_coord_eo/10_L.in create mode 100644 test/061_coord_eo/10_L.out create mode 100644 test/061_coord_eo/13_F.in create mode 100644 test/061_coord_eo/13_F.out create mode 100644 test/061_coord_eo/14_F2.in create mode 100644 test/061_coord_eo/14_F2.out create mode 100644 test/061_coord_eo/15_F3.in create mode 100644 test/061_coord_eo/15_F3.out create mode 100644 test/061_coord_eo/16_B.in create mode 100644 test/061_coord_eo/16_B.out create mode 100644 test/061_coord_eo/17_B2.in create mode 100644 test/061_coord_eo/17_B2.out create mode 100644 test/061_coord_eo/18_B3.in create mode 100644 test/061_coord_eo/18_B3.out create mode 100644 test/061_coord_eo/20_scrambled.in create mode 100644 test/061_coord_eo/20_scrambled.out create mode 100644 test/061_coord_eo/coord_eo_tests.c diff --git a/README.md b/README.md index 4ec5eff..d829af4 100644 --- a/README.md +++ b/README.md @@ -30,30 +30,54 @@ for benchmarks. ## TODO: -### Documentation and interface - -* inline some documentation as comments in cube.h or cube.c -* README.md (maybe convert to txt?) becomes the reference documentation +### Coordinates -### More features +* [done] eo +* co +* ep +* epsep +* cp +* cpsep +* cphtr -* move() that takes a string (alg) as input -* coordinates: co, eo, epsep, cpsep_sym, cocpsep_sym, cphtr_sym, cocphtr_sym +What about symcoord? ### Solving -* Fixed depth -* pruning tables (1 bit per entry + fallback) -* Takes as parameters the amount of memory to use and a FILE for the tables -* Use multi-move (up to 4/5 moves at once) +All solving functions take a cube and some parameters as input. + +* Depth [uint, <= 20]: all solvers work at fixed depth. The caller + implementation can implement an A* search. +* Full [bool]: if false, stop at first solution found, otherwise + find all solutions at that depth. +* Table [uint8_t *]: table with all the necessare pre-computed info. + The table can be generated with a companion function, but reading + from and writing to file is delegated to the caller implementation. + +Implement the following solvers: +* Slow: basic solver without any table. +* H48: one-bit-per-entry table + fallback, 48 symmetries and so on. + See planner. +* nxopt31: mostly for comparison. +* other nxopt solvers: make generic and take the type as parameter. +* Step solver: take a coordinate function and a moveset as a parameter. ### cube.h changes * Consider removing zerocube() from the api * prefix public functions with nissy_ or something similar +* move() that takes a string (alg) as input + +### Documentation and interface -### Future optimizations +* inline some documentation as comments in source code +* README.md (maybe convert to txt?) becomes the reference documentation + +### Optimizations +* Trans: don't do full compose, for some trans composing perm is enough. + Split out sumco() as a separate function and refactor, optimize. +* Use multi-move (up to 4/5 moves at once) * CO is the worst part of moving, transforming and inverting. Try basing everything on representing the cube without CO and apply it only at the end to check that it is actually solved. diff --git a/cube.c b/cube.c index e98bc40..8ca2c72 100644 --- a/cube.c +++ b/cube.c @@ -2104,6 +2104,19 @@ _compose(cube_t c1, cube_t c2) return ret; } +static inline int16_t +_coord_eo(cube_t c) +{ + cube_t eo, shifted; + int mask; + + eo = _mm256_and_si256(c, _eo_avx2); + shifted = _mm256_slli_epi32(eo, 3); + mask = _mm256_movemask_epi8(shifted); + + return (int16_t)(mask >> 17); +} + /****************************************************************************** Section: portable fast methods @@ -3420,6 +3433,19 @@ _compose(cube_t c1, cube_t c2) return ret; } +static inline int16_t +_coord_eo(cube_t c) +{ + int i, p; + int16_t ret; + + ret = 0; + for (i = 1, p = 1; i < 12; i++, p *= 2) + ret += p * (c.e[i] >> 4); + + return ret; +} + #endif @@ -3696,3 +3722,9 @@ transform(cube_t c, trans_t t) return zerocube(); } } + +int16_t +coord_eo(cube_t c) +{ + return _coord_eo(c); +} diff --git a/cube.h b/cube.h index 4bbf28a..5dc7410 100644 --- a/cube.h +++ b/cube.h @@ -31,3 +31,5 @@ cube_t move(cube_t, move_t); cube_t inverse(cube_t); cube_t compose(cube_t, cube_t); cube_t transform(cube_t, trans_t); + +int16_t coord_eo(cube_t); diff --git a/test/061_coord_eo/00_solved.in b/test/061_coord_eo/00_solved.in new file mode 100644 index 0000000..dff224d --- /dev/null +++ b/test/061_coord_eo/00_solved.in @@ -0,0 +1 @@ +UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/061_coord_eo/00_solved.out b/test/061_coord_eo/00_solved.out new file mode 100644 index 0000000..573541a --- /dev/null +++ b/test/061_coord_eo/00_solved.out @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/01_U.in b/test/061_coord_eo/01_U.in new file mode 100644 index 0000000..b5b36ad --- /dev/null +++ b/test/061_coord_eo/01_U.in @@ -0,0 +1 @@ +UR0 UL0 DB0 DF0 UB0 UF0 DL0 DR0 FR0 FL0 BL0 BR0 UBR0 UFL0 DFL0 DBR0 UFR0 UBL0 DFR0 DBL0 diff --git a/test/061_coord_eo/01_U.out b/test/061_coord_eo/01_U.out new file mode 100644 index 0000000..573541a --- /dev/null +++ b/test/061_coord_eo/01_U.out @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/02_U2.in b/test/061_coord_eo/02_U2.in new file mode 100644 index 0000000..316ad57 --- /dev/null +++ b/test/061_coord_eo/02_U2.in @@ -0,0 +1 @@ +UB0 UF0 DB0 DF0 UL0 UR0 DL0 DR0 FR0 FL0 BL0 BR0 UBL0 UFR0 DFL0 DBR0 UBR0 UFL0 DFR0 DBL0 diff --git a/test/061_coord_eo/02_U2.out b/test/061_coord_eo/02_U2.out new file mode 100644 index 0000000..573541a --- /dev/null +++ b/test/061_coord_eo/02_U2.out @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/03_U3.in b/test/061_coord_eo/03_U3.in new file mode 100644 index 0000000..7721ab5 --- /dev/null +++ b/test/061_coord_eo/03_U3.in @@ -0,0 +1 @@ +UL0 UR0 DB0 DF0 UF0 UB0 DL0 DR0 FR0 FL0 BL0 BR0 UFL0 UBR0 DFL0 DBR0 UBL0 UFR0 DFR0 DBL0 diff --git a/test/061_coord_eo/03_U3.out b/test/061_coord_eo/03_U3.out new file mode 100644 index 0000000..573541a --- /dev/null +++ b/test/061_coord_eo/03_U3.out @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/04_D.in b/test/061_coord_eo/04_D.in new file mode 100644 index 0000000..cf4f816 --- /dev/null +++ b/test/061_coord_eo/04_D.in @@ -0,0 +1 @@ +UF0 UB0 DR0 DL0 UR0 UL0 DB0 DF0 FR0 FL0 BL0 BR0 UFR0 UBL0 DBL0 DFR0 UFL0 UBR0 DFL0 DBR0 diff --git a/test/061_coord_eo/04_D.out b/test/061_coord_eo/04_D.out new file mode 100644 index 0000000..573541a --- /dev/null +++ b/test/061_coord_eo/04_D.out @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/07_R.in b/test/061_coord_eo/07_R.in new file mode 100644 index 0000000..8c8fcb3 --- /dev/null +++ b/test/061_coord_eo/07_R.in @@ -0,0 +1 @@ +UF0 UB0 DB0 DF0 FR0 UL0 DL0 BR0 DR0 FL0 BL0 UR0 DFR2 UBL0 DFL0 UBR2 UFL0 UFR1 DBR1 DBL0 diff --git a/test/061_coord_eo/07_R.out b/test/061_coord_eo/07_R.out new file mode 100644 index 0000000..573541a --- /dev/null +++ b/test/061_coord_eo/07_R.out @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/08_R2.in b/test/061_coord_eo/08_R2.in new file mode 100644 index 0000000..90765e2 --- /dev/null +++ b/test/061_coord_eo/08_R2.in @@ -0,0 +1 @@ +UF0 UB0 DB0 DF0 DR0 UL0 DL0 UR0 BR0 FL0 BL0 FR0 DBR0 UBL0 DFL0 UFR0 UFL0 DFR0 UBR0 DBL0 diff --git a/test/061_coord_eo/08_R2.out b/test/061_coord_eo/08_R2.out new file mode 100644 index 0000000..573541a --- /dev/null +++ b/test/061_coord_eo/08_R2.out @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/10_L.in b/test/061_coord_eo/10_L.in new file mode 100644 index 0000000..0b0565c --- /dev/null +++ b/test/061_coord_eo/10_L.in @@ -0,0 +1 @@ +UF0 UB0 DB0 DF0 UR0 BL0 FL0 DR0 FR0 UL0 DL0 BR0 UFR0 DBL2 UFL2 DBR0 UBL1 UBR0 DFR0 DFL1 diff --git a/test/061_coord_eo/10_L.out b/test/061_coord_eo/10_L.out new file mode 100644 index 0000000..573541a --- /dev/null +++ b/test/061_coord_eo/10_L.out @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/13_F.in b/test/061_coord_eo/13_F.in new file mode 100644 index 0000000..e805af8 --- /dev/null +++ b/test/061_coord_eo/13_F.in @@ -0,0 +1 @@ +FL1 UB0 DB0 FR1 UR0 UL0 DL0 DR0 UF1 DF1 BL0 BR0 UFL1 UBL0 DFR1 DBR0 DFL2 UBR0 UFR2 DBL0 diff --git a/test/061_coord_eo/13_F.out b/test/061_coord_eo/13_F.out new file mode 100644 index 0000000..2c60641 --- /dev/null +++ b/test/061_coord_eo/13_F.out @@ -0,0 +1 @@ +388 diff --git a/test/061_coord_eo/14_F2.in b/test/061_coord_eo/14_F2.in new file mode 100644 index 0000000..8aa701f --- /dev/null +++ b/test/061_coord_eo/14_F2.in @@ -0,0 +1 @@ +DF0 UB0 DB0 UF0 UR0 UL0 DL0 DR0 FL0 FR0 BL0 BR0 DFL0 UBL0 UFR0 DBR0 DFR0 UBR0 UFL0 DBL0 diff --git a/test/061_coord_eo/14_F2.out b/test/061_coord_eo/14_F2.out new file mode 100644 index 0000000..573541a --- /dev/null +++ b/test/061_coord_eo/14_F2.out @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/15_F3.in b/test/061_coord_eo/15_F3.in new file mode 100644 index 0000000..40f1260 --- /dev/null +++ b/test/061_coord_eo/15_F3.in @@ -0,0 +1 @@ +FR1 UB0 DB0 FL1 UR0 UL0 DL0 DR0 DF1 UF1 BL0 BR0 DFR1 UBL0 UFL1 DBR0 UFR2 UBR0 DFL2 DBL0 diff --git a/test/061_coord_eo/15_F3.out b/test/061_coord_eo/15_F3.out new file mode 100644 index 0000000..2c60641 --- /dev/null +++ b/test/061_coord_eo/15_F3.out @@ -0,0 +1 @@ +388 diff --git a/test/061_coord_eo/16_B.in b/test/061_coord_eo/16_B.in new file mode 100644 index 0000000..f7fb13c --- /dev/null +++ b/test/061_coord_eo/16_B.in @@ -0,0 +1 @@ +UF0 BR1 BL1 DF0 UR0 UL0 DL0 DR0 FR0 FL0 UB1 DB1 UFR0 UBR1 DFL0 DBL1 UFL0 DBR2 DFR0 UBL2 diff --git a/test/061_coord_eo/16_B.out b/test/061_coord_eo/16_B.out new file mode 100644 index 0000000..1fd9918 --- /dev/null +++ b/test/061_coord_eo/16_B.out @@ -0,0 +1 @@ +1539 diff --git a/test/061_coord_eo/17_B2.in b/test/061_coord_eo/17_B2.in new file mode 100644 index 0000000..9b33e35 --- /dev/null +++ b/test/061_coord_eo/17_B2.in @@ -0,0 +1 @@ +UF0 DB0 UB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BR0 BL0 UFR0 DBR0 DFL0 UBL0 UFL0 DBL0 DFR0 UBR0 diff --git a/test/061_coord_eo/17_B2.out b/test/061_coord_eo/17_B2.out new file mode 100644 index 0000000..573541a --- /dev/null +++ b/test/061_coord_eo/17_B2.out @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/18_B3.in b/test/061_coord_eo/18_B3.in new file mode 100644 index 0000000..1367517 --- /dev/null +++ b/test/061_coord_eo/18_B3.in @@ -0,0 +1 @@ +UF0 BL1 BR1 DF0 UR0 UL0 DL0 DR0 FR0 FL0 DB1 UB1 UFR0 DBL1 DFL0 UBR1 UFL0 UBL2 DFR0 DBR2 diff --git a/test/061_coord_eo/18_B3.out b/test/061_coord_eo/18_B3.out new file mode 100644 index 0000000..1fd9918 --- /dev/null +++ b/test/061_coord_eo/18_B3.out @@ -0,0 +1 @@ +1539 diff --git a/test/061_coord_eo/20_scrambled.in b/test/061_coord_eo/20_scrambled.in new file mode 100644 index 0000000..274d30b --- /dev/null +++ b/test/061_coord_eo/20_scrambled.in @@ -0,0 +1,3 @@ +UL0 BL0 BR1 DL0 FR0 DF0 DB1 DR1 UB0 FL0 UF0 UR1 DFL0 UFR1 DBR1 UBR2 DBL2 DFR0 UFL1 UBL2 + +// Scramble: U R D' L D' F L2 D L F B D2 B' L2 F U2 L2 D2 R2 L2 B' diff --git a/test/061_coord_eo/20_scrambled.out b/test/061_coord_eo/20_scrambled.out new file mode 100644 index 0000000..aa309cc --- /dev/null +++ b/test/061_coord_eo/20_scrambled.out @@ -0,0 +1 @@ +1122 diff --git a/test/061_coord_eo/coord_eo_tests.c b/test/061_coord_eo/coord_eo_tests.c new file mode 100644 index 0000000..3aed352 --- /dev/null +++ b/test/061_coord_eo/coord_eo_tests.c @@ -0,0 +1,22 @@ +#include +#include +#include + +#include "../../cube.h" + +#define STRLENMAX 10000 + +int main() { + char str[STRLENMAX]; + cube_t cube; + int16_t result; + + fgets(str, STRLENMAX, stdin); + cube = readcube(H48, str); + + result = coord_eo(cube); + + printf("%" PRId16 "\n", result); + + return 0; +} -- cgit v1.3