commit 975e3eafbae15b93a1a4f160dd781d359a6c717b
parent b82df53eb461506984eb2b6a9b53e445b75e46af
Author: Sebastiano Tronto <sebastiano.tronto@gmail.com>
Date: Sun, 26 Dec 2021 19:38:28 +0100
Added two-phase solver
Diffstat:
11 files changed, 171 insertions(+), 33 deletions(-)
diff --git 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
@@ -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
Binary files differ.
diff --git a/nissy.exe b/nissy.exe
Binary files differ.
diff --git 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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);
