From 0f23987edbbabdf88fbe175f695b4fdb727586fd Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Fri, 28 Mar 2025 20:57:04 +0100 Subject: DR coordinate solver --- src/solvers/coord/coord.h | 1 + src/solvers/coord/dr.h | 178 +++++++++++++++++++++++++++++++++++++++ src/solvers/coord/eo.h | 10 ++- src/solvers/coord/gendata.h | 54 +++++++++--- src/solvers/coord/list.h | 1 + src/solvers/coord/types_macros.h | 1 + src/utils/constants.h | 7 ++ 7 files changed, 238 insertions(+), 14 deletions(-) create mode 100644 src/solvers/coord/dr.h (limited to 'src') diff --git a/src/solvers/coord/coord.h b/src/solvers/coord/coord.h index f42739d..11d41bc 100644 --- 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 new file mode 100644 index 0000000..5f3a99b --- /dev/null +++ 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 index ef9b27a..3fabf9f 100644 --- 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 index ca058b0..5e40575 100644 --- 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 index 32c94a4..7d43d45 100644 --- 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 index 9eaeca0..8741e27 100644 --- 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 index ef8c7e0..a6c6b7a 100644 --- 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) -- cgit v1.3