commit 7defd8041e6050a9adf7927b43fd249d75d6389f
parent 038469b6f27106ab2002c7da11c6bca2a5fe30ee
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue, 4 Mar 2025 08:24:39 +0100
Begin work for coordinate solver
Diffstat:
12 files changed, 263 insertions(+), 0 deletions(-)
diff --git a/TODO_COORDINATES b/TODO_COORDINATES
@@ -0,0 +1,7 @@
+- solver
+ - include NISS
+- test solver for EO
+- make solve parallelized
+- other coordinates
+ - gendata must handle symmetry
+- make gendata parallelized
diff --git a/src/solvers/coord/common.h b/src/solvers/coord/common.h
@@ -0,0 +1,20 @@
+#include "eo.h"
+
+coord_t *all_coordinates[] = {
+ &coordinate_eo,
+ NULL
+};
+
+STATIC void append_coord_name(const coord_t *, char *);
+
+STATIC void
+append_coord_name(const coord_t *coord, char *str)
+{
+ int i, j;
+
+ i = 0;
+ j = strlen(str);
+ while (coord->name[i]) str[j++] = coord->name[i++];
+
+ str[j] = '\0';
+}
diff --git a/src/solvers/coord/coord_solve.h b/src/solvers/coord/coord_solve.h
@@ -0,0 +1,3 @@
+#include "coord_types_macros.h"
+#include "common.h"
+#include "gendata_coord.h"
diff --git a/src/solvers/coord/coord_types_macros.h b/src/solvers/coord/coord_types_macros.h
@@ -0,0 +1,13 @@
+#define COORD_INDEX(i) ((i)/2)
+#define COORD_SHIFT(i) (UINT8_C(4) * (uint8_t)((i) % 2))
+#define COORD_MASK(i) (UINT8_C(0xF) << COORD_SHIFT(i))
+
+typedef struct {
+ char name[255];
+ uint64_t (*coord)(cube_t, const void *);
+ cube_t (*cube)(uint64_t, const void *);
+ size_t (*gendata)(void *);
+ uint64_t max;
+ uint32_t moves_mask;
+ uint64_t trans_mask;
+} coord_t;
diff --git a/src/solvers/coord/eo.h b/src/solvers/coord/eo.h
@@ -0,0 +1,33 @@
+STATIC uint64_t coordinate_eo_coord(cube_t, const void *);
+STATIC cube_t coordinate_eo_cube(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,
+ .gendata = coordinate_eo_gendata,
+ .max = POW_2_11,
+ .trans_mask = TM_ALLTRANS,
+ .moves_mask = MM_ALLMOVES,
+};
+
+STATIC uint64_t
+coordinate_eo_coord(cube_t c, const void *data)
+{
+ return (uint64_t)coord_eo(c);
+}
+
+STATIC cube_t
+coordinate_eo_cube(uint64_t c, const void *data)
+{
+ cube_t cube = SOLVED_CUBE;
+ set_eo(&cube, (int64_t)c);
+ return cube;
+}
+
+STATIC size_t
+coordinate_eo_gendata(void *data)
+{
+ return 0;
+}
diff --git a/src/solvers/coord/gendata_coord.h b/src/solvers/coord/gendata_coord.h
@@ -0,0 +1,134 @@
+STATIC size_t gendata_coordinate(const coord_t *, void *);
+STATIC size_t gendata_coordinate_name(const char *, void *);
+STATIC tableinfo_t genptable_coordinate(const coord_t *, const void *, uint8_t *);
+STATIC uint8_t get_coord_pval(const coord_t *, const uint8_t *, uint64_t);
+STATIC void set_coord_pval(const coord_t *, uint8_t *, uint64_t, uint8_t);
+
+STATIC size_t
+gendata_coordinate_name(const char *name, void *buf)
+{
+ int i;
+
+ for (i = 0; all_coordinates[i] != NULL; i++)
+ if (strcmp(all_coordinates[i]->name, name) == 0)
+ return gendata_coordinate(all_coordinates[i], buf);
+
+ LOG("Cannot generate data for coordinate '%s': not found\n", name);
+ return 0;
+}
+
+STATIC size_t
+gendata_coordinate(const coord_t *coord, void *buf)
+{
+ uint64_t coord_dsize, tablesize, ninfo;
+ void *pruningbuf, *coord_data;
+ uint8_t *table;
+ tableinfo_t coord_data_info, pruning_info;
+
+ coord_data = buf == NULL ? NULL : ((uint8_t *)buf) + INFOSIZE;
+ coord_dsize = coord->gendata(coord_data);
+ ninfo = coord_dsize == 0 ? 1 : 2;
+ tablesize = DIV_ROUND_UP(coord->max, 2);
+
+ if (buf == NULL)
+ goto gendata_coordinate_return_size;
+
+ if (ninfo == 2) {
+ coord_data_info = (tableinfo_t) {
+ .solver = "coord helper table for ",
+ .type = TABLETYPE_SPECIAL,
+ .infosize = INFOSIZE,
+ .fullsize = INFOSIZE + coord_dsize,
+ .hash = 0, /* TODO */
+ .next = INFOSIZE + coord_dsize,
+
+ /* Unknown / non-applicable values */
+ .entries = 0,
+ .classes = 0,
+ .bits = 0,
+ .base = 0,
+ .maxvalue = 0,
+ };
+
+ append_coord_name(coord, coord_data_info.solver);
+
+ writetableinfo(&coord_data_info, INFOSIZE + coord_dsize, buf);
+
+ pruningbuf = ((uint8_t *)buf) + INFOSIZE + coord_dsize;
+ } else {
+ pruningbuf = buf;
+ }
+
+ table = ((uint8_t *)pruningbuf) + INFOSIZE;
+ pruning_info = genptable_coordinate(coord, coord_data, table);
+ writetableinfo(&pruning_info, INFOSIZE + tablesize, pruningbuf);
+
+gendata_coordinate_return_size:
+ return ninfo * INFOSIZE + coord_dsize + tablesize;
+}
+
+STATIC tableinfo_t
+genptable_coordinate(const coord_t *coord, const void *data, uint8_t *table)
+{
+ uint64_t tablesize, i, j, d, tot;
+ tableinfo_t info;
+ uint8_t m;
+ cube_t c, cc;
+
+ tablesize = DIV_ROUND_UP(coord->max, 2);
+
+ memset(table, 0xFF, tablesize);
+
+ info = (tableinfo_t) {
+ .solver = "coordinate solver for ",
+ .type = TABLETYPE_PRUNING,
+ .infosize = INFOSIZE,
+ .fullsize = INFOSIZE + tablesize,
+ .hash = 0, /* TODO */
+ .entries = coord->max,
+ .classes = 0,
+ .bits = 4,
+ .base = 0,
+ .maxvalue = 0,
+ .next = 0
+ };
+
+ memset(info.distribution, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t));
+ append_coord_name(coord, info.solver);
+
+ i = coord->coord(SOLVED_CUBE, data);
+ set_coord_pval(coord, table, i, 0);
+ info.distribution[0] = 1;
+ 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]++;
+ }
+ }
+ }
+ }
+ }
+ info.maxvalue = d-1;
+
+ return info;
+}
+
+STATIC uint8_t
+get_coord_pval(const coord_t *coord, const uint8_t *table, uint64_t i)
+{
+ return (table[COORD_INDEX(i)] & COORD_MASK(i)) >> COORD_SHIFT(i);
+}
+
+STATIC void
+set_coord_pval(const coord_t *coord, uint8_t *table, uint64_t i, uint8_t val)
+{
+ table[COORD_INDEX(i)] = (table[COORD_INDEX(i)] & (~COORD_MASK(i)))
+ | (val << COORD_SHIFT(i));
+}
diff --git a/src/solvers/solvers.h b/src/solvers/solvers.h
@@ -1,2 +1,3 @@
#include "tables.h"
#include "h48/h48.h"
+#include "coord/coord_solve.h"
diff --git a/src/utils/constants.h b/src/utils/constants.h
@@ -99,6 +99,8 @@ STATIC int64_t binomial[12][12] = {
#define MM_ALLMOVES UINT32_C(0x3FFFF)
#define MM_NOHALFTURNS UINT32_C(0x2DB6D)
+#define TM_ALLTRANS UINT64_C(0xFFFFFFFFFFFF)
+
#define CORNER_UFR UINT8_C(0)
#define CORNER_UBL UINT8_C(1)
#define CORNER_DFL UINT8_C(2)
diff --git a/test/120_gendata_eo/00_all.in b/test/120_gendata_eo/00_all.in
diff --git a/test/120_gendata_eo/00_all.out b/test/120_gendata_eo/00_all.out
@@ -0,0 +1,12 @@
+1536
+0: 1
+1: 2
+2: 25
+3: 202
+4: 620
+5: 900
+6: 285
+7: 13
+8: 0
+9: 0
+10: 0
diff --git a/test/120_gendata_eo/gendata_eo_tests.c b/test/120_gendata_eo/gendata_eo_tests.c
@@ -0,0 +1,37 @@
+/*
+Pruning table values (from nissy):
+0: 1
+1: 2
+2: 25
+3: 202
+4: 620
+5: 900
+6: 285
+7: 13
+*/
+
+#include "../test.h"
+
+#define ISIZE 512
+#define FULLSIZE (ISIZE + 1024)
+
+char buf[FULLSIZE];
+
+size_t gendata_coordinate_name(const char *, void *);
+bool readtableinfo(uint64_t, const char *, tableinfo_t *);
+
+void run(void) {
+ uint32_t i;
+ size_t result;
+ tableinfo_t info;
+
+ result = gendata_coordinate_name("EO", buf);
+ if (readtableinfo(FULLSIZE, buf, &info) != NISSY_OK) {
+ printf("Error reading info from table\n");
+ return;
+ }
+
+ printf("%zu\n", result);
+ for (i = 0; i <= 10; i++)
+ printf("%" PRIu32 ": %" PRIu64 "\n", i, info.distribution[i]);
+}
diff --git a/test/test.h b/test/test.h
@@ -14,6 +14,7 @@
#include "../src/solvers/h48/coordinate_macros.h"
#include "../src/solvers/h48/map_types_macros.h"
#include "../src/solvers/h48/gendata_types_macros.h"
+#include "../src/solvers/coord/coord_types_macros.h"
#define STRLENMAX 10000
