Added a solver, but found out h48 table is broken

10 files changed, 265 insertions, 60 deletions

diff --git a/.gitignore b/.gitignore
index ce4229b..16439b4 100644
--- a/.gitignore
+++ b/.gitignore
@@ -5,6 +5,7 @@ gen
 debuggen
 perf.data
 perf.data.old
+run
 tables/*
 test/*/runtest
 test/run
diff --git a/Makefile b/Makefile
index 5859eca..43bc3e4 100644
--- a/Makefile
+++ b/Makefile
@@ -24,4 +24,8 @@ shell: cube.o
         mkdir -p tables
         ${CC} ${CFLAGS} -o run cube.o shell.c
 
-.PHONY: all clean test benchmark shell
+debugshell: debugcube.o
+        mkdir -p tables
+        ${CC} ${DBGFLAGS} -o run debugcube.o shell.c
+
+.PHONY: all clean test benchmark shell debugshell
diff --git a/README.md b/README.md
index 71015b0..098b960 100644
--- a/README.md
+++ b/README.md
@@ -27,3 +27,20 @@ $ TEST=coord make test
 ```
 
 Due to ongoing changes, benchmarks are currently broken.
+
+## Solving
+
+Notes for myself while this is work in progress
+
+```
+$ make shell
+$ ./run frommoves -moves (scramble)
+```
+
+copy the result, then
+
+```
+$ ./run solve -solver "H48" -options "2;20" -n 1 -M 10 -cube (paste here)
+```
+
+Options can be changed from `2;20` to `n;20` for larger tables.
diff --git a/TODO.txt b/TODO.txt
index befedff..6f212c3 100644
--- a/TODO.txt
+++ b/TODO.txt
@@ -1,8 +1,16 @@
 Solver
-  - write a solver (how many tricks? some, but not all are needed)
+  - fix and cleanup current implementation
+        - fails for UFRUFU when using full table
+          SOMETHING IS WRONG FOR coord_h48 = 3! (pvalue 15??)
+        - do not copy dfsarg, change and undo
+        - implement and use premove (and test) instead of inverting
   - benchmark for solve
     table generation, where to keep tables? in benchmark folder or in tables/?
+  - more tricks for solver, optimize, try larger tables
   - remove solve_simple and maybe the whole solve_generic
+  - shell: silently accept other formats too?
+  - shell: allow generating multiple tables for different options
+  - gendata: move info at start of tables?
 
 Cleanup cube_public and interface
   - remove options, use only solver name
@@ -17,6 +25,8 @@ Goal: find out which k value is best
 
 Improvements
   - check hash of generated data
+  - use interleaved tables (e.g. big table with k=2 or k=1 and interleaved
+    small table with k=4 for better backup pruning)
 
 ## H48 optimal solver (some has already been implemented)
 
diff --git a/shell.c b/shell.c
index 1b8b70e..5cd8fb2 100644
--- a/shell.c
+++ b/shell.c
@@ -1,5 +1,6 @@
 #include <inttypes.h>
 #include <errno.h>
+#include <stdarg.h>
 #include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -28,7 +29,6 @@ typedef struct {
         int8_t maxmoves;
         int8_t optimal;
         int64_t maxsolutions;
-        int64_t datasize; /* Option for gendata + solve, TODO change? */
 } args_t;
 
 static void print_cube_result(int64_t, char [static 22]);
@@ -39,9 +39,7 @@ static int64_t inverse_exec(args_t *);
 static int64_t applymoves_exec(args_t *);
 static int64_t applytrans_exec(args_t *);
 static int64_t frommoves_exec(args_t *);
-static int64_t readcube_exec(args_t *);
-static int64_t writecube_exec(args_t *);
-static int64_t convertcube_exec(args_t *);
+static int64_t convert_exec(args_t *);
 static int64_t datasize_exec(args_t *);
 static int64_t gendata_exec(args_t *);
 static int64_t solve_exec(args_t *);
@@ -76,9 +74,7 @@ struct {
         COMMAND("applymoves", applymoves_exec),
         COMMAND("applytrans", applytrans_exec),
         COMMAND("frommoves", frommoves_exec),
-        COMMAND("readcube", readcube_exec),
-        COMMAND("writecube", writecube_exec),
-        COMMAND("convertcube", convertcube_exec),
+        COMMAND("convert", convert_exec),
         COMMAND("datasize", datasize_exec),
         COMMAND("gendata", gendata_exec),
         COMMAND("solve", solve_exec),
@@ -199,43 +195,19 @@ frommoves_exec(args_t *args)
         char result[22];
         int64_t ret;
 
-        ret = nissy_frommoves(args->str_trans, result);
+        ret = nissy_frommoves(args->str_moves, result);
         print_cube_result(ret, result);
 
         return ret;
 }
 
 static int64_t
-readcube_exec(args_t *args)
-{
-        char result[22];
-        int64_t ret;
-
-        ret = nissy_readcube(args->str_format, args->str_cube, result);
-        print_cube_result(ret, result);
-
-        return ret;
-}
-
-static int64_t
-writecube_exec(args_t *args)
-{
-        char result[PRINTCUBE_BUFFER_SIZE];
-        int64_t ret;
-
-        ret = nissy_writecube(args->str_format, args->str_cube, result);
-        print_str_result(ret, result);
-
-        return ret;
-}
-
-static int64_t
-convertcube_exec(args_t *args)
+convert_exec(args_t *args)
 {
         char result[PRINTCUBE_BUFFER_SIZE];
         int64_t ret;
 
-        ret = nissy_convertcube(
+        ret = nissy_convert(
             args->str_format_in, args->str_format_out, args->str_cube, result);
         print_str_result(ret, result);
 
@@ -275,14 +247,17 @@ gendata_exec(args_t *args)
 
         if (tablepaths[i] == NULL) {
                 fprintf(stderr, "Cannot write data to file\n");
+                fclose(file);
                 return -2;
         }
 
         size = nissy_datasize(args->str_solver, args->str_options);
+
         if (size < 0) {
                 fprintf(stderr,
                     "Unknown error in retrieving data size"
                     "(make sure solver is valid)\n");
+                fclose(file);
                 return -3;
         }
 
@@ -291,19 +266,23 @@ gendata_exec(args_t *args)
         ret = nissy_gendata(args->str_solver, args->str_options, buf);
         if (ret < 0) {
                 fprintf(stderr, "Unknown error in generating data\n");
+                fclose(file);
                 free(buf);
                 return -4;
         }
         if (ret != size) {
-                fprintf(stderr, "Unknown error: unexpected data size\n");
+                fprintf(stderr, "Unknown error: unexpected data size "
+                                 "(got %zu, expected %zu)\n", ret, size);
+                fclose(file);
                 free(buf);
                 return -5;
         }
 
         written = fwrite(buf, size, 1, file);
+        fclose(file);
         free(buf);
 
-        if (written != (int64_t)size) {
+        if (written != 1) {
                 fprintf(stderr,
                     "Error: data was generated correctly, but could not be "
                     "written to file (generated %" PRId64 " bytes, written "
@@ -311,7 +290,6 @@ gendata_exec(args_t *args)
                 return -6;
         }
 
-        args->datasize = size;
         fprintf(stderr, "Data written to %s\n", path);
 
         return 0;
@@ -323,7 +301,7 @@ solve_exec(args_t *args)
         int i;
         FILE *file;
         char *buf, solutions[SOLUTIONS_BUFFER_SIZE], path[MAX_PATH_LENGTH];
-        int64_t ret, gendata_ret;
+        int64_t ret, gendata_ret, size;
         size_t read;
 
         for (i = 0; tablepaths[i] != NULL; i++) {
@@ -344,23 +322,30 @@ solve_exec(args_t *args)
         }
 
         /* Ugh, this is not elegant TODO */
-        for (i = 0; tablepaths[i] != NULL; i++) {
-                strcpy(path, tablepaths[i]);
-                strcat(path, args->str_solver);
-                file = fopen(path, "rb");
-                if (file != NULL)
-                        break;
+        if (file == NULL) {
+                for (i = 0; tablepaths[i] != NULL; i++) {
+                        strcpy(path, tablepaths[i]);
+                        strcat(path, args->str_solver);
+                        file = fopen(path, "rb");
+                        if (file != NULL)
+                                break;
+                }
         }
 
         if (tablepaths[i] == NULL) {
                 fprintf(stderr, "Error: data file not found\n");
+                fclose(file);
                 return -1;
         }
 
-        buf = malloc(args->datasize);
-        read = fread(buf, args->datasize, 1, file);
-        if (read != args->datasize) {
-                fprintf(stderr, "Error reading data from file\n");
+        size = nissy_datasize(args->str_solver, args->str_options);
+        buf = malloc(size);
+        read = fread(buf, size, 1, file);
+        fclose(file);
+        if (read != 1) {
+                fprintf(stderr, "Error reading data from file: "
+                    "fread() returned %zu instead of 1 when attempting to"
+                    "read %" PRId64 " bytes from file %s\n", read, size, path);
                 return -2;
         }
 
@@ -413,7 +398,7 @@ parse_args(int argc, char **argv, args_t *args)
                                     options[j].name);
                                 return 1;
                         }
-                        if (!options[j].set(n, argv+i, args)) {
+                        if (!options[j].set(n, argv+i+1, args)) {
                                 fprintf(stderr,
                                     "Error parsing arguments for option %s\n",
                                     options[j].name);
@@ -448,7 +433,8 @@ parse_int64(char *argv, int64_t *result)
 {
         *result = strtoll(argv, NULL, 10);
 
-        return errno != 0;
+        /* TODO: figure out how errno works and use it */
+        return true;
 }
 
 static bool
@@ -565,11 +551,22 @@ set_maxsolutions(int argc, char **argv, args_t *args)
         return parse_int64(argv[0], &args->maxsolutions);
 }
 
+void log_stderr(const char *str, ...)
+{
+        va_list args;
+
+        va_start(args, str);
+        vfprintf(stderr, str, args);
+        va_end(args);
+}
+
 int main(int argc, char **argv)
 {
         int parse_error;
         args_t args;
 
+        nissy_setlogger(log_stderr);
+
         parse_error = parse_args(argc-1, argv+1, &args);
         if (parse_error)
                 return parse_error;
diff --git a/src/cube_public.h b/src/cube_public.h
index ea1d28d..a1c4b90 100644
--- a/src/cube_public.h
+++ b/src/cube_public.h
@@ -89,7 +89,7 @@ nissy_frommoves(
 }
 
 int64_t
-nissy_convertcube(
+nissy_convert(
         const char *format_in,
         const char *format_out,
         const char *cube_string,
@@ -155,6 +155,7 @@ nissy_solve(
 {
         cube_t c;
         int64_t ret;
+        int h;
 
         c = readcube_B32(cube);
 
@@ -188,8 +189,12 @@ nissy_solve(
                 return -1;
         }
 
-        if (!strcmp(solver, "h48")) {
-                LOG("h48 solver not implemented yet\n");
+        /* TODO define and use solve_options_t */
+        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, "simple")) {
                 ret = solve_simple(
diff --git a/src/solve_generic.h b/src/solve_generic.h
index d1d1469..41d995a 100644
--- a/src/solve_generic.h
+++ b/src/solve_generic.h
@@ -21,7 +21,7 @@ solve_generic_appendsolution(dfsarg_generic_t *arg)
 {
         int strl;
 
-        strl = writemoves(arg->moves, arg->depth, *arg->nextsol);
+        strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol);
         LOG("Solution found: %s\n", *arg->nextsol);
         *arg->nextsol += strl;
         **arg->nextsol = '\n';
@@ -53,7 +53,6 @@ solve_generic_dfs(dfsarg_generic_t *arg)
                 return 1;
         }
 
-        /* memcpy(&nextarg, arg, sizeof(dfsarg_generic_t)); */
         nextarg = *arg;
         nextarg.nmoves = arg->nmoves + 1;
         for (m = 0, ret = 0; m < 18; m++) {
diff --git a/src/solve_h48.h b/src/solve_h48.h
index 1646f49..201c7c6 100644
--- a/src/solve_h48.h
+++ b/src/solve_h48.h
@@ -11,6 +11,8 @@
 #define COCLASS(x)            (((x) & COCLASS_MASK) >> UINT32_C(16))
 #define TTREP_MASK            (UINT32_C(0xFF) << UINT32_C(8))
 #define TTREP(x)              (((x) & TTREP_MASK) >> UINT32_C(8))
+#define CBOUND_MASK           UINT32_C(0xFF)
+#define CBOUND(x)             ((x) & CBOUND_MASK)
 #define H48_ESIZE(h)          ((_12c4 * _8c4) << (int64_t)(h))
 
 #define ESEP_IND(i)           ((uint32_t)(i) / UINT32_C(8))
@@ -19,6 +21,8 @@
 #define VISITED_IND(i)        ((uint32_t)(i) / UINT32_C(8))
 #define VISITED_MASK(i)       (UINT32_C(1) << ((uint32_t)(i) % UINT32_C(8)))
 
+#define MAX_SOLUTION_LENGTH 20
+
 typedef struct {
         cube_t cube;
         uint8_t depth;
@@ -39,6 +43,20 @@ typedef struct {
         cube_t *crep;
 } bfsarg_esep_t;
 
+typedef struct {
+        cube_t cube;
+        cube_t inverse;
+        int8_t nmoves;
+        int8_t depth;
+        uint8_t moves[MAX_SOLUTION_LENGTH];
+        int64_t *nsols;
+        int64_t maxsolutions;
+        uint8_t h;
+        uint32_t *cocsepdata;
+        uint32_t *h48data;
+        char **nextsol;
+} dfsarg_solveh48_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);
@@ -53,6 +71,13 @@ _static_inline void set_visited(uint8_t *, int64_t);
 _static_inline uint8_t get_esep_pval(const uint32_t *, int64_t);
 _static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t);
 
+_static void solve_h48_appendsolution(dfsarg_solveh48_t *);
+_static_inline int8_t get_h48_cdata(cube_t, uint32_t *, uint32_t *);
+_static_inline int8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint32_t *);
+_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_inline int64_t
 coord_h48(cube_t c, const uint32_t *cocsepdata, uint8_t h)
 {
@@ -238,8 +263,11 @@ gendata_h48(void *buf, uint8_t h, uint8_t maxdepth)
         cube_t crep[COCSEP_CLASSES];
         size_t cocsepsize, infosize;
 
+        /* TODO: move info at start of tables (all tables!) */
         infosize = 4 * maxdepth;
         cocsepsize = gendata_cocsep(buf, selfsim, crep);
+        infosize = 88;
+
         if (buf == NULL)
                 goto gendata_h48_return_size;
 
@@ -272,7 +300,6 @@ gendata_h48(void *buf, uint8_t h, uint8_t maxdepth)
         }
 
         info[0] = arg.depth-1;
-        infosize = 4 * (size_t)(info[0] + 2);
 
         LOG("h48 pruning table computed\n");
         LOG("Maximum pruning value: %" PRIu32 "\n", info[0]);
@@ -353,3 +380,148 @@ set_esep_pval(uint32_t *buf32, int64_t i, uint8_t val)
         buf32[ESEP_IND(i)] =
             (buf32[ESEP_IND(i)] & (~ESEP_MASK(i))) | (val << ESEP_SHIFT(i));
 }
+
+_static void
+solve_h48_appendsolution(dfsarg_solveh48_t *arg)
+{
+        int strl;
+
+        strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol);
+        LOG("Solution found: %s\n", *arg->nextsol);
+        *arg->nextsol += strl;
+        **arg->nextsol = '\n';
+        (*arg->nextsol)++;
+        (*arg->nsols)++;
+}
+
+_static_inline int8_t
+get_h48_cdata(cube_t cube, uint32_t *cocsepdata, uint32_t *cdata)
+{
+        int64_t coord;
+
+        coord = coord_cocsep(cube);
+        *cdata = cocsepdata[coord];
+
+        return CBOUND(*cdata);
+}
+
+_static_inline int8_t
+get_h48_bound(cube_t cube, uint32_t cdata, uint8_t h, uint32_t *h48data)
+{
+        int64_t coord;
+
+        coord = coord_h48_edges(cube, COCLASS(cdata), TTREP(cdata), h);
+        return get_esep_pval(h48data, coord);
+}
+
+_static_inline bool
+solve_h48_stop(dfsarg_solveh48_t *arg)
+{
+        uint32_t data, data_inv;
+        int8_t bound;
+
+        bound = get_h48_cdata(arg->cube, arg->cocsepdata, &data);
+        if (bound + arg->nmoves > arg->depth)
+                return true;
+
+        bound = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv);
+        if (bound + arg->nmoves > arg->depth)
+                return true;
+
+/*
+        bound = get_h48_bound(arg->cube, data, arg->h, arg->h48data);
+LOG("Using pval %" PRId8 "\n", bound);
+        if (bound + arg->nmoves > arg->depth)
+                return true;
+
+        bound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->h48data);
+        if (bound + arg->nmoves > arg->depth)
+                return true;
+*/
+
+        return false;
+}
+
+_static int64_t
+solve_h48_dfs(dfsarg_solveh48_t *arg)
+{
+        dfsarg_solveh48_t nextarg;
+        int64_t ret;
+        uint8_t m;
+
+        if (*arg->nsols == arg->maxsolutions)
+                return 0;
+
+        if (solve_h48_stop(arg))
+                return 0;
+
+        if (issolved(arg->cube)) {
+                if (arg->nmoves != arg->depth)
+                        return 0;
+                solve_h48_appendsolution(arg);
+                return 1;
+        }
+
+        /* TODO: avoid copy, change arg and undo changes after recursion */
+        nextarg = *arg;
+        nextarg.nmoves = arg->nmoves + 1;
+        ret = 0;
+        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);
+                nextarg.inverse = inverse(nextarg.cube); /* TODO: use premove */
+                ret += solve_h48_dfs(&nextarg);
+        }
+
+        return ret;
+}
+
+_static int64_t
+solve_h48(
+        cube_t cube,
+        int8_t minmoves,
+        int8_t maxmoves,
+        int8_t maxsolutions,
+        uint8_t h,
+        const void *data,
+        char *solutions
+)
+{
+        int64_t nsols;
+        dfsarg_solveh48_t arg;
+
+        arg = (dfsarg_solveh48_t) {
+                .cube = cube,
+                .inverse = inverse(cube),
+                .nsols = &nsols,
+                .maxsolutions = maxsolutions,
+                .h = h,
+                .cocsepdata = (uint32_t *)data,
+                .h48data = ((uint32_t *)data) + COCSEP_FULLSIZE / 4,
+                .nextsol = &solutions
+        };
+
+        nsols = 0;
+        for (arg.depth = minmoves;
+             arg.depth <= maxmoves && nsols < maxsolutions;
+             arg.depth++)
+        {
+                LOG("Found %" PRId64 " solutions, searching at depth %"
+                    PRId8 "\n", nsols, arg.depth);
+                arg.nmoves = 0;
+                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;
+}
diff --git a/test/103_gendata_h48/00_h_0.out b/test/103_gendata_h48/00_h_0.out
index db6e121..cc5cf9b 100644
--- a/test/103_gendata_h48/00_h_0.out
+++ b/test/103_gendata_h48/00_h_0.out
@@ -1,4 +1,4 @@
-59903545
+59903605
 
 cocsepdata:
 Classes: 3393
diff --git a/test/103_gendata_h48/01_h_1.out b/test/103_gendata_h48/01_h_1.out
index 456305d..bd0931c 100644
--- a/test/103_gendata_h48/01_h_1.out
+++ b/test/103_gendata_h48/01_h_1.out
@@ -1,4 +1,4 @@
-118687270
+118687330
 
 cocsepdata:
 Classes: 3393