commit 0f23987edbbabdf88fbe175f695b4fdb727586fd
parent 50fedbdbf98bcf01bcd95259ac5a93ae108b3c68
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri, 28 Mar 2025 20:57:04 +0100
DR coordinate solver
Diffstat:
11 files changed, 299 insertions(+), 15 deletions(-)
diff --git a/src/solvers/coord/coord.h b/src/solvers/coord/coord.h
@@ -1,6 +1,7 @@
#include "types_macros.h"
#include "common.h"
#include "eo.h"
+#include "dr.h"
#include "list.h"
#include "utils.h"
#include "gendata.h"
diff --git a/src/solvers/coord/dr.h b/src/solvers/coord/dr.h
@@ -0,0 +1,178 @@
+#define DREOESEP_CLASSES UINT64_C(64430)
+#define DREOESEP_MAX (POW_2_11 * COMB_12_4)
+
+#define DR_CLASS_TABLESIZE (sizeof(uint32_t) * (size_t)DREOESEP_MAX)
+#define DR_REP_TABLESIZE (sizeof(uint32_t) * (size_t)DREOESEP_CLASSES)
+#define DR_COORD_DATASIZE (INFOSIZE + DR_CLASS_TABLESIZE + DR_REP_TABLESIZE)
+
+#define DR_CLASS_SHIFT UINT32_C(16)
+#define DR_CLASS_MASK (UINT32_C(0xFFFF) << DR_CLASS_SHIFT)
+#define DR_CLASS(d) (((d) & DR_CLASS_MASK) >> DR_CLASS_SHIFT)
+
+#define DR_TTREP_SHIFT UINT32_C(0)
+#define DR_TTREP_MASK (UINT32_C(0xFF) << DR_TTREP_SHIFT)
+#define DR_TTREP(d) (((d) & DR_TTREP_MASK) >> DR_TTREP_SHIFT)
+
+#define DR_ISNASTY_SHIFT UINT32_C(8)
+#define DR_ISNASTY_MASK (UINT32_C(0xFF) << DR_ISNASTY_SHIFT)
+#define DR_ISNASTY(d) (((d) & DR_ISNASTY_MASK) >> DR_ISNASTY_SHIFT)
+
+STATIC uint64_t coord_dreoesep_nosym(cube_t);
+STATIC cube_t invcoord_dreoesep_nosym(uint64_t);
+
+STATIC uint64_t coordinate_dr_coord(cube_t, const void *);
+STATIC cube_t coordinate_dr_cube(uint64_t, const void *);
+STATIC bool coordinate_dr_isnasty(uint64_t, const void *);
+STATIC uint64_t coordinate_dr_gendata(void *);
+
+STATIC coord_t coordinate_dr = {
+ .name = "DR",
+ .coord = &coordinate_dr_coord,
+ .cube = &coordinate_dr_cube,
+ .isnasty = &coordinate_dr_isnasty,
+ .gendata = coordinate_dr_gendata,
+ .max = DREOESEP_CLASSES * POW_3_7,
+ .trans_mask = TM_UDFIX,
+ .moves_mask = MM_ALLMOVES,
+ .axistrans = {
+ [AXIS_UD] = TRANS_UFr,
+ [AXIS_RL] = TRANS_RFr,
+ [AXIS_FB] = TRANS_FDr,
+ },
+ .is_admissible = &solution_lastqt_cw,
+};
+
+STATIC uint64_t
+coord_dreoesep_nosym(cube_t cube)
+{
+ uint64_t eo, esep;
+
+ esep = coord_esep(cube) / COMB_8_4;
+ eo = coord_eo(cube);
+
+ return esep * POW_2_11 + eo;
+}
+
+STATIC cube_t
+invcoord_dreoesep_nosym(uint64_t coord)
+{
+ uint64_t eo, esep;
+ cube_t cube;
+
+ eo = coord % POW_2_11;
+ esep = (coord / POW_2_11) * COMB_8_4;
+ cube = invcoord_esep(esep);
+ set_eo(&cube, eo);
+
+ return cube;
+}
+
+STATIC uint64_t
+coordinate_dr_coord(cube_t cube, const void *data)
+{
+ const char *datanoinfo;
+ const uint32_t *data32;
+ uint32_t d;
+ cube_t transformed;
+
+ datanoinfo = (const char *)data + INFOSIZE;
+ data32 = (const uint32_t *)datanoinfo;
+ d = data32[coord_dreoesep_nosym(cube)];
+ transformed = transform(cube, DR_TTREP(d));
+
+ return DR_CLASS(d) * POW_3_7 + coord_co(transformed);
+}
+
+STATIC cube_t
+coordinate_dr_cube(uint64_t coord, const void *data)
+{
+ const char *datanoinfo;
+ const uint32_t *rep32;
+ cube_t cube;
+
+ datanoinfo = (const char *)data + INFOSIZE;
+ rep32 = (const uint32_t *)(datanoinfo + DR_CLASS_TABLESIZE);
+ cube = invcoord_dreoesep_nosym(rep32[coord / POW_3_7]);
+ copy_corners(&cube, invcoord_co(coord % POW_3_7));
+
+ return cube;
+}
+
+STATIC bool
+coordinate_dr_isnasty(uint64_t coord, const void *data)
+{
+ const char *datanoinfo;
+ const uint32_t *classttrep;
+
+ datanoinfo = (const char *)data + INFOSIZE;
+ classttrep = (const uint32_t *)datanoinfo;
+
+ return DR_ISNASTY(classttrep[coord]);
+}
+
+STATIC size_t
+coordinate_dr_gendata(void *data)
+{
+ uint64_t i, ii, j, n, t, nasty;
+ char *datanoinfo;
+ uint32_t *classttrep, *rep;
+ cube_t c;
+ tableinfo_t info;
+
+ if (data == NULL)
+ goto coordinate_dr_gendata_returnsize;
+
+ datanoinfo = (char *)data + INFOSIZE;
+ classttrep = (uint32_t *)datanoinfo;
+ rep = classttrep + (DR_CLASS_TABLESIZE / sizeof(uint32_t));
+ memset(data, 0xFF, DR_COORD_DATASIZE);
+
+ info = (tableinfo_t) {
+ .solver = "coord data for DR",
+ .type = TABLETYPE_SPECIAL,
+ .infosize = INFOSIZE,
+ .fullsize = DR_COORD_DATASIZE,
+ .hash = 0,
+ .entries = DREOESEP_CLASSES + DREOESEP_MAX,
+ .classes = DREOESEP_CLASSES,
+ .bits = 32,
+ .base = 0,
+ .maxvalue = 0,
+ .next = 0
+ };
+
+ for (i = 0, n = 0; i < COMB_12_4 * POW_2_11; i++) {
+ if (classttrep[i] != 0xFFFFFFFF)
+ continue;
+
+ c = invcoord_dreoesep_nosym(i);
+ ii = coord_dreoesep_nosym(c);
+ for (t = 0, nasty = 0; t < NTRANS && !nasty; t++) {
+ if (!((UINT64_C(1) << t) & coordinate_dr.trans_mask))
+ continue;
+
+ nasty = ii == coord_dreoesep_nosym(transform(c, t));
+ }
+
+ for (t = 0; t < NTRANS; t++) {
+ if (!((UINT64_C(1) << t) & coordinate_dr.trans_mask))
+ continue;
+
+ j = coord_dreoesep_nosym(transform(c, t));
+ classttrep[j] =
+ (n << DR_CLASS_SHIFT) |
+ (nasty << DR_ISNASTY_SHIFT) |
+ (inverse_trans(t) << DR_TTREP_SHIFT);
+ }
+ rep[n++] = i;
+ }
+
+ writetableinfo(&info, DR_COORD_DATASIZE, data);
+
+ DBG_ASSERT(n == DREOESEP_CLASSES, 0,
+ "dr coordinate data: computed %" PRIu64 " classes, "
+ "expected %" PRIu64 "\n", n, DREOESEP_CLASSES);
+
+coordinate_dr_gendata_returnsize:
+ return DR_COORD_DATASIZE;
+}
diff --git a/src/solvers/coord/eo.h b/src/solvers/coord/eo.h
@@ -1,14 +1,16 @@
STATIC uint64_t coordinate_eo_coord(cube_t, const void *);
STATIC cube_t coordinate_eo_cube(uint64_t, const void *);
+STATIC bool coordinate_eo_isnasty(uint64_t, const void *);
STATIC uint64_t coordinate_eo_gendata(void *);
STATIC coord_t coordinate_eo = {
.name = "EO",
.coord = &coordinate_eo_coord,
.cube = &coordinate_eo_cube,
+ .isnasty = &coordinate_eo_isnasty,
.gendata = coordinate_eo_gendata,
.max = POW_2_11,
- .trans_mask = TM_ALLTRANS,
+ .trans_mask = TM_SINGLE(TRANS_UFr),
.moves_mask = MM_ALLMOVES,
.axistrans = {
[AXIS_UD] = TRANS_FDr,
@@ -32,6 +34,12 @@ coordinate_eo_cube(uint64_t c, const void *data)
return cube;
}
+STATIC bool
+coordinate_eo_isnasty(uint64_t c, const void *data)
+{
+ return false;
+}
+
STATIC size_t
coordinate_eo_gendata(void *data)
{
diff --git a/src/solvers/coord/gendata.h b/src/solvers/coord/gendata.h
@@ -2,6 +2,8 @@ STATIC size_t gendata_coord(const coord_t [static 1], void *);
STATIC int64_t gendata_coord_dispatch(const char *, void *);
STATIC tableinfo_t genptable_coord(
const coord_t [static 1], const void *, uint8_t *);
+STATIC uint64_t genptable_coord_fillneighbors(
+ const coord_t [static 1], const void *, uint64_t, uint8_t, uint8_t *);
STATIC void getdistribution_coord(
const uint8_t *, const char *, uint64_t [static INFO_DISTRIBUTION_LEN]);
STATIC uint8_t get_coord_pval(
@@ -81,10 +83,8 @@ genptable_coord(
uint8_t *table
)
{
- uint64_t tablesize, i, j, d, tot;
+ uint64_t tablesize, i, d, tot, t;
tableinfo_t info;
- uint8_t m;
- cube_t c, cc;
tablesize = DIV_ROUND_UP(coord->max, 2);
@@ -113,24 +113,52 @@ genptable_coord(
for (d = 1, tot = 1; tot < coord->max; d++) {
for (i = 0; i < coord->max; i++) {
if (get_coord_pval(coord, table, i) == d-1) {
- c = coord->cube(i, data);
- for (m = 0; m < 18; m++) {
- cc = move(c, m);
- j = coord->coord(cc, data);
- if (get_coord_pval(coord, table, j) > d) {
- set_coord_pval(coord, table, j, d);
- tot++;
- info.distribution[d]++;
- }
- }
+ t = genptable_coord_fillneighbors(
+ coord, data, i, d, table);
+ tot += t;
+ info.distribution[d] += t;
}
}
+ LOG("Depth %" PRIu64 ": %" PRIu64 " of %" PRIu64 "\n",
+ d, tot, coord->max);
}
info.maxvalue = d-1;
return info;
}
+STATIC uint64_t
+genptable_coord_fillneighbors(
+ const coord_t coord[static 1],
+ const void *data,
+ uint64_t i,
+ uint8_t d,
+ uint8_t *table
+)
+{
+ uint8_t m;
+ uint64_t j, t, tot;
+ cube_t c, moved;
+
+ c = coord->cube(i, data);
+ tot = 0;
+ for (m = 0; m < NMOVES; m++) {
+ moved = move(c, m);
+ for (t = 0; t < NTRANS; t++) {
+ if (!((UINT64_C(1) << t) & coord->trans_mask))
+ continue;
+
+ j = coord->coord(transform(moved, t), data);
+ if (get_coord_pval(coord, table, j) > d) {
+ set_coord_pval(coord, table, j, d);
+ tot++;
+ }
+ }
+ }
+
+ return tot;
+}
+
STATIC void
getdistribution_coord(
const uint8_t *table,
diff --git a/src/solvers/coord/list.h b/src/solvers/coord/list.h
@@ -1,4 +1,5 @@
coord_t *all_coordinates[] = {
&coordinate_eo,
+ &coordinate_dr,
NULL
};
diff --git a/src/solvers/coord/types_macros.h b/src/solvers/coord/types_macros.h
@@ -6,6 +6,7 @@ typedef struct {
const char name[255];
uint64_t (*coord)(cube_t, const void *);
cube_t (*cube)(uint64_t, const void *);
+ bool (*isnasty)(uint64_t, const void *);
size_t (*gendata)(void *);
uint64_t max;
uint32_t moves_mask;
diff --git a/src/utils/constants.h b/src/utils/constants.h
@@ -106,6 +106,13 @@ STATIC int64_t binomial[12][12] = {
#define TM_ALLTRANS UINT64_C(0xFFFFFFFFFFFF)
#define TM_SINGLE(t) (UINT64_C(1) << (uint64_t)(t))
+#define TM_UDFIX (\
+ TM_SINGLE(TRANS_UFr) | TM_SINGLE(TRANS_UBr) | TM_SINGLE(TRANS_URr) | \
+ TM_SINGLE(TRANS_ULr) | TM_SINGLE(TRANS_UFm) | TM_SINGLE(TRANS_UBm) | \
+ TM_SINGLE(TRANS_URm) | TM_SINGLE(TRANS_ULm) | TM_SINGLE(TRANS_DFr) | \
+ TM_SINGLE(TRANS_DBr) | TM_SINGLE(TRANS_DRr) | TM_SINGLE(TRANS_DLr) | \
+ TM_SINGLE(TRANS_DFm) | TM_SINGLE(TRANS_DBm) | TM_SINGLE(TRANS_DRm) | \
+ TM_SINGLE(TRANS_DLm))
#define CORNER_UFR UINT8_C(0)
#define CORNER_UBL UINT8_C(1)
diff --git a/test/121_coorddata_dr/00_all.in b/test/121_coorddata_dr/00_all.in
diff --git a/test/121_coorddata_dr/00_all.out b/test/121_coorddata_dr/00_all.out
@@ -0,0 +1 @@
+All good
diff --git a/test/121_coorddata_dr/coorddata_dr.c b/test/121_coorddata_dr/coorddata_dr.c
@@ -0,0 +1,59 @@
+#include "../test.h"
+
+#define POW_3_7 2187
+#define BOUND (64430 * POW_3_7 / 100)
+#define TGROUP UINT64_C(4278190335)
+
+cube_t transform(cube_t, uint8_t);
+uint64_t coordinate_dr_coord(cube_t, const void *);
+cube_t coordinate_dr_cube(uint64_t, const void *);
+uint64_t coordinate_dr_gendata(void *);
+
+void run(void) {
+ bool found;
+ uint64_t t;
+ char str[STRLENMAX];
+ void *data;
+ size_t size;
+ cube_t cube;
+ uint64_t coord, coord2;
+
+ size = coordinate_dr_gendata(NULL);
+ data = malloc(size);
+ coordinate_dr_gendata(data);
+
+ /* Test all possible values for CO coordinate */
+ for (coord = 0; coord < BOUND; coord++) {
+ cube = coordinate_dr_cube(coord, data);
+
+ if (!isconsistent(cube)) {
+ printf("Error: invcoord of %" PRId64
+ " is not consistent\n", coord);
+ goto cleanup;
+ }
+
+ for (t = 0, found = false; t < 48; t++) {
+ if (!((UINT64_C(1) << t) & TGROUP))
+ continue;
+
+ coord2 = coordinate_dr_coord(transform(cube, t), data);
+ if (coord == coord2) {
+ found = true;
+ break;
+ }
+ }
+
+ if (!found) {
+ printf("Error: invcoord of %" PRId64 " returns %"
+ PRId64 " with cube:\n", coord, coord2);
+ writecube("H48", cube, STRLENMAX, str);
+ printf("%s\n", str);
+ goto cleanup;
+ }
+ }
+
+ printf("All good\n");
+
+cleanup:
+ free(data);
+}
diff --git a/test/test.h b/test/test.h
@@ -26,7 +26,7 @@ bool isconsistent(cube_t);
bool issolvable(cube_t);
bool issolved(cube_t);
cube_t readcube(char *, char *);
-int64_t writecube(char *, cube_t, size_t n, char [n]);
+int64_t writecube(const char *, cube_t, size_t n, char [n]);
/* Test function to be implemented by all tests */
void run(void);
