commit 0c9a5d0e5c1702d07b24eeac181f78d1689c05cc parent 1964938ca6abef6e5c81d9dccdf42c55abacb5e9 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Sun, 5 Nov 2023 19:59:45 +0100 Added coord_eo Diffstat:
34 files changed, 124 insertions(+), 12 deletions(-)
diff --git 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 @@ -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 @@ -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 @@ -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 @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/01_U.in 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 @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/02_U2.in 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 @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/03_U3.in 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 @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/04_D.in 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 @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/07_R.in 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 @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/08_R2.in 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 @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/10_L.in 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 @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/13_F.in 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 @@ -0,0 +1 @@ +388 diff --git a/test/061_coord_eo/14_F2.in 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 @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/15_F3.in 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 @@ -0,0 +1 @@ +388 diff --git a/test/061_coord_eo/16_B.in 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 @@ -0,0 +1 @@ +1539 diff --git a/test/061_coord_eo/17_B2.in 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 @@ -0,0 +1 @@ +0 diff --git a/test/061_coord_eo/18_B3.in 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 @@ -0,0 +1 @@ +1539 diff --git a/test/061_coord_eo/20_scrambled.in 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 @@ -0,0 +1 @@ +1122 diff --git a/test/061_coord_eo/coord_eo_tests.c b/test/061_coord_eo/coord_eo_tests.c @@ -0,0 +1,22 @@ +#include <stdbool.h> +#include <inttypes.h> +#include <stdio.h> + +#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; +}