commit c2275e4b9625a1a19eb50d0880f70ed583d5c358
parent 66c1c11ec13d362ddfb1b5f6abe8127969c0ad29
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon, 8 Jul 2024 19:22:16 +0200
Stats for h48 solver as tool
Diffstat:
14 files changed, 177 insertions(+), 146 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -10,5 +10,6 @@ tables/*
test/*/runtest
test/run
test/last.*
+tools/results
*.o
*.s
diff --git a/Makefile b/Makefile
@@ -18,8 +18,13 @@ test: debugcube.o
CUBETYPE=${CUBETYPE} TEST=${TEST} ./test/test.sh
tool: cube.o
+ mkdir -p tools/results
CUBETYPE=${CUBETYPE} ./tools/run_tool.sh
+debugtool: debugcube.o
+ mkdir -p tools/results
+ CUBETYPE=${CUBETYPE} DEBUG=1 ./tools/run_tool.sh
+
shell: cube.o
mkdir -p tables
${CC} ${CFLAGS} -o run cube.o shell.c
@@ -28,4 +33,4 @@ debugshell: debugcube.o
mkdir -p tables
${CC} ${DBGFLAGS} -o run debugcube.o shell.c
-.PHONY: all clean test tool shell debugshell
+.PHONY: all clean test tool debugtool shell debugshell
diff --git a/TODO.txt b/TODO.txt
@@ -1,7 +1,5 @@
Check stats for all tables using H48stats solver
- - optional: dr states (includes "fix" option)
- - implement tool for stats
- - output to file, only write cocsep to stdout
+ - what now?
Bug in esep table generation
- Fails for UFRUFU, try command
@@ -18,8 +16,9 @@ Bug in esep table generation
Solver
- cleanup h48 solver
- - do not copy dfsarg, change and undo
- - implement and use premove (and test) instead of inverting
+ - do not copy dfsarg, change and undo
+ - implement and use premove (and test) instead of inverting
+ - improve name of tables file in shell.c (include h value, maybe k, max)
- benchmark for solve
table generation, where to keep tables? in benchmark folder or in tables/?
- more tricks for solver, optimize, try larger tables
diff --git a/src/cube_public.h b/src/cube_public.h
@@ -156,17 +156,22 @@ nissy_gendata(
int64_t ret;
uint8_t maxdepth, h, i, j;
- if (!strcmp(solver, "H48")) {
+ if (!strcmp(solver, "h48")) {
/* options are in the form "h;maxdepth" */
for (i = 0; options[i] != ';'; i++) ;
for (j = i; options[j]; j++) ;
h = atoi(options);
- maxdepth = atoi(&options[i+1]);
- ret = gendata_h48(data, h, maxdepth);
- } else if (!strcmp(solver, "H48stats")) {
- ret = gendata_cocsep(data, NULL, NULL);
+ if (h != 0) {
+ LOG("Temporarily only h=0 is supported\n");
+ ret = -1;
+ } else {
+ maxdepth = atoi(&options[i+1]);
+ ret = gendata_h48h0k4(data, maxdepth);
+ }
+ } else if (!strcmp(solver, "h48stats")) {
+ ret = gendata_h48h0k4(data, 20);
} else {
- LOG("gendata: implemented only for H48 solver\n");
+ LOG("gendata: implemented only for h48 solver\n");
ret = -1;
}
@@ -224,13 +229,13 @@ nissy_solve(
}
/* TODO define and use solve_options_t */
- if (!strcmp(solver, "H48")) {
+ if (!strcmp(solver, "h48")) {
h = atoi(options); /* TODO: better parsing */
ret = solve_h48(
c, minmoves, maxmoves, maxsolutions,
(uint8_t)h, data, solutions);
ret = -1;
- } else if (!strcmp(solver, "H48stats")) {
+ } else if (!strcmp(solver, "h48stats")) {
ret = solve_h48stats(c, maxmoves, data, solutions);
} else if (!strcmp(solver, "simple")) {
ret = solve_simple(
diff --git a/src/solve_h48.h b/src/solve_h48.h
@@ -36,7 +36,6 @@ typedef struct {
typedef struct {
uint8_t depth;
- uint8_t h;
uint32_t *cocsepdata;
uint32_t *buf32;
uint64_t *selfsim;
@@ -63,6 +62,7 @@ typedef struct {
int8_t depth;
uint8_t moves[MAX_SOLUTION_LENGTH];
uint32_t *cocsepdata;
+ uint32_t *h48data;
char *s;
} dfsarg_solveh48stats_t;
@@ -72,8 +72,8 @@ _static_inline cube_t invcoord_h48(int64_t, const cube_t *, uint8_t);
_static size_t gendata_cocsep(void *, uint64_t *, cube_t *);
_static uint32_t gendata_cocsep_dfs(dfsarg_cocsep_t *);
-_static size_t gendata_h48(void *, uint8_t, uint8_t);
-_static uint64_t gendata_esep_bfs(bfsarg_esep_t *);
+_static size_t gendata_h48h0k4(void *, uint8_t);
+_static uint64_t gendata_h48h0k4_bfs(bfsarg_esep_t *);
_static_inline bool get_visited(const uint8_t *, int64_t);
_static_inline void set_visited(uint8_t *, int64_t);
@@ -88,7 +88,7 @@ _static int64_t solve_h48_dfs(dfsarg_solveh48_t *);
_static int64_t solve_h48(cube_t, int8_t, int8_t, int8_t, uint8_t, const void *, char *);
_static int64_t solve_h48stats_dfs(dfsarg_solveh48stats_t *);
-_static int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 13]);
+_static int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]);
_static_inline int64_t
coord_h48(cube_t c, const uint32_t *cocsepdata, uint8_t h)
@@ -119,12 +119,6 @@ coord_h48_edges(cube_t c, int64_t coclass, uint8_t t, uint8_t h)
edges = (esep << 11) + eo;
return (coclass * H48_ESIZE(11) + edges) >> (11 - (int64_t)h);
-
-/*
-TODO: decide which alternative is better, if above or below
- edges = (esep << (int64_t)h) + (eo >> (11 - (int64_t)h));
- return coclass * H48_ESIZE(h) + edges;
-*/
}
/*
@@ -133,7 +127,8 @@ the given value, because it works up to symmetry. This means that the
returned cube is a transformed cube of one that gives the correct value.
*/
_static_inline cube_t
-invcoord_h48(int64_t i, const cube_t *crep, uint8_t h) {
+invcoord_h48(int64_t i, const cube_t *crep, uint8_t h)
+{
cube_t ret;
int64_t hh, coclass, ee, esep, eo;
@@ -274,9 +269,8 @@ TODO description
generating fixed table with h=0, k=4
*/
_static size_t
-gendata_h48(void *buf, uint8_t h, uint8_t maxdepth)
+gendata_h48h0k4(void *buf, uint8_t maxdepth)
{
- const int k = 4; /* TODO: other cases? */
uint32_t j, *buf32, *info, *cocsepdata;
bfsarg_esep_t arg;
int64_t sc, cc, tot, esep_max;
@@ -290,19 +284,18 @@ gendata_h48(void *buf, uint8_t h, uint8_t maxdepth)
infosize = 88;
if (buf == NULL)
- goto gendata_h48_return_size;
+ goto gendata_h48h0k4_return_size;
- esep_max = (int64_t)ESEP_MAX(h);
+ esep_max = (int64_t)ESEP_MAX(0);
cocsepdata = (uint32_t *)buf;
buf32 = cocsepdata + cocsepsize / 4;
- info = buf32 + (ESEP_TABLESIZE(h, k) / sizeof(uint32_t));
- memset(buf32, 0xFF, ESEP_TABLESIZE(h, k));
+ info = buf32 + (ESEP_TABLESIZE(0, 4) / sizeof(uint32_t));
+ memset(buf32, 0xFF, ESEP_TABLESIZE(0, 4));
- sc = coord_h48(solved, cocsepdata, h);
+ sc = coord_h48(solved, cocsepdata, 0);
set_esep_pval(buf32, sc, 0);
info[1] = 1;
arg = (bfsarg_esep_t) {
- .h = h,
.cocsepdata = cocsepdata,
.buf32 = buf32,
.crep = crep,
@@ -314,7 +307,7 @@ gendata_h48(void *buf, uint8_t h, uint8_t maxdepth)
arg.depth++
) {
LOG("esep: generating depth %" PRIu8 "\n", arg.depth);
- cc = gendata_esep_bfs(&arg);
+ cc = gendata_h48h0k4_bfs(&arg);
tot += cc;
info[arg.depth+1] = cc;
LOG("found %" PRIu64 "\n", cc);
@@ -328,25 +321,25 @@ gendata_h48(void *buf, uint8_t h, uint8_t maxdepth)
for (j = 0; j <= info[0]; j++)
LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, info[j+1]);
-gendata_h48_return_size:
- return cocsepsize + ESEP_TABLESIZE(h, k) + infosize;
+gendata_h48h0k4_return_size:
+ return cocsepsize + ESEP_TABLESIZE(0, 4) + infosize;
}
_static uint64_t
-gendata_esep_bfs(bfsarg_esep_t *arg)
+gendata_h48h0k4_bfs(bfsarg_esep_t *arg)
{
uint8_t c, m, x;
uint32_t cc;
int64_t i, j, k, t, cocsep_coord, sim, esep_max;
cube_t cube, moved, transd;
- esep_max = (uint64_t)ESEP_MAX(arg->h);
+ esep_max = (uint64_t)ESEP_MAX(0);
for (i = 0, cc = 0; i < esep_max; i++) {
c = get_esep_pval(arg->buf32, i);
if (c != arg->depth - 1)
continue;
- cube = invcoord_h48(i, arg->crep, arg->h);
+ cube = invcoord_h48(i, arg->crep, 0);
for (m = 0; m < 18; m++) {
/*
* TODO: here we can optimize by computing at first
@@ -354,19 +347,19 @@ gendata_esep_bfs(bfsarg_esep_t *arg)
* the edge parts for each transformation.
*/
moved = move(cube, m);
- j = coord_h48(moved, arg->cocsepdata, arg->h);
+ j = coord_h48(moved, arg->cocsepdata, 0);
x = get_esep_pval(arg->buf32, j);
if (x <= arg->depth)
continue;
set_esep_pval(arg->buf32, j, arg->depth);
cc += x != arg->depth;
- cocsep_coord = j / H48_ESIZE(arg->h);
+ cocsep_coord = j / H48_ESIZE(0);
sim = arg->selfsim[cocsep_coord] >> 1;
for (t = 1; t < 48 && sim; t++, sim >>= 1) {
if (!(sim & 1))
continue;
transd = transform(moved, t);
- k = coord_h48(transd, arg->cocsepdata, arg->h);
+ k = coord_h48(transd, arg->cocsepdata, 0);
x = get_esep_pval(arg->buf32, k);
if (x <= arg->depth)
continue;
@@ -539,46 +532,45 @@ solve_h48(
solve_h48_dfs(&arg);
}
-/*
-for (int64_t i = 0; i < 4; i++)
-LOG("Data for coord = %" PRId64 ": %" PRIu8 "\n",
-i, get_esep_pval(arg.h48data, i));
-*/
return nsols;
}
/*
-The h48stats solver computes how many moves it takes to solve to each of
-the 13 h48 coordinates: the corner-only coordinate, and 12 cocsep+esep
-coordinates with h from 0 to 11. The solutions array is filled with
-the length of the solutions: solutions[0] contains the value for the
-corner-only coordinate, and for i>0 solutions[i] contains the value for
-the cocsep+esep coordinate with h=i-1. The solution array is therefore
-not a printable string.
+The h48stats solver computes how many moves it takes to solve to
+each of the 12 h48 coordinates, one for each value of h from 0 to 11.
+The solutions array is filled with the length of the solutions. The
+solution array is therefore not a printable string.
*/
_static int64_t
solve_h48stats_dfs(dfsarg_solveh48stats_t *arg)
{
+ const int64_t limit = 11;
+
int8_t bound, u;
uint8_t m;
uint32_t d;
int64_t coord, h;
dfsarg_solveh48stats_t nextarg;
+ /* Check cocsep lower bound (corners only) */
bound = get_h48_cdata(arg->cube, arg->cocsepdata, &d);
if (bound + arg->nmoves > arg->depth)
return 0;
- u = COCLASS(d) == 0 && arg->s[0] == 99;
- arg->s[0] = u * arg->nmoves + (1-u) * arg->s[0];
+ /* Check h48 lower bound for h=0 (esep, but no eo) */
+ coord = coord_h48_edges(arg->cube, COCLASS(d), TTREP(d), 0);
+ bound = get_esep_pval(arg->h48data, coord);
+ if (bound + arg->nmoves > arg->depth)
+ return 0;
+ /* Update all other values, if solved */
coord = coord_h48_edges(arg->cube, COCLASS(d), TTREP(d), 11);
- for (h = 0; h <= 11; h++) {
- u = coord >> (11-h) == 0 && arg->s[h+1] == 99;
- arg->s[h+1] = u * arg->nmoves + (1-u) * arg->s[h+1];
+ for (h = 0; h <= limit; h++) {
+ u = coord >> (11-h) == 0 && arg->s[h] == 99;
+ arg->s[h] = u * arg->nmoves + (1-u) * arg->s[h];
}
- if (arg->s[12] != 99)
+ if (arg->s[limit] != 99)
return 0;
nextarg = *arg;
@@ -603,23 +595,27 @@ solve_h48stats(
cube_t cube,
int8_t maxmoves,
const void *data,
- char solutions[static 13]
+ char solutions[static 12]
)
{
int i;
+ size_t cocsepsize;
dfsarg_solveh48stats_t arg;
+ cocsepsize = gendata_cocsep(NULL, NULL, NULL);
+
arg = (dfsarg_solveh48stats_t) {
.cube = cube,
.cocsepdata = (uint32_t *)data,
+ .h48data = ((uint32_t *)data) + (cocsepsize/4),
.s = solutions
};
- for (i = 0; i < 13; i++)
+ for (i = 0; i < 12; i++)
solutions[i] = (char)99;
for (arg.depth = 0;
- arg.depth <= maxmoves && solutions[12] == 99;
+ arg.depth <= maxmoves && solutions[11] == 99;
arg.depth++)
{
arg.nmoves = 0;
diff --git a/test/103_gendata_h48/00_h_0.in b/test/103_gendata_h48/00_h_0.in
@@ -1 +0,0 @@
-0
diff --git a/test/103_gendata_h48/01_h_1.in b/test/103_gendata_h48/01_h_1.in
@@ -1 +0,0 @@
-1
diff --git a/test/103_gendata_h48/01_h_1.out b/test/103_gendata_h48/01_h_1.out
@@ -1,23 +0,0 @@
-118687330
-
-cocsepdata:
-Classes: 3393
-Max value: 9
-0: 1
-1: 6
-2: 63
-3: 468
-4: 3068
-5: 15438
-6: 53814
-7: 71352
-8: 8784
-9: 96
-
-h48:
-0: 1
-1: 1
-2: 4
-3: 34
-4: 375
-5: 4078
diff --git a/test/103_gendata_h48/gendata_h48_tests.c b/test/103_gendata_h48/gendata_h48_tests.c
@@ -1,34 +0,0 @@
-#include "../test.h"
-
-#define MAXDEPTH 5
-#define COCSEPSIZE 1119792
-#define ETABLESIZE(h) (((3393 * 495 * 70) >> 1) << (size_t)(h))
-
-size_t gendata_h48(void *, uint8_t, uint8_t);
-
-void run(void) {
- char str[STRLENMAX];
- uint8_t h, i;
- uint32_t *buf, *h48info;
- size_t result;
-
- fgets(str, STRLENMAX, stdin);
- h = atoi(str);
- buf = (uint32_t *)malloc(sizeof(uint32_t) * (60000000 << h));
- result = gendata_h48(buf, h, MAXDEPTH);
- h48info = buf + (ETABLESIZE(h) + COCSEPSIZE) / 4;
-
- printf("%zu\n\n", result);
-
- printf("cocsepdata:\n");
- printf("Classes: %" PRIu32 "\n", buf[COCSEPSIZE/4-12]);
- printf("Max value: %" PRIu32 "\n", buf[COCSEPSIZE/4-11]);
- for (i = 0; i < 10; i++)
- printf("%" PRIu32 ": %" PRIu32 "\n", i, buf[COCSEPSIZE/4-10+i]);
-
- printf("\nh48:\n");
- for (i = 0; i < MAXDEPTH+1; i++)
- printf("%" PRIu32 ": %" PRIu32 "\n", i, h48info[i+1]);
-
- free(buf);
-}
diff --git a/test/103_gendata_h48_h0/00_h_0.in b/test/103_gendata_h48_h0/00_h_0.in
diff --git a/test/103_gendata_h48/00_h_0.out b/test/103_gendata_h48_h0/00_h_0.out
diff --git a/test/103_gendata_h48_h0/gendata_h48_tests.c b/test/103_gendata_h48_h0/gendata_h48_tests.c
@@ -0,0 +1,33 @@
+#include "../test.h"
+
+#define MAXDEPTH 5
+#define COCSEPSIZE 1119792
+#define ETABLESIZE ((3393 * 495 * 70) >> 1)
+
+size_t gendata_h48h0k4(void *, uint8_t);
+
+void run(void) {
+ char str[STRLENMAX];
+ uint8_t i;
+ uint32_t *buf, *h48info;
+ size_t result;
+
+ fgets(str, STRLENMAX, stdin);
+ buf = (uint32_t *)malloc(sizeof(uint32_t) * 60000000);
+ result = gendata_h48h0k4(buf, MAXDEPTH);
+ h48info = buf + (ETABLESIZE + COCSEPSIZE) / 4;
+
+ printf("%zu\n\n", result);
+
+ printf("cocsepdata:\n");
+ printf("Classes: %" PRIu32 "\n", buf[COCSEPSIZE/4-12]);
+ printf("Max value: %" PRIu32 "\n", buf[COCSEPSIZE/4-11]);
+ for (i = 0; i < 10; i++)
+ printf("%" PRIu32 ": %" PRIu32 "\n", i, buf[COCSEPSIZE/4-10+i]);
+
+ printf("\nh48:\n");
+ for (i = 0; i < MAXDEPTH+1; i++)
+ printf("%" PRIu32 ": %" PRIu32 "\n", i, h48info[i+1]);
+
+ free(buf);
+}
diff --git a/tools/run_tool.sh b/tools/run_tool.sh
@@ -6,21 +6,29 @@ if [ -z "$TOOL" ]; then
fi
CC="cc -std=c99 -pedantic -Wall -Wextra \
- -Wno-unused-parameter -Wno-unused-function -O3 -D$CUBETYPE \
+ -Wno-unused-parameter -Wno-unused-function -D$CUBETYPE \
-D_POSIX_C_SOURCE=199309L"
+if [ -n "$DEBUG" ]; then
+ CC="$CC -fsanitize=address -g3"
+ CUBEOBJ="debugcube.o"
+else
+ CC="$CC -O3"
+ CUBEOBJ="cube.o"
+fi
+
[ "$CUBETYPE" = "CUBE_AVX2" ] && CC="$CC -mavx2"
BIN="tools/run"
-CUBEOBJ="cube.o"
d="$(date +'%Y-%m-%d-%H-%M-%S')"
for t in tools/*; do
if [ ! -d "$t" ] || [ -z "$(echo "$t" | grep "$TOOL")" ]; then
continue
fi
+ toolname="$(basename "$t" .c)"
$CC -o $BIN $t/*.c $CUBEOBJ || exit 1;
- $BIN
+ $BIN | tee "tools/results/$toolname-$d.txt"
break
done
diff --git a/tools/stats_tables_h48/stats_tables_h48.c b/tools/stats_tables_h48/stats_tables_h48.c
@@ -1,10 +1,13 @@
+#include <stdarg.h>
#include <time.h>
#include "../timerun.h"
#include "../../src/cube.h"
#define MAXMOVES 20
-#define NCUBES 1000
+#define NCUBES 10000
+#define LOG_EVERY (NCUBES / 20)
+const char *filename = "tables/h48h0k4";
char *buf;
uint64_t rand64(void) {
@@ -16,22 +19,18 @@ uint64_t rand64(void) {
return ret;
}
-void output(int64_t v[13][100]) {
-/* TODO: write to file and output only cocsepdata table stats */
+void log_stderr(const char *str, ...) {
+ va_list args;
+
+ va_start(args, str);
+ vfprintf(stderr, str, args);
+ va_end(args);
}
void run(void) {
- uint32_t *h48info;
- int i, j;
- char sols[13], cube[22];
- int64_t s, ep, eo, cp, co, v[13][100] = {0};
-
- s = nissy_gendata("H48stats", "", buf);
-
- if (s == -1) {
- printf("Error generating table\n");
- return;
- }
+ int i, j, k;
+ char sols[12], cube[22];
+ int64_t ep, eo, cp, co, v[12][100] = {0};
for (i = 0; i < NCUBES; i++) {
ep = rand64();
@@ -39,13 +38,53 @@ void run(void) {
cp = rand64();
co = rand64();
nissy_getcube(ep, eo, cp, co, "fix", cube);
- nissy_solve(cube, "H48stats",
- "", "", "", 0, MAXMOVES, 1, -1, buf, sols);
- for (j = 0; j < 13; j++)
+ nissy_solve(cube, "h48stats", "", "",
+ 0, MAXMOVES, 1, -1, buf, sols);
+ for (j = 0; j < 12; j++)
v[j][(int)sols[j]]++;
+ if ((i+1) % LOG_EVERY == 0)
+ fprintf(stderr, "%d cubes solved...\n", i+1);
}
- output(v);
+ for (j = 0; j < 12; j++) {
+ printf("Data for h=%d\n", j);
+ for (k = 0; k <= 16; k++)
+ printf("%d\t%" PRId64 "\n", k, v[j][k]);
+ printf("\n");
+ }
+}
+
+int getdata(int64_t size) {
+ int64_t s;
+ FILE *f;
+
+ buf = malloc(size);
+
+ if ((f = fopen(filename, "rb")) == NULL) {
+ fprintf(stderr, "Table file not found, generating them."
+ " This can take a while.\n");
+ s = nissy_gendata("h48stats", "", buf);
+ if (s != size) {
+ fprintf(stderr, "Error generating table");
+ if (s != -1)
+ fprintf(stderr, " (got %" PRId64 " bytes)", s);
+ fprintf(stderr, "\n");
+ return 1;
+ }
+ if ((f = fopen(filename, "wb")) == NULL) {
+ fprintf(stderr, "Could not write tables to file %s"
+ ", will be regenerated next time.\n", filename);
+ } else {
+ fwrite(buf, size, 1, f);
+ fclose(f);
+ }
+ } else {
+ fprintf(stderr, "Reading tables from file %s\n", filename);
+ fread(buf, size, 1, f);
+ fclose(f);
+ }
+
+ return 0;
}
int main() {
@@ -53,17 +92,21 @@ int main() {
srand(time(NULL));
- size = nissy_datasize("H48", OPTIONS);
+ nissy_setlogger(log_stderr);
+ size = nissy_datasize("h48stats", "");
if (size == -1) {
printf("h48 stats: error in datasize\n");
return 1;
}
- buf = malloc(size);
+ if (getdata(size) != 0) {
+ printf("Error getting table, stopping\n");
+ free(buf);
+ return 1;
+ }
timerun(run, "h48 table stats");
free(buf);
-
return 0;
}
