commit 425eee24421bf0a19c7e0199d2e3ecba3318c8f4
parent 4a16da26dacdb37b9ef8d3d11e10ecb94b0cf396
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Wed, 3 Jul 2024 17:15:24 +0200
Preparing for table stats
Diffstat:
6 files changed, 255 insertions(+), 7 deletions(-)
diff --git a/TODO.txt b/TODO.txt
@@ -1,7 +1,29 @@
+Check stats for all tables using H48stats solver
+ - implement gencube
+ - move cubefromarray from cube_io to where needed
+ - implement in cube_generic
+ - fix in cube_public
+ - add tests
+ - test shell
+ - optional: dr states (just to check options)
+ - implement tool for stats
+ - output to file, only write cocsep to stdout
+
+Bug in esep table generation
+ - Fails for UFRUFU, try command
+ ./run solve -solver H48 -options "2;20" -n 1 -M 10 -cube \
+ "$(./run frommoves -moves "UFRUFU")"
+ - Fundamental error in how tables are generated, each coordinate has too
+ many representative. I need to use the big table with the full coordinate
+ first (h=11, ~241 billion positions, 60Gb with k=2). From this the smaller
+ tables can be easily deduced.
+ - Investigate the possibility of computing smaller tables directly in some
+ other way, even if slow.
+ - use dfs for computing big table, save distance %3 until the last two steps,
+ then clean the table and double loop over moves to fill the value
+
Solver
- - fix and cleanup current implementation
- - fails for UFRUFU when using full table
- SOMETHING IS WRONG FOR coord_h48 = 3! (pvalue 15??)
+ - cleanup h48 solver
- do not copy dfsarg, change and undo
- implement and use premove (and test) instead of inverting
- benchmark for solve
diff --git a/shell.c b/shell.c
@@ -29,6 +29,7 @@ typedef struct {
int8_t maxmoves;
int8_t optimal;
int64_t maxsolutions;
+ uint8_t id[16];
} args_t;
static void print_cube_result(int64_t, char [static 22]);
@@ -40,6 +41,7 @@ static int64_t applymoves_exec(args_t *);
static int64_t applytrans_exec(args_t *);
static int64_t frommoves_exec(args_t *);
static int64_t convert_exec(args_t *);
+static int64_t gencube_exec(args_t *);
static int64_t datasize_exec(args_t *);
static int64_t gendata_exec(args_t *);
static int64_t solve_exec(args_t *);
@@ -63,6 +65,7 @@ static bool set_minmoves(int, char **, args_t *);
static bool set_maxmoves(int, char **, args_t *);
static bool set_optimal(int, char **, args_t *);
static bool set_maxsolutions(int, char **, args_t *);
+static bool set_id(int, char **, args_t *);
#define COMMAND(N, E) { .name = N, .exec = E }
struct {
@@ -75,6 +78,7 @@ struct {
COMMAND("applytrans", applytrans_exec),
COMMAND("frommoves", frommoves_exec),
COMMAND("convert", convert_exec),
+ COMMAND("gencube", gencube_exec),
COMMAND("datasize", datasize_exec),
COMMAND("gendata", gendata_exec),
COMMAND("solve", solve_exec),
@@ -102,6 +106,7 @@ struct {
OPTION("-M", 1, set_maxmoves),
OPTION("-O", 1, set_optimal),
OPTION("-n", 1, set_maxsolutions),
+ OPTION("-id", 16, set_id),
OPTION(NULL, 0, NULL)
};
@@ -215,6 +220,18 @@ convert_exec(args_t *args)
}
static int64_t
+gencube_exec(args_t *args)
+{
+ char result[PRINTCUBE_BUFFER_SIZE];
+ int64_t ret;
+
+ ret = nissy_gencube(args->id, args->str_options, result);
+ print_str_result(ret, result);
+
+ return ret;
+}
+
+static int64_t
datasize_exec(args_t *args)
{
int64_t ret;
@@ -551,6 +568,21 @@ set_maxsolutions(int argc, char **argv, args_t *args)
return parse_int64(argv[0], &args->maxsolutions);
}
+static bool
+set_id(int argc, char **argv, args_t *args)
+{
+ int i;
+ int64_t n;
+
+ for (i = 0; i < 16; i++) {
+ if (!parse_int64(argv[i], &n))
+ return false;
+ args->id[i] = (uint8_t)n;
+ }
+
+ return true;
+}
+
void log_stderr(const char *str, ...)
{
va_list args;
diff --git a/src/cube.h b/src/cube.h
@@ -41,6 +41,12 @@ int64_t nissy_convert(
char *result
);
+int64_t nissy_gencube(
+ uint8_t id[16],
+ const char *options,
+ char result[static 22]
+);
+
/*
Returns the size of the data generated by nissy_gendata, when called with
the same parameters, or -1 in case of error. The returned value can be
diff --git a/src/cube_public.h b/src/cube_public.h
@@ -105,6 +105,18 @@ nissy_convert(
}
int64_t
+nissy_gencube(
+ uint8_t id[16],
+ const char *options,
+ char result[static 22]
+)
+{
+ /* TODO: compute cube from id % (number of positions) */
+ /* options can be used for generating e.g. DR-state cube */
+ return -1;
+}
+
+int64_t
nissy_datasize(
const char *solver,
const char *options
@@ -131,6 +143,8 @@ nissy_gendata(
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);
} else {
LOG("gendata: implemented only for H48 solver\n");
ret = -1;
@@ -196,6 +210,8 @@ nissy_solve(
c, minmoves, maxmoves, maxsolutions,
(uint8_t)h, data, solutions);
ret = -1;
+ } else if (!strcmp(solver, "H48stats")) {
+ ret = solve_h48stats(c, maxmoves, data, solutions);
} else if (!strcmp(solver, "simple")) {
ret = solve_simple(
c, minmoves, maxmoves, maxsolutions, optimal, solutions);
diff --git a/src/solve_h48.h b/src/solve_h48.h
@@ -57,6 +57,15 @@ typedef struct {
char **nextsol;
} dfsarg_solveh48_t;
+typedef struct {
+ cube_t cube;
+ int8_t nmoves;
+ int8_t depth;
+ uint8_t moves[MAX_SOLUTION_LENGTH];
+ uint32_t *cocsepdata;
+ char *s;
+} dfsarg_solveh48stats_t;
+
_static_inline int64_t coord_h48(cube_t, const uint32_t *, uint8_t);
_static_inline int64_t coord_h48_edges(cube_t, int64_t, uint8_t, uint8_t);
_static_inline cube_t invcoord_h48(int64_t, const cube_t *, uint8_t);
@@ -78,6 +87,9 @@ _static_inline bool solve_h48_stop(dfsarg_solveh48_t *);
_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_inline int64_t
coord_h48(cube_t c, const uint32_t *cocsepdata, uint8_t h)
{
@@ -104,9 +116,15 @@ coord_h48_edges(cube_t c, int64_t coclass, uint8_t t, uint8_t h)
d = transform_edges(c, t);
esep = coord_esep(d);
eo = coord_eo(d);
- edges = (esep << (int64_t)h) + (eo >> (11 - (int64_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;
+*/
}
/*
@@ -160,7 +178,8 @@ gendata_cocsep(void *buf, uint64_t *selfsim, cube_t *rep)
buf32 = (uint32_t *)buf;
info = buf32 + COCSEP_TABLESIZE;
memset(buf32, 0xFF, sizeof(uint32_t) * COCSEP_TABLESIZE);
- memset(selfsim, 0, sizeof(uint64_t) * COCSEP_CLASSES);
+ if (selfsim != NULL)
+ memset(selfsim, 0, sizeof(uint64_t) * COCSEP_CLASSES);
arg = (dfsarg_cocsep_t) {
.cube = solved,
@@ -221,7 +240,8 @@ gendata_cocsep_dfs(dfsarg_cocsep_t *arg)
d = transform_corners(arg->cube, t);
j = coord_cocsep(d);
is = (i == j);
- arg->selfsim[*arg->n] |= is << t;
+ if (arg->selfsim != NULL)
+ arg->selfsim[*arg->n] |= is << t;
set_visited(arg->visited, j);
tinv = inverse_trans(t);
olddepth = (uint8_t)(arg->buf32[j] & 0xFF);
@@ -232,7 +252,8 @@ gendata_cocsep_dfs(dfsarg_cocsep_t *arg)
depth = (uint32_t)arg->depth;
arg->buf32[j] = class | ttrep | depth;
}
- arg->rep[*arg->n] = arg->cube;
+ if (arg->rep != NULL)
+ arg->rep[*arg->n] = arg->cube;
(*arg->n)++;
return cc;
@@ -525,3 +546,85 @@ 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.
+*/
+_static int64_t
+solve_h48stats_dfs(dfsarg_solveh48stats_t *arg)
+{
+ int8_t bound, u;
+ uint8_t m;
+ uint32_t d;
+ int64_t coord, h;
+ dfsarg_solveh48stats_t nextarg;
+
+ 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];
+
+ 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];
+ }
+
+ if (arg->s[12] != 99)
+ return 0;
+
+ nextarg = *arg;
+ nextarg.nmoves = arg->nmoves + 1;
+ for (m = 0; m < 18; m++) {
+ nextarg.moves[arg->nmoves] = m;
+ if (!allowednextmove(nextarg.moves, nextarg.nmoves)) {
+ /* If a move is not allowed, neither are its 180
+ * and 270 degree variations */
+ m += 2;
+ continue;
+ }
+ nextarg.cube = move(arg->cube, m);
+ solve_h48stats_dfs(&nextarg);
+ }
+
+ return 0;
+}
+
+_static int64_t
+solve_h48stats(
+ cube_t cube,
+ int8_t maxmoves,
+ const void *data,
+ char solutions[static 13]
+)
+{
+ int i;
+ dfsarg_solveh48stats_t arg;
+
+ arg = (dfsarg_solveh48stats_t) {
+ .cube = cube,
+ .cocsepdata = (uint32_t *)data,
+ .s = solutions
+ };
+
+ for (i = 0; i < 13; i++)
+ solutions[i] = (char)99;
+
+ for (arg.depth = 0;
+ arg.depth <= maxmoves && solutions[12] == 99;
+ arg.depth++)
+ {
+ arg.nmoves = 0;
+ solve_h48stats_dfs(&arg);
+ }
+
+ return 0;
+}
diff --git a/tools/stats_tables_h48/stats_tables_h48.c b/tools/stats_tables_h48/stats_tables_h48.c
@@ -0,0 +1,69 @@
+#include <time.h>
+#include "../timerun.h"
+#include "../../src/cube.h"
+
+#define MAXMOVES 20
+#define NCUBES 1000
+
+typedef struct { uint8_t n[16]; } i128;
+
+char *buf;
+
+i128 rand128(void) {
+ uint8_t i, j;
+ i128 ret = {0};
+
+ for (i = 0; i < 16; i++)
+ for (j = 0; j < 8; j++)
+ ret.n[i] |= (uint8_t)(rand() % 2) << j;
+
+ return ret;
+}
+
+void output(int64_t v[13][100]) {
+/* TODO: write to file and output only cocsepdata table stats */
+}
+
+void run(void) {
+ uint32_t *h48info;
+ int i, j;
+ char sols[13], cube[22];
+ int64_t s, v[13][100] = {0};
+
+ s = nissy_gendata("H48stats", "", buf);
+
+ if (s == -1) {
+ printf("Error generating table\n");
+ return;
+ }
+
+ for (i = 0; i < NCUBES; i++) {
+ nissy_gencube(rand128(), "", cube);
+ nissy_solve(cube, "H48stats",
+ "", "", "", 0, MAXMOVES, 1, -1, buf, sols);
+ for (j = 0; j < 13; j++)
+ v[j][(int)sols[j]]++;
+ }
+
+ output(v);
+}
+
+int main() {
+ int64_t size;
+
+ srand(time(NULL));
+
+ size = nissy_datasize("H48", OPTIONS);
+ if (size == -1) {
+ printf("h48 stats: error in datasize\n");
+ return 1;
+ }
+
+ buf = malloc(size);
+
+ timerun(run, "h48 table stats");
+
+ free(buf);
+
+ return 0;
+}
