Merge pull request #2 from enricotenuti/master

nissbranch ver1

25 files changed, 302 insertions, 70 deletions

diff --git a/.gitignore b/.gitignore
index 5fb5b1f..c2ff877 100644
--- a/.gitignore
+++ b/.gitignore
@@ -8,6 +8,7 @@ tables/*
 test/*/runtest
 test/run
 test/run.DSYM
+run.DSYM
 test/last.*
 tools/results
 .vscode
diff --git a/src/core/cube.h b/src/core/cube.h
index fe36f90..4b28103 100644
--- a/src/core/cube.h
+++ b/src/core/cube.h
@@ -13,11 +13,13 @@ _static cube_t frommoves(const char *);
 _static void getcube_fix(int64_t *, int64_t *, int64_t *, int64_t *);
 _static cube_t getcube(int64_t, int64_t, int64_t, int64_t);
 
-_static cube_t move(cube_t, uint8_t);
 _static cube_t transform_edges(cube_t, uint8_t);
 _static cube_t transform_corners(cube_t, uint8_t);
 _static cube_t transform(cube_t, uint8_t);
 
+/* declared in moves.h */
+_static cube_t move(cube_t, uint8_t);
+
 _static cube_t
 cubefromarray(uint8_t c[static 8], uint8_t e[static 12])
 {
@@ -239,52 +241,6 @@ applytrans(cube_t cube, const char *buf)
         return transform(cube, t);
 }
 
-_static cube_t
-move(cube_t c, uint8_t m)
-{
-        switch (m) {
-        case _move_U:
-                return _move(U, c);
-        case _move_U2:
-                return _move(U2, c);
-        case _move_U3:
-                return _move(U3, c);
-        case _move_D:
-                return _move(D, c);
-        case _move_D2:
-                return _move(D2, c);
-        case _move_D3:
-                return _move(D3, c);
-        case _move_R:
-                return _move(R, c);
-        case _move_R2:
-                return _move(R2, c);
-        case _move_R3:
-                return _move(R3, c);
-        case _move_L:
-                return _move(L, c);
-        case _move_L2:
-                return _move(L2, c);
-        case _move_L3:
-                return _move(L3, c);
-        case _move_F:
-                return _move(F, c);
-        case _move_F2:
-                return _move(F2, c);
-        case _move_F3:
-                return _move(F3, c);
-        case _move_B:
-                return _move(B, c);
-        case _move_B2:
-                return _move(B2, c);
-        case _move_B3:
-                return _move(B3, c);
-        default:
-                LOG("move error, unknown move\n");
-                return zero;
-        }
-}
-
 /*
 TODO transform is now relegated to a separated file because it is too long.
 It would be nice to make it shorter without loosing performance.
diff --git a/src/core/moves.h b/src/core/moves.h
index 7da6405..8f9c8f5 100644
--- a/src/core/moves.h
+++ b/src/core/moves.h
@@ -1,7 +1,23 @@
+/* probably these can be placed in constants file */
+#define NORMAL 0x00
+#define INVERSE 0x01
+#define INVERSEBRANCH 0x03
+#define NORMALBRANCH 0x02
+#define ALLMOVES 0x3FFFF
+#define NOHALFTURNS 0x2DB6D
+
 _static_inline bool allowednextmove(uint8_t *, uint8_t);
+_static uint32_t allowednextmoveH48(uint8_t *, uint8_t, uint32_t);
+
 _static_inline uint8_t inverse_trans(uint8_t);
 _static_inline uint8_t movebase(uint8_t);
 _static_inline uint8_t moveaxis(uint8_t);
+_static_inline uint32_t disable_moves(uint32_t, uint8_t);
+
+_static cube_t move(cube_t, uint8_t);
+_static cube_t premove(cube_t, uint8_t);
+_static uint8_t inverse_move(uint8_t);
+_static uint8_t* invertpremoves(uint8_t *, uint8_t);
 
 _static bool
 allowednextmove(uint8_t *moves, uint8_t n)
@@ -28,6 +44,40 @@ allowednextmove(uint8_t *moves, uint8_t n)
         return axis[1] != axis[2] || base[0] != base[2];
 }
 
+_static_inline uint32_t 
+disable_moves(uint32_t current_result, uint8_t base_index)
+{
+        return current_result & ~(7 << base_index);
+}
+
+_static uint32_t
+allowednextmoveH48(uint8_t *moves, uint8_t n, uint32_t h48branch)
+{
+        uint32_t result = ALLMOVES;
+        if (h48branch & NORMALBRANCH)
+                result &= NOHALFTURNS;
+        if (n < 1)
+                return result;
+
+        uint8_t base1 = movebase(moves[n-1]);
+        uint8_t axis1 = moveaxis(moves[n-1]);
+
+        result = disable_moves(result, base1 * 3);
+        if (base1 % 2)
+                result = disable_moves(result, (base1 - 1) * 3);
+
+        if (n == 1)
+                return result;
+        
+        uint8_t base2 = movebase(moves[n-2]);
+        uint8_t axis2 = moveaxis(moves[n-2]);
+
+        if(axis1 == axis2)
+                result = disable_moves(result, base2 * 3);
+
+        return result;
+}
+
 _static_inline uint8_t
 inverse_trans(uint8_t t)
 {
@@ -45,3 +95,116 @@ moveaxis(uint8_t move)
 {
         return move / 6;
 }
+
+_static cube_t
+move(cube_t c, uint8_t m)
+{
+        switch (m) {
+        case _move_U:
+                return _move(U, c);
+        case _move_U2:
+                return _move(U2, c);
+        case _move_U3:
+                return _move(U3, c);
+        case _move_D:
+                return _move(D, c);
+        case _move_D2:
+                return _move(D2, c);
+        case _move_D3:
+                return _move(D3, c);
+        case _move_R:
+                return _move(R, c);
+        case _move_R2:
+                return _move(R2, c);
+        case _move_R3:
+                return _move(R3, c);
+        case _move_L:
+                return _move(L, c);
+        case _move_L2:
+                return _move(L2, c);
+        case _move_L3:
+                return _move(L3, c);
+        case _move_F:
+                return _move(F, c);
+        case _move_F2:
+                return _move(F2, c);
+        case _move_F3:
+                return _move(F3, c);
+        case _move_B:
+                return _move(B, c);
+        case _move_B2:
+                return _move(B2, c);
+        case _move_B3:
+                return _move(B3, c);
+        default:
+                LOG("move error, unknown move\n");
+                return zero;
+        }
+}
+
+_static cube_t
+premove(cube_t c, uint8_t m)
+{
+        switch (m) {
+        case _move_U:
+                return _premove(U3, c);
+        case _move_U2:
+                return _premove(U2, c);
+        case _move_U3:
+                return _premove(U, c);
+        case _move_D:
+                return _premove(D3, c);
+        case _move_D2:
+                return _premove(D2, c);
+        case _move_D3:
+                return _premove(D, c);
+        case _move_R:
+                return _premove(R3, c);
+        case _move_R2:
+                return _premove(R2, c);
+        case _move_R3:
+                return _premove(R, c);
+        case _move_L:
+                return _premove(L3, c);
+        case _move_L2:
+                return _premove(L2, c);
+        case _move_L3:
+                return _premove(L, c);
+        case _move_F:
+                return _premove(F3, c);
+        case _move_F2:
+                return _premove(F2, c);
+        case _move_F3:
+                return _premove(F, c);
+        case _move_B:
+                return _premove(B3, c);
+        case _move_B2:
+                return _premove(B2, c);
+        case _move_B3:
+                return _premove(B, c);
+        default:
+                LOG("move error, unknown move\n");
+                return zero;
+        }
+}
+
+_static uint8_t
+inverse_move(uint8_t m)
+{
+        return m - 2 * (m % 3) + 2;     
+}
+
+_static uint8_t*
+invertpremoves(uint8_t *moves, uint8_t nmoves)
+{
+        uint8_t i;
+        uint8_t *ret = malloc(nmoves * sizeof(uint8_t));
+
+        for (i = 0; i < nmoves; i++)
+                ret[i] = inverse_move(moves[i]);
+
+        // invert elements in the array
+        for (i = 0; i < nmoves / 2; i++)
+                _swap(ret[i], ret[nmoves - i - 1]);
+        return ret;
+}
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
index 0843792..bbe59e5 100644
--- a/src/solvers/h48/solve.h
+++ b/src/solvers/h48/solve.h
@@ -11,6 +11,9 @@ typedef struct {
         uint32_t *cocsepdata;
         uint32_t *h48data;
         char **nextsol;
+        uint8_t nissbranch;
+        int8_t npremoves;
+        uint8_t premoves[MAXLEN];
 } dfsarg_solveh48_t;
 
 typedef struct {
@@ -26,8 +29,7 @@ typedef struct {
 _static void solve_h48_appendsolution(dfsarg_solveh48_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, uint8_t, const void *, char *);
+_static int64_t solve_h48(cube_t, int8_t, int8_t, int8_t, uint8_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 12]);
@@ -36,10 +38,22 @@ _static void
 solve_h48_appendsolution(dfsarg_solveh48_t *arg)
 {
         int strl;
+        char *solution = *arg->nextsol; 
 
         strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol);
-        LOG("Solution found: %s\n", *arg->nextsol);
-        *arg->nextsol += strl;
+        *arg->nextsol += strl; 
+
+        if (arg->npremoves) {
+                **arg->nextsol = ' ';
+                (*arg->nextsol)++;
+
+                uint8_t* invertedpremoves = invertpremoves(arg->premoves, arg->npremoves);
+                strl = writemoves(invertedpremoves, arg->npremoves, *arg->nextsol);
+                free(invertedpremoves);
+                *arg->nextsol += strl;
+        }
+        LOG("Solution found: %s\n", solution);
+
         **arg->nextsol = '\n';
         (*arg->nextsol)++;
         (*arg->nsols)++;
@@ -51,24 +65,27 @@ solve_h48_stop(dfsarg_solveh48_t *arg)
         uint32_t data, data_inv;
         int8_t bound;
 
+        arg->nissbranch = NORMAL;
         bound = get_h48_cdata(arg->cube, arg->cocsepdata, &data);
-        if (bound + arg->nmoves > arg->depth)
+        if (bound + arg->nmoves + arg->npremoves > arg->depth)
                 return true;
 
         bound = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv);
-        if (bound + arg->nmoves > arg->depth)
+        if (bound + arg->nmoves + arg->npremoves > arg->depth)
                 return true;
 
-/*
         bound = get_h48_bound(arg->cube, data, arg->h, arg->k, arg->h48data);
-LOG("Using pval %" PRId8 "\n", bound);
-        if (bound + arg->nmoves > arg->depth)
+        // LOG("Using pval %" PRId8 "\n", bound);
+        if (bound + arg->nmoves + arg->npremoves > arg->depth)
                 return true;
+        if (bound + arg->nmoves + arg->npremoves == arg->depth)
+                arg->nissbranch = INVERSEBRANCH;
 
         bound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->k, arg->h48data);
-        if (bound + arg->nmoves > arg->depth)
+        if (bound + arg->nmoves + arg->npremoves > arg->depth)
                 return true;
-*/
+        if (bound + arg->nmoves + arg->npremoves == arg->depth)
+                arg->nissbranch = NORMALBRANCH;
 
         return false;
 }
@@ -87,7 +104,7 @@ solve_h48_dfs(dfsarg_solveh48_t *arg)
                 return 0;
 
         if (issolved(arg->cube)) {
-                if (arg->nmoves != arg->depth)
+                if (arg->nmoves + arg->npremoves != arg->depth)
                         return 0;
                 solve_h48_appendsolution(arg);
                 return 1;
@@ -95,19 +112,30 @@ solve_h48_dfs(dfsarg_solveh48_t *arg)
 
         /* 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;
+        uint32_t allowed;
+        if(arg->nissbranch & INVERSE) {
+                allowed = allowednextmoveH48(arg->premoves, arg->npremoves, arg->nissbranch);
+                for (m = 0; m < 18; m++) {
+                        if(allowed & (1 << m)) {
+                                nextarg.npremoves = arg->npremoves + 1;
+                                nextarg.premoves[arg->npremoves] = m;
+                                nextarg.inverse = move(arg->inverse, m);
+                                nextarg.cube = premove(arg->cube, m);
+                                ret += solve_h48_dfs(&nextarg);
+                        }
+                }
+        } else {
+                allowed = allowednextmoveH48(arg->moves, arg->nmoves, arg->nissbranch);
+                for (m = 0; m < 18; m++) {
+                        if (allowed & (1 << m)) {
+                                nextarg.nmoves = arg->nmoves + 1;
+                                nextarg.moves[arg->nmoves] = m;
+                                nextarg.cube = move(arg->cube, m);
+                                nextarg.inverse = premove(arg->inverse, m);
+                                ret += solve_h48_dfs(&nextarg);
+                        }
                 }
-                nextarg.cube = move(arg->cube, m);
-                nextarg.inverse = inverse(nextarg.cube); /* TODO: use premove */
-                ret += solve_h48_dfs(&nextarg);
         }
 
         return ret;
@@ -148,6 +176,7 @@ solve_h48(
                 LOG("Found %" PRId64 " solutions, searching at depth %"
                     PRId8 "\n", nsols, arg.depth);
                 arg.nmoves = 0;
+                arg.npremoves = 0;
                 solve_h48_dfs(&arg);
         }
 
diff --git a/test/082_allowednext_h48/00_empty_U.in b/test/082_allowednext_h48/00_empty_U.in
new file mode 100644
index 0000000..28271a6
--- /dev/null
+++ b/test/082_allowednext_h48/00_empty_U.in
@@ -0,0 +1,3 @@
+0
+0
+
diff --git a/test/082_allowednext_h48/00_empty_U.out b/test/082_allowednext_h48/00_empty_U.out
new file mode 100644
index 0000000..8607955
--- /dev/null
+++ b/test/082_allowednext_h48/00_empty_U.out
@@ -0,0 +1 @@
+0x3FFFF
diff --git a/test/082_allowednext_h48/01_F.in b/test/082_allowednext_h48/01_F.in
new file mode 100644
index 0000000..e7ae375
--- /dev/null
+++ b/test/082_allowednext_h48/01_F.in
@@ -0,0 +1,4 @@
+0
+1
+F
+
diff --git a/test/082_allowednext_h48/01_F.out b/test/082_allowednext_h48/01_F.out
new file mode 100644
index 0000000..5d6f843
--- /dev/null
+++ b/test/082_allowednext_h48/01_F.out
@@ -0,0 +1 @@
+0x38FFF
diff --git a/test/082_allowednext_h48/02_U2.in b/test/082_allowednext_h48/02_U2.in
new file mode 100644
index 0000000..2c5ee5f
--- /dev/null
+++ b/test/082_allowednext_h48/02_U2.in
@@ -0,0 +1,3 @@
+0
+1
+U
diff --git a/test/082_allowednext_h48/02_U2.out b/test/082_allowednext_h48/02_U2.out
new file mode 100644
index 0000000..a9a5adb
--- /dev/null
+++ b/test/082_allowednext_h48/02_U2.out
@@ -0,0 +1 @@
+0x3FFF8
diff --git a/test/082_allowednext_h48/03_R_L.in b/test/082_allowednext_h48/03_R_L.in
new file mode 100644
index 0000000..b6c0625
--- /dev/null
+++ b/test/082_allowednext_h48/03_R_L.in
@@ -0,0 +1,5 @@
+0
+2
+R
+L'
+
diff --git a/test/082_allowednext_h48/03_R_L.out b/test/082_allowednext_h48/03_R_L.out
new file mode 100644
index 0000000..a4aa4b2
--- /dev/null
+++ b/test/082_allowednext_h48/03_R_L.out
@@ -0,0 +1 @@
+0x3F03F
diff --git a/test/082_allowednext_h48/04_D.in b/test/082_allowednext_h48/04_D.in
new file mode 100644
index 0000000..83da556
--- /dev/null
+++ b/test/082_allowednext_h48/04_D.in
@@ -0,0 +1,3 @@
+0
+1
+D
diff --git a/test/082_allowednext_h48/04_D.out b/test/082_allowednext_h48/04_D.out
new file mode 100644
index 0000000..fe91843
--- /dev/null
+++ b/test/082_allowednext_h48/04_D.out
@@ -0,0 +1 @@
+0x3FFC0
diff --git a/test/082_allowednext_h48/05_U_F_B2.in b/test/082_allowednext_h48/05_U_F_B2.in
new file mode 100644
index 0000000..67e090f
--- /dev/null
+++ b/test/082_allowednext_h48/05_U_F_B2.in
@@ -0,0 +1,5 @@
+0
+2
+U
+F
+
diff --git a/test/082_allowednext_h48/05_U_F_B2.out b/test/082_allowednext_h48/05_U_F_B2.out
new file mode 100644
index 0000000..5d6f843
--- /dev/null
+++ b/test/082_allowednext_h48/05_U_F_B2.out
@@ -0,0 +1 @@
+0x38FFF
diff --git a/test/082_allowednext_h48/06_empty_bound.in b/test/082_allowednext_h48/06_empty_bound.in
new file mode 100644
index 0000000..389e262
--- /dev/null
+++ b/test/082_allowednext_h48/06_empty_bound.in
@@ -0,0 +1,2 @@
+2
+0
diff --git a/test/082_allowednext_h48/06_empty_bound.out b/test/082_allowednext_h48/06_empty_bound.out
new file mode 100644
index 0000000..eb601fc
--- /dev/null
+++ b/test/082_allowednext_h48/06_empty_bound.out
@@ -0,0 +1 @@
+0x2DB6D
diff --git a/test/082_allowednext_h48/07_F_bound.in b/test/082_allowednext_h48/07_F_bound.in
new file mode 100644
index 0000000..b3ae33d
--- /dev/null
+++ b/test/082_allowednext_h48/07_F_bound.in
@@ -0,0 +1,3 @@
+2
+1
+F
diff --git a/test/082_allowednext_h48/07_F_bound.out b/test/082_allowednext_h48/07_F_bound.out
new file mode 100644
index 0000000..0dc8997
--- /dev/null
+++ b/test/082_allowednext_h48/07_F_bound.out
@@ -0,0 +1 @@
+0x28B6D
diff --git a/test/082_allowednext_h48/08_U_D_bound_inverse.in b/test/082_allowednext_h48/08_U_D_bound_inverse.in
new file mode 100644
index 0000000..707f7e0
--- /dev/null
+++ b/test/082_allowednext_h48/08_U_D_bound_inverse.in
@@ -0,0 +1,4 @@
+3
+2
+U
+D2
\ No newline at end of file
diff --git a/test/082_allowednext_h48/08_U_D_bound_inverse.out b/test/082_allowednext_h48/08_U_D_bound_inverse.out
new file mode 100644
index 0000000..6f47cf0
--- /dev/null
+++ b/test/082_allowednext_h48/08_U_D_bound_inverse.out
@@ -0,0 +1 @@
+0x2DB40
diff --git a/test/082_allowednext_h48/09_R_false_bound.in b/test/082_allowednext_h48/09_R_false_bound.in
new file mode 100644
index 0000000..0b1d441
--- /dev/null
+++ b/test/082_allowednext_h48/09_R_false_bound.in
@@ -0,0 +1,3 @@
+1
+1
+R
\ No newline at end of file
diff --git a/test/082_allowednext_h48/09_R_false_bound.out b/test/082_allowednext_h48/09_R_false_bound.out
new file mode 100644
index 0000000..121bfeb
--- /dev/null
+++ b/test/082_allowednext_h48/09_R_false_bound.out
@@ -0,0 +1 @@
+0x3FE3F
diff --git a/test/082_allowednext_h48/allowednext_h48_tests.c b/test/082_allowednext_h48/allowednext_h48_tests.c
new file mode 100644
index 0000000..4cee695
--- /dev/null
+++ b/test/082_allowednext_h48/allowednext_h48_tests.c
@@ -0,0 +1,38 @@
+#include "../test.h"
+
+uint32_t allowednextmoveH48(uint8_t *, uint8_t, uint32_t);
+
+static char *moves[] = {
+        "U", "U2", "U'",
+        "D", "D2", "D'",
+        "R", "R2", "R'",
+        "L", "L2", "L'",
+        "F", "F2", "F'",
+        "B", "B2", "B'",
+};
+
+void run(void) {
+        char movestr[STRLENMAX];
+        uint8_t m[100];
+        int n, i, j, bound;
+
+        fgets(movestr, STRLENMAX, stdin);
+        bound = atoi(movestr);
+
+        fgets(movestr, STRLENMAX, stdin);
+        n = atoi(movestr);
+
+        for (i = 0; i < n; i++) {
+                fgets(movestr, STRLENMAX, stdin);
+                movestr[strcspn(movestr, "\n")] = 0;
+                for (j = 0; j < 18; j++)
+                        if (!strcmp(movestr, moves[j]))
+                                m[i] = j;
+        }
+
+        fprintf(stderr, "Last two: %s, %s\n",
+            n > 1 ? moves[m[n-2]] : "-",
+            n > 0 ? moves[m[n-1]] : "-");
+        uint32_t allowed = allowednextmoveH48(m, n, bound);
+        printf("0x%05X\n", allowed);
+}