From 975e3eafbae15b93a1a4f160dd781d359a6c717b Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sun, 26 Dec 2021 19:38:28 +0100 Subject: Added two-phase solver --- src/alg.c | 67 ++++++++++++++++++++++++++++++++-------------------------- src/alg.h | 1 + src/commands.c | 29 ++++++++++++++++++++++++- src/solve.c | 51 ++++++++++++++++++++++++++++++++++++++++++++ src/solve.h | 1 + src/steps.c | 2 +- src/steps.h | 46 ++++++++++++++++++++++++++++++++++++++++ 7 files changed, 165 insertions(+), 32 deletions(-) (limited to 'src') 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) { @@ -184,6 +184,13 @@ compose_alg(Alg *alg1, Alg *alg2) append_move(alg1, alg2->move[i], alg2->inv[i]); } +void +copy_alg(Alg *src, Alg *dst) +{ + dst->len = 0; /* Overwrites */ + compose_alg(dst, src); +} + void free_alg(Alg *alg) { 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); @@ -92,6 +93,15 @@ help_cmd = { .exec = help_exec, }; +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", @@ -128,6 +138,7 @@ Command *commands[NCOMMANDS] = { &quit_cmd, &solve_cmd, &steps_cmd, + &twophase_cmd, &unniss_cmd, &version_cmd, }; @@ -383,6 +394,22 @@ print_exec(CommandArgs *args) print_cube(apply_alg(args->scramble, (Cube){0})); } +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) { 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); -- cgit v1.3