nissy-nx

A Rubik's cube optimal solver
git clone https://git.tronto.net/nissy-nx
Download | Log | Files | Refs | README | LICENSE

commit 5cf18fa4694ab9f082813d04e3ec5b78a061d9df
parent cecdb7c5a0fc4821bc56c6aae5428925ec1baa15
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Mon, 26 Dec 2022 19:27:21 +0100

Implemented faster fst_ep_to_epos

Diffstat:
MTODO.md | 3+++
Msrc/fst.c | 124+++++++++++++++++++++++++++++++++++++++++++++++++++----------------------------
Msrc/fst.h | 1-
Mtests/fst_post_init_tests.c | 33---------------------------------
4 files changed, 83 insertions(+), 78 deletions(-)

diff --git a/TODO.md b/TODO.md @@ -4,6 +4,9 @@ This is a list of things that I would like to add or change at some point. It's more of a personal reminder than anything else. ## After symcoord +### Fixing stuff + completing new optimal solver +- clean up fst, check if more can be improved +- fst inverse tables: save to file ### generic: * all files should have an init function, calling the ones of the files includes + doing more stuff. A static "initiliazed" diff --git a/src/fst.c b/src/fst.c @@ -3,7 +3,6 @@ #include "fst.h" static FstCube ep_to_fst_epos(int *ep); -static void transform_ep_only(Trans t, int *ep, Cube *dst); static void init_fst_corner_invtables(); static void init_fst_eo_invtables(); static void init_fst_eo_update(uint64_t, uint64_t, int, Cube *); @@ -54,24 +53,12 @@ cube_to_fst(Cube *cube) static FstCube ep_to_fst_epos(int *ep) { - /* TODO: maybe optimize */ -/* TODO: this version if faster, but broken - probably need to fix transform_ep_only() - - FstCube ret; - Cube c; - - memcpy(c.ep, ep, 12 * sizeof(int)); - ret.uf_eposepe = coord_eposepe.i[0]->index(&c); - - transform_ep_only(fr, ep, &c); - ret.fr_eposepe = coord_eposepe.i[0]->index(&c); - - transform_ep_only(rd, ep, &c); - ret.rd_eposepe = coord_eposepe.i[0]->index(&c); -*/ +/* The block of commented code works, but it is slower. + The actual code is mysterious, and there is some overlap with coord.c + (coord_eposepe.i), and trans.c, butbut it is faster. */ +/* FstCube ret; Cube c, d; @@ -90,16 +77,89 @@ ep_to_fst_epos(int *ep) ret.rd_eposepe = coord_eposepe.i[0]->index(&d); return ret; +*/ + + static int eind[12] = { + [FR] = 0, [FL] = 1, [BL] = 2, [BR] = 3, + [UR] = 0, [DR] = 1, [DL] = 2, [UL] = 3, + [DB] = 0, [DF] = 1, [UF] = 2, [UB] = 3 + }; + static int eptrans_fr[12] = { + [FR] = UF, [DF] = UL, [FL] = UB, [UF] = UR, + [BR] = DF, [DB] = DL, [BL] = DB, [UB] = DR, + [UR] = FR, [DR] = FL, [DL] = BL, [UL] = BR + }; + static int eptrans_rd[12] = { + [DR] = UF, [FR] = UL, [UR] = UB, [BR] = UR, + [DL] = DF, [FL] = DL, [UL] = DB, [BL] = DR, + [DB] = FR, [DF] = FL, [UF] = BL, [UB] = BR + }; + + FstCube ret; + int i, ce, cs, cm; + int epe[4], eps[4], epm[4], epose[12], eposs[12], eposm[12]; + + memset(epose, 0, 12*sizeof(int)); + memset(eposs, 0, 12*sizeof(int)); + memset(eposm, 0, 12*sizeof(int)); + + for (i = 0, ce = 0; i < 12; i++) { + switch (edge_slice[ep[i]]) { + case 0: + epose[i] = 1; + epe[ce++] = eind[ep[i]]; + break; + case 1: + eposs[eptrans_fr[i]] = eind[ep[i]] + 1; + break; + default: + eposm[eptrans_rd[i]] = eind[ep[i]] + 1; + break; + } + } + + for (i = 0, cs = 0, cm = 0; i < 12; i++) { + if (eposs[i]) { + eps[cs++] = eposs[i] - 1; + eposs[i] = 1; + } + if (eposm[i]) { + epm[cm++] = eposm[i] - 1; + eposm[i] = 1; + } + } + + ret.uf_eposepe = subset_to_index(epose, 12, 4) * FACTORIAL4 + + perm_to_index(epe, 4); + ret.fr_eposepe = subset_to_index(eposs, 12, 4) * FACTORIAL4 + + perm_to_index(eps, 4); + ret.rd_eposepe = subset_to_index(eposm, 12, 4) * FACTORIAL4 + + perm_to_index(epm, 4); + + return ret; } FstCube fst_inverse(FstCube fst) { FstCube ret; - int i, ep_inv[12]; + int ep_inv[12]; + + ep_inv[FR] = fst_where_is_edge_arr[0][FR][fst.uf_eposepe]; + ep_inv[FL] = fst_where_is_edge_arr[0][FL][fst.uf_eposepe]; + ep_inv[BL] = fst_where_is_edge_arr[0][BL][fst.uf_eposepe]; + ep_inv[BR] = fst_where_is_edge_arr[0][BR][fst.uf_eposepe]; + + ep_inv[UR] = fst_where_is_edge_arr[1][UR][fst.fr_eposepe]; + ep_inv[UL] = fst_where_is_edge_arr[1][UL][fst.fr_eposepe]; + ep_inv[DR] = fst_where_is_edge_arr[1][DR][fst.fr_eposepe]; + ep_inv[DL] = fst_where_is_edge_arr[1][DL][fst.fr_eposepe]; + + ep_inv[UF] = fst_where_is_edge_arr[2][UF][fst.rd_eposepe]; + ep_inv[UB] = fst_where_is_edge_arr[2][UB][fst.rd_eposepe]; + ep_inv[DF] = fst_where_is_edge_arr[2][DF][fst.rd_eposepe]; + ep_inv[DB] = fst_where_is_edge_arr[2][DB][fst.rd_eposepe]; - for (i = 0; i < 12; i++) - ep_inv[i] = fst_where_is_edge(i, fst); ret = ep_to_fst_epos(ep_inv); ret.uf_eofb = ((uint16_t)eo_invtable[0][fst.uf_eofb][fst.uf_eposepe]) | @@ -175,30 +235,6 @@ fst_to_cube(FstCube fst, Cube *cube) cube->xp[i] = i; } -int -fst_where_is_edge(int e, FstCube fst) -{ - switch (edge_slice[e]) { - case 0: - return fst_where_is_edge_arr[0][e][fst.uf_eposepe]; - case 1: - return fst_where_is_edge_arr[1][e][fst.fr_eposepe]; - default: - return fst_where_is_edge_arr[2][e][fst.rd_eposepe]; - } - - return -1; -} - -static void -transform_ep_only(Trans t, int *ep, Cube *dst) -{ - int i; - - for (i = 0; i < 12; i++) - dst->ep[i] = trans_ep_alg[t][ep[trans_ep_inv[t][i]]]; -} - void init_fst() { diff --git a/src/fst.h b/src/fst.h @@ -7,7 +7,6 @@ FstCube cube_to_fst(Cube *cube); FstCube fst_inverse(FstCube fst); FstCube fst_move(Move m, FstCube fst); void fst_to_cube(FstCube fst, Cube *cube); -int fst_where_is_edge(int e, FstCube fst); void init_fst(); #endif diff --git a/tests/fst_post_init_tests.c b/tests/fst_post_init_tests.c @@ -4,19 +4,16 @@ static bool fst_move_testcase(Cube *c, Alg *a); static bool fst_inverse_testcase(Cube *c, Alg *a); static bool fst_move_test(); -static bool fst_where_is_edge_test(); static bool fst_inverse_test(); static Tester test[] = { fst_move_test, - fst_where_is_edge_test, fst_inverse_test, NULL }; static char *name[] = { "FST move", - "FST where is edge", "FST inverse", }; @@ -62,36 +59,6 @@ fst_move_test() } static bool -fst_where_is_edge_test() -{ - int i; - Alg *scr; - Cube c, d; - FstCube fst; - - /* Testing on a single scramble is fine for now */ - scr = new_alg("RUFDL2B2FRD"); - make_solved(&c); - apply_alg(scr, &c); - fst = cube_to_fst(&c); - - for (i = 0; i < 12; i++) { - if (fst_where_is_edge(c.ep[i], fst) != i) { - fst_to_cube(fst, &d); - printf("Alg: "); - print_alg(scr, false); - printf("Expected:\n"); - print_cube(&c); - printf("But got:\n"); - print_cube(&d); - return false; - } - } - - return true; -} - -static bool fst_inverse_test() { return try_all_str(fst_inverse_testcase, "FST test incorrect");