Added two-phase solver

11 files changed, 171 insertions, 33 deletions

diff --git a/TODO.md b/TODO.md
index fc5d9bb..eb8d487 100644
--- a/TODO.md
+++ b/TODO.md
@@ -10,7 +10,6 @@ It's more of a personal reminder than anything else.
 ### Commands that are available in nissy 1.0, but not in this version (yet):
 * drcorners (solve corners after dr)
 * search and improve non-optimal subsequences
-* **fast non-optimal solver (also needed for scramble)**
 * **scramble [dr, corners only, edges only, htr, fmc(RUF)...]**
 * save and edit algs as "variables"
   (or just use a "logging system" to keep info about previously run commands,
@@ -32,6 +31,7 @@ including e.g. solutions that were not shown because -c)
 * transform alg, rufify etc...
 * more scramble stuff (scramble FMC with rufify...)
 * command notation to list available moves
+* make multi-step solve much more general and create command
 
 ## Distribution
 
diff --git a/doc/nissy.1 b/doc/nissy.1
index 549cc4f..643674a 100644
--- a/doc/nissy.1
+++ b/doc/nissy.1
@@ -160,6 +160,11 @@ for the
 .Ar solve
 command.
 .
+.It Nm twophase Ar scramble
+Find a solution using a two-phase method. This does not guarantee
+to return an optimal solution (and in fact most often it does not),
+but it is very fast.
+.
 .It Nm unniss Ar scramble
 Rewrite the scramble without using NISS.
 .
diff --git a/nissy b/nissy
index ce40157..c697a48 100755
--- a/nissy
+++ b/nissy
diff --git a/nissy.exe b/nissy.exe
index cd521d5..9dff82b 100755
--- a/nissy.exe
+++ b/nissy.exe
diff --git a/src/alg.c b/src/alg.c
index d9317ab..4c732a3 100644
--- a/src/alg.c
+++ b/src/alg.c
@@ -107,36 +107,6 @@ allowed_next_HTM(Move l2, Move l1, Move m)
         return !(p || (commute(l1, l2) && q));
 }
 
-static int
-axis(Move m)
-{
-        if (m == NULLMOVE)
-                return 0;
-
-        if (m >= U && m <= B3)
-                return (m-1)/6 + 1;
-        
-        if (m >= Uw && m <= Bw3)
-                return (m-1)/6 - 2;
-
-        if (base_move(m) == E || base_move(m) == y)
-                return 1;
-
-        if (base_move(m) == M || base_move(m) == x)
-                return 2;
-
-        if (base_move(m) == S || base_move(m) == z)
-                return 3;
-
-        return -1;
-}
-
-bool
-commute(Move m1, Move m2)
-{
-        return axis(m1) == axis(m2);
-}
-
 void
 append_alg(AlgList *l, Alg *alg)
 {
@@ -166,6 +136,30 @@ append_move(Alg *alg, Move m, bool inverse)
         alg->len++;
 }
 
+static int
+axis(Move m)
+{
+        if (m == NULLMOVE)
+                return 0;
+
+        if (m >= U && m <= B3)
+                return (m-1)/6 + 1;
+        
+        if (m >= Uw && m <= Bw3)
+                return (m-1)/6 - 2;
+
+        if (base_move(m) == E || base_move(m) == y)
+                return 1;
+
+        if (base_move(m) == M || base_move(m) == x)
+                return 2;
+
+        if (base_move(m) == S || base_move(m) == z)
+                return 3;
+
+        return -1;
+}
+
 Move
 base_move(Move m)
 {
@@ -175,6 +169,12 @@ base_move(Move m)
                 return m - (m-1)%3;
 }
 
+bool
+commute(Move m1, Move m2)
+{
+        return axis(m1) == axis(m2);
+}
+
 void
 compose_alg(Alg *alg1, Alg *alg2)
 {
@@ -185,6 +185,13 @@ compose_alg(Alg *alg1, Alg *alg2)
 }
 
 void
+copy_alg(Alg *src, Alg *dst)
+{
+        dst->len = 0; /* Overwrites */
+        compose_alg(dst, src);
+}
+
+void
 free_alg(Alg *alg)
 {
         free(alg->move);
diff --git a/src/alg.h b/src/alg.h
index e046526..ea95a9c 100644
--- a/src/alg.h
+++ b/src/alg.h
@@ -19,6 +19,7 @@ void        append_move(Alg *alg, Move m, bool inverse);
 Move        base_move(Move m);
 void        compose_alg(Alg *alg1, Alg *alg2);
 bool        commute(Move m1, Move m2);
+void        copy_alg(Alg *src, Alg *dst);
 void        free_alg(Alg *alg);
 void        free_alglist(AlgList *l);
 Alg *       inverse_alg(Alg *alg);
diff --git a/src/commands.c b/src/commands.c
index 56ff944..02af19f 100644
--- a/src/commands.c
+++ b/src/commands.c
@@ -2,12 +2,12 @@
 
 /* Arg parsing functions *****************************************************/
 
-CommandArgs *           solve_parse_args(int c, char **v);
 CommandArgs *           gen_parse_args(int c, char **v);
 CommandArgs *           help_parse_args(int c, char **v);
 CommandArgs *           print_parse_args(int c, char **v);
 CommandArgs *           parse_only_scramble(int c, char **v);
 CommandArgs *           parse_no_arg(int c, char **v);
+CommandArgs *           solve_parse_args(int c, char **v);
 
 /* Exec functions ************************************************************/
 
@@ -17,6 +17,7 @@ static void             solve_exec(CommandArgs *args);
 static void             steps_exec(CommandArgs *args);
 static void             commands_exec(CommandArgs *args);
 static void             print_exec(CommandArgs *args);
+static void             twophase_exec(CommandArgs *args);
 static void             help_exec(CommandArgs *args);
 static void             quit_exec(CommandArgs *args);
 static void             unniss_exec(CommandArgs *args);
@@ -93,6 +94,15 @@ help_cmd = {
 };
 
 Command
+twophase_cmd = {
+        .name        = "twophase",
+        .usage       = "twophase",
+        .description = "Find a solution quickly using a 2-phase method",
+        .parse_args  = parse_only_scramble,
+        .exec        = twophase_exec,
+};
+
+Command
 quit_cmd = {
         .name        = "quit",
         .usage       = "quit",
@@ -128,6 +138,7 @@ Command *commands[NCOMMANDS] = {
         &quit_cmd,
         &solve_cmd,
         &steps_cmd,
+        &twophase_cmd,
         &unniss_cmd,
         &version_cmd,
 };
@@ -384,6 +395,22 @@ print_exec(CommandArgs *args)
 }
 
 static void
+twophase_exec(CommandArgs *args)
+{
+        Cube c;
+        Alg *sol;
+
+        init_movesets();
+        init_symcoord();
+
+        c = apply_alg(args->scramble, (Cube){0});
+        sol = solve_2phase(c, 1);
+
+        print_alg(sol, false);
+        free_alg(sol);
+}
+
+static void
 help_exec(CommandArgs *args)
 {
         if (args->command == NULL) {
diff --git a/src/solve.c b/src/solve.c
index 5a72bba..cfb2bd3 100644
--- a/src/solve.c
+++ b/src/solve.c
@@ -438,3 +438,54 @@ solve(Cube cube, Step *step, SolveOptions *opts)
 
         return sols;
 }
+
+/* TODO: make more general! */
+Alg *
+solve_2phase(Cube cube, int nthreads)
+{
+        int bestlen, newb;
+        Alg *bestalg;
+        AlgList *sols1, *sols2;
+        AlgListNode *i;
+        Cube c;
+        SolveOptions opts1, opts2;
+
+        opts1.min_moves     = 0;
+        opts1.max_moves     = 13;
+        opts1.max_solutions = 100;
+        opts1.nthreads      = nthreads;
+        opts1.optimal       = 3;
+        opts1.can_niss      = false;
+        opts1.verbose       = false;
+        opts1.all           = true;
+
+        opts2.min_moves     = 0;
+        opts2.max_moves     = 19;
+        opts2.max_solutions = 1;
+        opts2.nthreads      = nthreads;
+        opts2.can_niss      = false;
+        opts2.verbose       = false;
+
+        sols1 = solve(cube, &drany_HTM, &opts1);
+        bestalg = new_alg("");
+        bestlen = 999;
+        for (i = sols1->first; i != NULL; i = i->next) {
+                c = apply_alg(i->alg, cube);
+                sols2 = solve(c, &dranyfin_DR, &opts2);
+                
+                if (sols2->len > 0) {
+                        newb = i->alg->len + sols2->first->alg->len;
+                        if (newb < bestlen) {
+                                bestlen = newb;
+                                copy_alg(i->alg, bestalg);
+                                compose_alg(bestalg, sols2->first->alg);
+                        }
+                }
+
+                free_alglist(sols2);
+        }
+
+        free_alglist(sols1);
+
+        return bestalg;
+}
diff --git a/src/solve.h b/src/solve.h
index 668cd9a..6ce6609 100644
--- a/src/solve.h
+++ b/src/solve.h
@@ -6,5 +6,6 @@
 #include "trans.h"
 
 AlgList *   solve(Cube cube, Step *step, SolveOptions *opts);
+Alg *       solve_2phase(Cube cube, int nthreads);
 
 #endif
diff --git a/src/steps.c b/src/steps.c
index 98e26b5..5de3206 100644
--- a/src/steps.c
+++ b/src/steps.c
@@ -1437,7 +1437,7 @@ static int
 detect_pretrans_drud(Cube cube, Trans *ret)
 {
         int i, n;
-        static Trans tt[3] = {uf, ur, fd};
+        static Trans tt[3] = {uf, fr, rd};
 
         for (i = 0, n = 0; i < 3; i++)
                 if (check_drud(apply_trans(tt[i], cube)))
diff --git a/src/steps.h b/src/steps.h
index 5744e48..53f8e1b 100644
--- a/src/steps.h
+++ b/src/steps.h
@@ -7,6 +7,52 @@
 
 extern Step *           steps[NSTEPS];
 
+extern Step             optimal_HTM;
+extern Step             optimal_light_HTM;
+extern Step             eofin_eo;
+extern Step             eofbfin_eofb;
+extern Step             eorlfin_eorl;
+extern Step             eoudfin_eoud;
+extern Step             eoany_HTM;
+extern Step             eofb_HTM;
+extern Step             eorl_HTM;
+extern Step             eoud_HTM;
+extern Step             coany_HTM;
+extern Step             coud_HTM;
+extern Step             corl_HTM;
+extern Step             cofb_HTM;
+extern Step             coany_URF;
+extern Step             coud_URF;
+extern Step             corl_URF;
+extern Step             cofb_URF;
+extern Step             drany_HTM;
+extern Step             drud_HTM;
+extern Step             drrl_HTM;
+extern Step             drfb_HTM;
+extern Step             dr_eo;
+extern Step             dr_eofb;
+extern Step             dr_eorl;
+extern Step             dr_eoud;
+extern Step             drud_eofb;
+extern Step             drrl_eofb;
+extern Step             drud_eorl;
+extern Step             drfb_eorl;
+extern Step             drfb_eoud;
+extern Step             drrl_eoud;
+extern Step             dranyfin_DR;
+extern Step             drudfin_drud;
+extern Step             drrlfin_drrl;
+extern Step             drfbfin_drfb;
+extern Step             htr_any;
+extern Step             htr_drud;
+extern Step             htr_drrl;
+extern Step             htr_drfb;
+extern Step             htrfin_htr;
+extern Step             cornershtr_HTM;
+extern Step             cornershtr_URF;
+extern Step             corners_HTM;
+extern Step             corners_URF;
+
 void                    copy_estimatedata(EstimateData *s, EstimateData *d);
 void                    invert_estimatedata(EstimateData *ed);
 void                    reset_estimatedata(EstimateData *ed);