6 files changed, 255 insertions, 7 deletions

diff --git a/TODO.txt b/TODO.txt
index 6f212c3..86c48fd 100644
--- 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
index 5cd8fb2..03618de 100644
--- 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
index b5eb615..d3d096a 100644
--- 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
index a1c4b90..fe003c9 100644
--- 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
index 201c7c6..c2c541d 100644
--- 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
new file mode 100644
index 0000000..9f9bacf
--- /dev/null
+++ 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;
+}