commit c14e780551c4e7aa88d99b226b12f7cdd7b92527
parent ec564e62dcfe701b5ee3111b92c7d72ffd0dda6c
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Sat, 30 Mar 2024 18:40:02 +0100
Added cocsep data generation, but it is very slow
Diffstat:
9 files changed, 243 insertions(+), 23 deletions(-)
diff --git a/TODO.txt b/TODO.txt
@@ -1,8 +1,11 @@
-## (find better name) H48 solver, ideas
-
-TODO implement lookup tables
+TODO optimize cocsep generation (very slow!)
+TODO cocsep data: fix
+TODO cocsep data: add hash checks?
+TODO implement big pruning table for H48 solver
TODO alternative: ARM NEON part
+## H48 optimal solver
+
First compute co + csep. Use csep as a binary number (2^7 instead of 70,
loose a factor of 1.8 but still fits in a few megabytes or less). Use
co + csep as an index in a table whose entries have: 6 bits for ttrep,
diff --git a/cube.c b/cube.c
@@ -28,7 +28,33 @@
#endif
/******************************************************************************
-Section: constants, strings and other stuff
+Section: mathematical constants
+******************************************************************************/
+
+#define _2p11 2048U
+#define _2p12 4096U
+#define _3p7 2187U
+#define _3p8 6561U
+#define _12c4 495U
+#define _8c4 70U
+
+_static int64_t binomial[12][12] = {
+ {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {1, 3, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0},
+ {1, 4, 6, 4, 1, 0, 0, 0, 0, 0, 0, 0},
+ {1, 5, 10, 10, 5, 1, 0, 0, 0, 0, 0, 0},
+ {1, 6, 15, 20, 15, 6, 1, 0, 0, 0, 0, 0},
+ {1, 7, 21, 35, 35, 21, 7, 1, 0, 0, 0, 0},
+ {1, 8, 28, 56, 70, 56, 28, 8, 1, 0, 0, 0},
+ {1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 0, 0},
+ {1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 0},
+ {1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1},
+};
+
+/******************************************************************************
+Section: moves definitions and tables
******************************************************************************/
#define U 0U
@@ -378,7 +404,7 @@ _static cube_t solved = {
#define _trans_cube_BLm_inverse fastcube( \
38, 37, 39, 36, 67, 64, 66, 65, 23, 20, 21, 22, 24, 27, 26, 25, 3, 2, 1, 0)
-static char *cornerstr[] = {
+_static char *cornerstr[] = {
[_c_ufr] = "UFR",
[_c_ubl] = "UBL",
[_c_dfl] = "DFL",
@@ -389,7 +415,7 @@ static char *cornerstr[] = {
[_c_dbl] = "DBL"
};
-static char *cornerstralt[] = {
+_static char *cornerstralt[] = {
[_c_ufr] = "URF",
[_c_ubl] = "ULB",
[_c_dfl] = "DLF",
@@ -400,7 +426,7 @@ static char *cornerstralt[] = {
[_c_dbl] = "DLB"
};
-static char *edgestr[] = {
+_static char *edgestr[] = {
[_e_uf] = "UF",
[_e_ub] = "UB",
[_e_db] = "DB",
@@ -415,7 +441,7 @@ static char *edgestr[] = {
[_e_br] = "BR"
};
-static char *movestr[] = {
+_static char *movestr[] = {
[U] = "U",
[U2] = "U2",
[U3] = "U'",
@@ -436,7 +462,7 @@ static char *movestr[] = {
[B3] = "B'",
};
-static char *transstr[] = {
+_static char *transstr[] = {
[UFr] = "rotation UF",
[UFm] = "mirrored UF",
[ULr] = "rotation UL",
@@ -487,19 +513,55 @@ static char *transstr[] = {
[BLm] = "mirrored BL",
};
-static int64_t binomial[12][12] = {
- {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
- {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
- {1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
- {1, 3, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0},
- {1, 4, 6, 4, 1, 0, 0, 0, 0, 0, 0, 0},
- {1, 5, 10, 10, 5, 1, 0, 0, 0, 0, 0, 0},
- {1, 6, 15, 20, 15, 6, 1, 0, 0, 0, 0, 0},
- {1, 7, 21, 35, 35, 21, 7, 1, 0, 0, 0, 0},
- {1, 8, 28, 56, 70, 56, 28, 8, 1, 0, 0, 0},
- {1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 0, 0},
- {1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 0},
- {1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1},
+static uint8_t inverse_trans_table[48] = {
+ [UFr] = UFr,
+ [UFm] = UFm,
+ [ULr] = URr,
+ [ULm] = ULm,
+ [UBr] = UBr,
+ [UBm] = UBm,
+ [URr] = ULr,
+ [URm] = URm,
+ [DFr] = DFr,
+ [DFm] = DFm,
+ [DLr] = DLr,
+ [DLm] = DRm,
+ [DBr] = DBr,
+ [DBm] = DBm,
+ [DRr] = DRr,
+ [DRm] = DLm,
+ [RUr] = FRr,
+ [RUm] = FLm,
+ [RFr] = LFr,
+ [RFm] = RFm,
+ [RDr] = BLr,
+ [RDm] = BRm,
+ [RBr] = RBr,
+ [RBm] = LBm,
+ [LUr] = FLr,
+ [LUm] = FRm,
+ [LFr] = RFr,
+ [LFm] = LFm,
+ [LDr] = BRr,
+ [LDm] = BLm,
+ [LBr] = LBr,
+ [LBm] = RBm,
+ [FUr] = FUr,
+ [FUm] = FUm,
+ [FRr] = RUr,
+ [FRm] = LUm,
+ [FDr] = BUr,
+ [FDm] = BUm,
+ [FLr] = LUr,
+ [FLm] = RUm,
+ [BUr] = FDr,
+ [BUm] = FDm,
+ [BRr] = LDr,
+ [BRm] = RDm,
+ [BDr] = BDr,
+ [BDm] = BDm,
+ [BLr] = RDr,
+ [BLm] = LDm,
};
/******************************************************************************
@@ -536,6 +598,7 @@ _static_inline cube_fast_t compose_fast(cube_fast_t, cube_fast_t);
_static_inline int64_t coord_fast_co(cube_fast_t);
_static_inline int64_t coord_fast_csep(cube_fast_t);
+_static_inline int64_t coord_fast_cocsep(cube_fast_t);
_static_inline int64_t coord_fast_eo(cube_fast_t);
_static_inline int64_t coord_fast_esep(cube_fast_t);
@@ -694,6 +757,12 @@ coord_fast_csep(cube_fast_t c)
}
_static_inline int64_t
+coord_fast_cocsep(cube_fast_t c)
+{
+ return (coord_fast_co(c) << 7) + coord_fast_csep(c);
+}
+
+_static_inline int64_t
coord_fast_eo(cube_fast_t c)
{
cube_fast_t eo, shifted;
@@ -779,6 +848,7 @@ _static_inline cube_fast_t compose_fast(cube_fast_t, cube_fast_t);
_static_inline int64_t coord_fast_co(cube_fast_t);
_static_inline int64_t coord_fast_csep(cube_fast_t);
+_static_inline int64_t coord_fast_cocsep(cube_fast_t);
_static_inline int64_t coord_fast_eo(cube_fast_t);
_static_inline int64_t coord_fast_esep(cube_fast_t);
@@ -934,6 +1004,12 @@ coord_fast_csep(cube_fast_t c)
}
_static_inline int64_t
+coord_fast_cocsep(cube_fast_t c)
+{
+ return (coord_fast_co(c) << 7) + coord_fast_csep(c);
+}
+
+_static_inline int64_t
coord_fast_eo(cube_fast_t c)
{
int i, p;
@@ -1734,16 +1810,23 @@ transform(cube_fast_t c, uint8_t t)
}
/******************************************************************************
-Section: moves and move sequences
+Section: moves, move sequences and transformations
This section contains methods to work with moves and arrays of moves. They
do not rely on the cube structure.
******************************************************************************/
+_static_inline uint8_t inverse_trans(uint8_t);
_static_inline uint8_t movebase(uint8_t);
_static_inline uint8_t moveaxis(uint8_t);
_static_inline uint8_t
+inverse_trans(uint8_t t)
+{
+ return inverse_trans_table[t];
+}
+
+_static_inline uint8_t
movebase(uint8_t move)
{
return move / 3;
@@ -1759,7 +1842,87 @@ moveaxis(uint8_t move)
Section: auxiliary procedures for H48 optimal solver (temporary)
******************************************************************************/
+_static size_t gendata_cocsep(void *);
+_static uint16_t dfs_cocsep(cube_fast_t, uint8_t, uint8_t, uint16_t *, uint32_t *);
+
+/*
+Each element of the cocsep table is a uint32_t used as follows:
+ - Lowest 8-bit block: pruning value
+ - Second-lower 8-bit block: "ttrep" (transformation to representative)
+ - Top 16-bit block: symcoord value
+*/
+_static size_t
+gendata_cocsep(void *buf)
+{
+ uint32_t *buf32;
+ uint16_t n, cc;
+ uint8_t i, j;
+ size_t tablesize;
+
+ tablesize = _3p7 << 7U;
+
+ buf32 = (uint32_t *)buf;
+ memset(buf32, 0xFFU, 4*tablesize);
+ memset(buf32 + tablesize, 0, 21*4);
+
+ for (i = 0, n = 0, cc = 0; cc != 0 || i == 0; i++) {
+ DBG_LOG("gendata_cocsep: generating depth %" PRIu8 "\n", i);
+ cc = dfs_cocsep(cubetofast(solvedcube()), 0, i, &n, buf32);
+ buf32[tablesize+i+1] = (uint32_t)cc;
+ }
+ buf32[tablesize] = (uint32_t)n;
+ i--;
+
+ DBG_LOG("cocsep data computed, %" PRIu16 " symmetry classes\n", n);
+ DBG_LOG("Pruning value distribution:\n");
+ for (j = 0; j < i; j++)
+ DBG_LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, buf32[tablesize+j+1]);
+
+ return 4*(tablesize + i + 1);
+}
+
+_static uint16_t
+dfs_cocsep(
+ cube_fast_t c,
+ uint8_t depth,
+ uint8_t maxdepth,
+ uint16_t *n,
+ uint32_t *buf32
+)
+{
+ uint8_t m, t, tinv, olddepth;
+ uint16_t cc;
+ uint32_t oldvalue;
+ uint64_t i;
+ cube_fast_t d;
+
+ oldvalue = buf32[coord_fast_cocsep(c)];
+ if (depth == maxdepth) {
+ if ((oldvalue & 0xFFU) != 0xFFU)
+ return 0;
+ for (t = 0, cc = 0; t < 48; t++) {
+ d = transform(c, t);
+ i = coord_fast_cocsep(d);
+ tinv = inverse_trans(t);
+ if ((buf32[i] & 0xFFU) == 0xFFU)
+ cc++;
+ buf32[i] = (*n << 16U) | (tinv << 8U) | depth;
+ }
+ (*n)++;
+
+ return cc;
+ }
+
+ olddepth = (uint8_t)(oldvalue & 0xFFU);
+ if (olddepth != depth)
+ return 0;
+
+ for (m = 0, cc = 0; m < 18; m++)
+ cc += dfs_cocsep(move(c, m), depth+1, maxdepth, n, buf32);
+
+ return cc;
+}
/******************************************************************************
Section: solvers
diff --git a/test/061_inverse_trans/00_all.in b/test/061_inverse_trans/00_all.in
diff --git a/test/061_inverse_trans/00_all.out b/test/061_inverse_trans/00_all.out
diff --git a/test/061_inverse_trans/inverse_trans_tests.c b/test/061_inverse_trans/inverse_trans_tests.c
@@ -0,0 +1,38 @@
+#include "../test.h"
+
+uint8_t readtrans(char *);
+uint8_t inverse_trans(uint8_t);
+cube_t applymoves(cube_t, char *);
+cube_t applytrans(cube_t, char *);
+extern char *transstr[];
+
+int main(void) {
+ uint8_t t, tinv;
+ cube_t cube;
+
+ for (t = 0; t < 48; t++) {
+ cube = solvedcube();
+ cube = applymoves(cube, "R");
+ cube = applymoves(cube, "U");
+ cube = applymoves(cube, "F");
+
+ cube = applytrans(cube, transstr[t]);
+ tinv = inverse_trans(t);
+ cube = applytrans(cube, transstr[tinv]);
+
+ if (iserror(cube)) {
+ printf("Error transforming cube\n");
+ } else if (!issolvable(cube)) {
+ printf("Transformed cube is not solvable\n");
+ } else {
+ cube = applymoves(cube, "F'");
+ cube = applymoves(cube, "U'");
+ cube = applymoves(cube, "R'");
+ if (!issolved(cube))
+ printf("%s: Error! Got %" PRIu8 "\n",
+ transstr[t], tinv);
+ }
+ }
+
+ return 0;
+}
diff --git a/test/100_gendata_cocsep/00_all.in b/test/100_gendata_cocsep/00_all.in
diff --git a/test/100_gendata_cocsep/00_all.out b/test/100_gendata_cocsep/00_all.out
@@ -0,0 +1 @@
+1119788
diff --git a/test/100_gendata_cocsep/gendata_cocsep_tests.c b/test/100_gendata_cocsep/gendata_cocsep_tests.c
@@ -0,0 +1,14 @@
+#include "../test.h"
+
+size_t gendata_cocsep(void *);
+
+int main(void) {
+ uint32_t buf[300000];
+ size_t result;
+
+ result = gendata_cocsep(buf);
+
+ printf("%zu\n", result);
+
+ return 0;
+}
diff --git a/test/test.h b/test/test.h
@@ -22,5 +22,6 @@ typedef cube_t cube_fast_t;
cube_t solvedcube(void);
bool iserror(cube_t);
bool issolvable(cube_t);
+bool issolved(cube_t);
cube_t readcube(char *, char *);
void writecube(char *, cube_t, char *);
