nissy-nx

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

commit cecdb7c5a0fc4821bc56c6aae5428925ec1baa15
parent 1ac26de8dcb76323a5f96eab200a027236cb55d0
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Mon, 26 Dec 2022 12:41:36 +0100

Fixed fst_inverse

Diffstat:
MMakefile | 4+++-
MTODO.md | 13+++++++++++--
Msrc/cube.c | 126+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------------
Msrc/cube.h | 12++++++++++++
Msrc/fst.c | 75+++++++++++++++++++++++++++++++++++++++++++++++++++------------------------
Msrc/fst.h | 1+
Msrc/moves.c | 18++++++++++++++++++
Msrc/moves.h | 3+++
Atests/fst_post_init_tests.c | 114+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Atests/fst_pre_init_tests.c | 89+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Atests/fst_test_util.c | 64++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Atests/fst_test_util.h | 7+++++++
Dtests/inc.h | 1-
Atests/nissy_tests.c | 12++++++++++++
Dtests/test_all.c | 10----------
Dtests/test_fst.c | 184-------------------------------------------------------------------------------
16 files changed, 489 insertions(+), 244 deletions(-)

diff --git a/Makefile b/Makefile @@ -21,7 +21,9 @@ nissy: clean ${CC} ${CFLAGS} -o nissy src/*.c test: - ${CC} ${TESTFLAGS} -o test src/*.c tests/*.c + ${CC} ${TESTFLAGS} -o nissy-test src/*.c tests/*.c + ./nissy-test + rm nissy-test nissy.exe: x86_64-w64-mingw32-gcc ${CFLAGS} -static -o nissy.exe src/*.c diff --git a/TODO.md b/TODO.md @@ -9,8 +9,8 @@ It's more of a personal reminder than anything else. of the files includes + doing more stuff. A static "initiliazed" variable is probably needed too. ### testing! -* test fst: implement fst_consistent -* test fst: init_fst is necessary before testing move and inverse +* generic test util: function taking an array of tests, an array of testnames + (or maybe tests should be their own type?) and running them * separate "commands" for testing different parts (e.g. ./test coord) * test coordinate (needed anyway to test fst) * other tests (start from bottom: utils.c) @@ -19,10 +19,15 @@ It's more of a personal reminder than anything else. * add Void * extradata to DfsArg and a custom move function * add optional custom pre-process for generating special table (nx) * copy_dfsdata should copy extra too! +### Solving simplification / refactor +* Split solve in solve_coord, solve_generic, solve_singlethread... +* Rework choicesteps: simplify, remove one type of rotation... ### nx.c * implement nxopt with all tables and all tricks (maybe compile time variable for maximum memory to use?) * is_valid should also unniss / cleanup the alg +### Other easy refactor +* split cubetypes.h into other files ## For version 2.1 ### Changes to Step and Solve @@ -47,9 +52,11 @@ It's more of a personal reminder than anything else. check if found enough solutions before checking pruning values) ### Technical * generic option parser +* scan system to get best number of threads ### Commands * Easy: add option -I (inverse) and -L (linear, like inverse + normal) to do only linear NISS +* message for -N ignored say -n (lowercase) ## Commands @@ -75,6 +82,8 @@ including e.g. solutions that were not shown because -c) * solve should try up to a small bound without loading the large pruning table (maybe this is not necessary if loading the table is fast enough) * silent batch mode without >>> +* Optimal solver: when asking for only one solution, scan for upper bound in + parallel using a two-phase solver. ### New features * EO analysis (and also DR and HTR analysis): group similar EOs together diff --git a/src/cube.c b/src/cube.c @@ -5,27 +5,61 @@ static int where_is_piece(int piece, int *arr, int n); void -compose(Cube *c2, Cube *c1) +compose_centers(Cube *c2, Cube *c1) { - apply_permutation(c2->ep, c1->ep, 12); - apply_permutation(c2->ep, c1->eo, 12); - sum_arrays_mod(c2->eo, c1->eo, 12, 2); + apply_permutation(c2->xp, c1->xp, 6); +} +void +compose_corners(Cube *c2, Cube *c1) +{ apply_permutation(c2->cp, c1->cp, 8); apply_permutation(c2->cp, c1->co, 8); sum_arrays_mod(c2->co, c1->co, 8, 3); +} - apply_permutation(c2->xp, c1->xp, 6); +void +compose_edges(Cube *c2, Cube *c1) +{ + apply_permutation(c2->ep, c1->ep, 12); + apply_permutation(c2->ep, c1->eo, 12); + sum_arrays_mod(c2->eo, c1->eo, 12, 2); } void -copy_cube(Cube *src, Cube *dst) +compose(Cube *c2, Cube *c1) +{ + compose_centers(c2, c1); + compose_corners(c2, c1); + compose_edges(c2, c1); +} + +void +copy_cube_centers(Cube *src, Cube *dst) +{ + memcpy(dst->xp, src->xp, 6 * sizeof(int)); +} + +void +copy_cube_corners(Cube *src, Cube *dst) { - memcpy(dst->ep, src->ep, 12 * sizeof(int)); - memcpy(dst->eo, src->eo, 12 * sizeof(int)); memcpy(dst->cp, src->cp, 8 * sizeof(int)); memcpy(dst->co, src->co, 8 * sizeof(int)); - memcpy(dst->xp, src->xp, 6 * sizeof(int)); +} + +void +copy_cube_edges(Cube *src, Cube *dst) +{ + memcpy(dst->ep, src->ep, 12 * sizeof(int)); + memcpy(dst->eo, src->eo, 12 * sizeof(int)); +} + +void +copy_cube(Cube *src, Cube *dst) +{ + copy_cube_centers(src, dst); + copy_cube_corners(src, dst); + copy_cube_edges(src, dst); } bool @@ -49,25 +83,51 @@ equal(Cube *c1, Cube *c2) } void -invert_cube(Cube *cube) +invert_cube_centers(Cube *cube) { - Cube aux; int i; + Cube aux; - copy_cube(cube, &aux); + copy_cube_centers(cube, &aux); - for (i = 0; i < 12; i++) { - cube->ep[aux.ep[i]] = i; - cube->eo[aux.ep[i]] = aux.eo[i]; - } + for (i = 0; i < 6; i++) + cube->xp[aux.xp[i]] = i; +} + +void +invert_cube_corners(Cube *cube) +{ + int i; + Cube aux; + + copy_cube_corners(cube, &aux); for (i = 0; i < 8; i++) { cube->cp[aux.cp[i]] = i; cube->co[aux.cp[i]] = (3 - aux.co[i]) % 3; } +} - for (i = 0; i < 6; i++) - cube->xp[aux.xp[i]] = i; +void +invert_cube_edges(Cube *cube) +{ + int i; + Cube aux; + + copy_cube_edges(cube, &aux); + + for (i = 0; i < 12; i++) { + cube->ep[aux.ep[i]] = i; + cube->eo[aux.ep[i]] = aux.eo[i]; + } +} + +void +invert_cube(Cube *cube) +{ + invert_cube_centers(cube); + invert_cube_corners(cube); + invert_cube_edges(cube); } bool @@ -105,15 +165,37 @@ is_solved(Cube *cube) } void -make_solved(Cube *cube) +make_solved_centers(Cube *cube) +{ + static int sorted[6] = {0, 1, 2, 3, 4, 5}; + + memcpy(cube->xp, sorted, 6 * sizeof(int)); +} + +void +make_solved_corners(Cube *cube) +{ + static int sorted[8] = {0, 1, 2, 3, 4, 5, 6, 7}; + + memcpy(cube->cp, sorted, 8 * sizeof(int)); + memset(cube->co, 0, 8 * sizeof(int)); +} + +void +make_solved_edges(Cube *cube) { static int sorted[12] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}; memcpy(cube->ep, sorted, 12 * sizeof(int)); memset(cube->eo, 0, 12 * sizeof(int)); - memcpy(cube->cp, sorted, 8 * sizeof(int)); - memset(cube->co, 0, 8 * sizeof(int)); - memcpy(cube->xp, sorted, 6 * sizeof(int)); +} + +void +make_solved(Cube *cube) +{ + make_solved_centers(cube); + make_solved_corners(cube); + make_solved_edges(cube); } void diff --git a/src/cube.h b/src/cube.h @@ -8,12 +8,24 @@ #include "utils.h" void compose(Cube *c2, Cube *c1); /* Use c2 as an alg on c1 */ +void compose_centers(Cube *c2, Cube *c1); +void compose_corners(Cube *c2, Cube *c1); +void compose_edges(Cube *c2, Cube *c1); void copy_cube(Cube *src, Cube *dst); +void copy_cube_centers(Cube *src, Cube *dst); +void copy_cube_corners(Cube *src, Cube *dst); +void copy_cube_edges(Cube *src, Cube *dst); bool equal(Cube *c1, Cube *c2); void invert_cube(Cube *cube); +void invert_cube_centers(Cube *cube); +void invert_cube_corners(Cube *cube); +void invert_cube_edges(Cube *cube); bool is_admissible(Cube *cube); bool is_solved(Cube *cube); void make_solved(Cube *cube); +void make_solved_centers(Cube *cube); +void make_solved_corners(Cube *cube); +void make_solved_edges(Cube *cube); void print_cube(Cube *cube); int where_is_center(Center x, Cube *c); int where_is_corner(Corner k, Cube *c); 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 int fst_where_is_edge(int e, FstCube fst); static void transform_ep_only(Trans t, int *ep, Cube *dst); static void init_fst_corner_invtables(); static void init_fst_eo_invtables(); @@ -55,7 +54,10 @@ cube_to_fst(Cube *cube) static FstCube ep_to_fst_epos(int *ep) { - /* TODO: maybe optimize? */ + /* TODO: maybe optimize */ + +/* TODO: this version if faster, but broken + probably need to fix transform_ep_only() FstCube ret; Cube c; @@ -68,6 +70,24 @@ ep_to_fst_epos(int *ep) transform_ep_only(rd, ep, &c); ret.rd_eposepe = coord_eposepe.i[0]->index(&c); +*/ + + FstCube ret; + Cube c, d; + + make_solved(&c); + memcpy(c.ep, ep, 12 * sizeof(int)); + + copy_cube(&c, &d); + ret.uf_eposepe = coord_eposepe.i[0]->index(&d); + + copy_cube(&c, &d); + apply_trans(fr, &d); + ret.fr_eposepe = coord_eposepe.i[0]->index(&d); + + copy_cube(&c, &d); + apply_trans(rd, &d); + ret.rd_eposepe = coord_eposepe.i[0]->index(&d); return ret; } @@ -155,7 +175,7 @@ fst_to_cube(FstCube fst, Cube *cube) cube->xp[i] = i; } -static int +int fst_where_is_edge(int e, FstCube fst) { switch (edge_slice[e]) { @@ -183,6 +203,10 @@ void init_fst() { init_trans(); + gen_coord(&coord_eofb); + gen_coord(&coord_eposepe); + gen_coord(&coord_coud); + gen_coord(&coord_cp); init_fst_corner_invtables(); init_fst_eo_invtables(); @@ -193,32 +217,29 @@ init_fst() static void init_fst_corner_invtables() { -/* TODO: this can be optimized by transforming and copying only corners */ -/* A factor of about 4 would be saved in the innermost loop */ - Cube c, d; uint64_t cp, coud; for (cp = 0; cp < FACTORIAL8; cp++) { - make_solved(&c); + make_solved_corners(&c); coord_cp.i[0]->to_cube(cp, &c); - copy_cube(&c, &d); - invert_cube(&d); - inv_cp[cp] = coord_coud.i[0]->index(&d); + copy_cube_corners(&c, &d); + invert_cube_corners(&d); + inv_cp[cp] = coord_cp.i[0]->index(&d); for (coud = 0; coud < POW3TO7; coud++) { - copy_cube(&c, &d); + copy_cube_corners(&c, &d); coord_coud.i[0]->to_cube(coud, &d); - invert_cube(&d); + invert_cube_corners(&d); inv_coud[cp][coud] = coord_coud.i[0]->index(&d); } - copy_cube(&c, &d); + copy_cube_corners(&c, &d); apply_trans(fr, &d); uf_cp_to_fr_cp[cp] = coord_cp.i[0]->index(&d); - copy_cube(&c, &d); + copy_cube_corners(&c, &d); apply_trans(rd, &d); uf_cp_to_rd_cp[cp] = coord_cp.i[0]->index(&d); } @@ -234,13 +255,17 @@ init_fst_eo_invtables() make_solved(&c); coord_eposepe.i[0]->to_cube(ep, &c); for (eo = 0; eo < POW2TO11; eo++) { - coord_eofb.i[0]->to_cube(eo, &c); - copy_cube(&c, &d); + copy_cube_edges(&c, &d); + coord_eofb.i[0]->to_cube(eo, &d); init_fst_eo_update(eo, ep, 0, &d); + apply_trans(inverse_trans(fr), &d); + coord_eofb.i[0]->to_cube(eo, &d); init_fst_eo_update(eo, ep, 1, &d); - copy_cube(&c, &d); + + copy_cube_edges(&c, &d); apply_trans(inverse_trans(rd), &d); + coord_eofb.i[0]->to_cube(eo, &d); init_fst_eo_update(eo, ep, 2, &d); } } @@ -251,9 +276,11 @@ init_fst_eo_update(uint64_t eo, uint64_t ep, int s, Cube *d) { int i; - for (i = 0; i < 12; i++) - if (d->eo[i]) - eo_invtable[s][eo][ep] |= ((uint16_t)1) << d->ep[i]; + for (i = 0; i < 12; i++) { + if (edge_slice[d->ep[i]] == s && d->eo[i] && d->ep[i] != 11) + eo_invtable[s][eo][ep] |= + ((uint16_t)1) << ((uint16_t)d->ep[i]); + } } static void @@ -270,7 +297,7 @@ init_fst_transalg() apply_alg(alg, &c); for (i = 0; i < 12; i++) trans_ep_alg[t][i] = c.ep[i]; - invert_cube(&c); + invert_cube_edges(&c); for (i = 0; i < 12; i++) trans_ep_inv[t][i] = c.ep[i]; } @@ -286,20 +313,20 @@ init_fst_where_is_edge() for (e = 0; e < BINOM12ON4 * FACTORIAL4; e++) { coord_eposepe.i[0]->to_cube(e, &c); - copy_cube(&c, &d); + copy_cube_edges(&c, &d); fst_where_is_edge_arr[0][FR][e] = where_is_edge(FR, &d); fst_where_is_edge_arr[0][FL][e] = where_is_edge(FL, &d); fst_where_is_edge_arr[0][BL][e] = where_is_edge(BL, &d); fst_where_is_edge_arr[0][BR][e] = where_is_edge(BR, &d); - copy_cube(&c, &d); + copy_cube_edges(&c, &d); apply_trans(inverse_trans(fr), &d); fst_where_is_edge_arr[1][UL][e] = where_is_edge(UL, &d); fst_where_is_edge_arr[1][UR][e] = where_is_edge(UR, &d); fst_where_is_edge_arr[1][DL][e] = where_is_edge(DL, &d); fst_where_is_edge_arr[1][DR][e] = where_is_edge(DR, &d); - copy_cube(&c, &d); + copy_cube_edges(&c, &d); apply_trans(inverse_trans(rd), &d); fst_where_is_edge_arr[2][UF][e] = where_is_edge(UF, &d); fst_where_is_edge_arr[2][UB][e] = where_is_edge(UB, &d); diff --git a/src/fst.h b/src/fst.h @@ -7,6 +7,7 @@ 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/src/moves.c b/src/moves.c @@ -106,6 +106,24 @@ apply_move(Move m, Cube *cube) compose(&move_array[m], cube); } +void +apply_move_centers(Move m, Cube *cube) +{ + compose_centers(&move_array[m], cube); +} + +void +apply_move_corners(Move m, Cube *cube) +{ + compose_corners(&move_array[m], cube); +} + +void +apply_move_edges(Move m, Cube *cube) +{ + compose_edges(&move_array[m], cube); +} + Alg * cleanup(Alg *alg) { diff --git a/src/moves.h b/src/moves.h @@ -7,6 +7,9 @@ void apply_alg(Alg *alg, Cube *cube); void apply_move(Move m, Cube *cube); +void apply_move_centers(Move m, Cube *cube); +void apply_move_corners(Move m, Cube *cube); +void apply_move_edges(Move m, Cube *cube); Alg * cleanup(Alg *alg); void init_moves(); diff --git a/tests/fst_post_init_tests.c b/tests/fst_post_init_tests.c @@ -0,0 +1,114 @@ +#include "fst_test_util.h" + +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", +}; + +static bool +fst_move_testcase(Cube *c, Alg *a) +{ + int i; + Cube d; + FstCube fst; + + make_solved(&d); + fst = cube_to_fst(&d); + + for (i = 0; i < a->len; i++) { + if (a->inv[i] || a->move[i] > B3) { + printf("Cannot apply the following alg to FST: "); + print_alg(a, false); + return false; + } + fst = fst_move(a->move[i], fst); + } + + fst_to_cube(fst, &d); + + return equal_and_log(c, &d); +} + +static bool +fst_inverse_testcase(Cube *c, Alg *a) +{ + Cube d; + + fst_to_cube(fst_inverse(cube_to_fst(c)), &d); + invert_cube(c); + + return equal_and_log(c, &d); +} + +static bool +fst_move_test() +{ + return try_all_str(fst_move_testcase, "FST move incorrect"); +} + +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"); +} + +void fst_post_init_testall() { + int i; + + init_fst(); + + for (i = 0; test[i] != NULL; i++) { + printf("Test: %s\n", name[i]); + if (!test[i]()) { + printf("Failed!\n"); + exit(1); + } + printf("Passed.\n\n"); + } + printf("All FST post-init tests passed.\n\n"); +} diff --git a/tests/fst_pre_init_tests.c b/tests/fst_pre_init_tests.c @@ -0,0 +1,89 @@ +#include "fst_test_util.h" + +static bool cube_to_fst_to_cube_testcase(Cube *c, Alg *a); +static bool fst_is_consistent_testcase(Cube *c, Alg *a); + +static bool fst_is_consistent_test(); +static bool cube_to_fst_to_cube_test(); + +static Tester test[] = { + fst_is_consistent_test, + cube_to_fst_to_cube_test, + NULL +}; + +static char *name[] = { + "Consistency of FST (converted from cube)", + "Cube to FST to cube", +}; + +static bool +fst_is_consistent_testcase(Cube *c, Alg *a) +{ + FstCube fst_uf, fst_fr, fst_rd; + Cube c_fr, c_rd; + bool consistent_fr, consistent_rd; + + copy_cube(c, &c_fr); + apply_trans(fr, &c_fr); + + copy_cube(c, &c_rd); + apply_trans(rd, &c_rd); + + fst_uf = cube_to_fst(c); + fst_fr = cube_to_fst(&c_fr); + fst_rd = cube_to_fst(&c_rd); + + consistent_fr = fst_uf.fr_eofb == fst_fr.uf_eofb && + fst_uf.fr_eposepe == fst_fr.uf_eposepe && + fst_uf.fr_coud == fst_fr.uf_coud; + + consistent_rd = fst_uf.rd_eofb == fst_rd.uf_eofb && + fst_uf.rd_eposepe == fst_rd.uf_eposepe && + fst_uf.rd_coud == fst_rd.uf_coud; + + return consistent_fr && consistent_rd; +} + +static bool +cube_to_fst_to_cube_testcase(Cube *c, Alg *a) +{ + Cube d; + FstCube fst; + + fst = cube_to_fst(c); + fst_to_cube(fst, &d); + + return equal_and_log(c, &d);; +} + +static bool +cube_to_fst_to_cube_test() +{ + return try_all_str( + cube_to_fst_to_cube_testcase, "Cube to FST to cube failed"); +} + +static bool +fst_is_consistent_test() +{ + return try_all_str( + fst_is_consistent_testcase, "FST from cube not consistent"); +} + +void fst_pre_init_testall() { + int i; + + init_env(); + init_trans(); + + for (i = 0; test[i] != NULL; i++) { + printf("Test: %s\n", name[i]); + if (!test[i]()) { + printf("Failed!\n"); + exit(1); + } + printf("Passed.\n\n"); + } + printf("All FST pre-init tests passed.\n\n"); +} diff --git a/tests/fst_test_util.c b/tests/fst_test_util.c @@ -0,0 +1,64 @@ +#include "fst_test_util.h" + +char *algs[] = { + "", + "U", "U2", "U'", "D", "D2", "D'", "R", "R2", "R'", + "L", "L2", "L'", "F", "F2", "F'", "B", "B2", "B'", + "U2 R2 U2 R2 U2", + "U2 F2 R2 B2 U2 D2 F2 L2 B2", + "RUR'URU2R'", + "L2 D R U2 B2 L", + "R'U'F", + "F2 U' R2 D' B2 D2 R2 D2 R2 U' F L' U' R B F2 R B' D2", + "D L2 F2 R2 D R2 U L2 U' B2 D L' F2 U2 B' L D' U' R' B2 F2", + "F' L2 F' D' R F2 L U L' D2 R2 F2 D2 R2 B' L2 B2 U2 F D2 B", + NULL, +}; + +bool +equal_and_log(Cube *c, Cube *d) +{ + bool ret = equal(c, d); + + if (!ret) { + printf("These cubes should be equal, but are not:\n\n"); + print_cube(c); + printf("\n"); + print_cube(d); + printf("\n"); + } + + return ret; +} + +bool +try_str(CubeTester f, char *algstr, char *msg) +{ + bool b; + Alg *a; + Cube c; + + a = new_alg(algstr); + make_solved(&c); + apply_alg(a, &c); + + if (!(b = f(&c, a))) + printf("%s with alg %s\n", msg, algstr); + + free_alg(a); + + return b; +} + +bool +try_all_str(CubeTester f, char *msg) +{ + bool b; + int i; + + b = true; + for (i = 0; algs[i] != NULL; i++) + b = b && try_str(f, algs[i], msg); + + return b; +} diff --git a/tests/fst_test_util.h b/tests/fst_test_util.h @@ -0,0 +1,7 @@ +#include "../src/fst.h" + +extern char *algs[]; + +bool equal_and_log(Cube *c, Cube *d); +bool try_str(CubeTester f, char *algstr, char *msg); +bool try_all_str(CubeTester f, char *msg); diff --git a/tests/inc.h b/tests/inc.h @@ -1 +0,0 @@ -#include <stdio.h> diff --git a/tests/nissy_tests.c b/tests/nissy_tests.c @@ -0,0 +1,12 @@ +#include <stdio.h> + +void fst_pre_init_testall(); +void fst_post_init_testall(); + +int main() { + fst_pre_init_testall(); + fst_post_init_testall(); + + printf("All tests passed.\n"); + return 0; +} diff --git a/tests/test_all.c b/tests/test_all.c @@ -1,10 +0,0 @@ -#include "inc.h" - -void test_fst_all(); - -int main() { - test_fst_all(); - - printf("All tests passed.\n"); - return 0; -} diff --git a/tests/test_fst.c b/tests/test_fst.c @@ -1,184 +0,0 @@ -#include "inc.h" -#include "../src/fst.h" - -static bool cube_to_fst_to_cube(Cube *c, Alg *a); -static bool fst_consistent(Cube *c, Alg *a); -static bool fst_move_test(Cube *c, Alg *a); -static bool fst_inverse_test(Cube *c, Alg *a); -static bool try_str(CubeTester f, char *algstr, char *msg); -static bool try_all_str(CubeTester f, char *msg); - -static bool test_fst_consistent_algs(); -static bool test_cube_to_fst_to_cube_algs(); -static bool test_fst_move_algs(); -static bool test_fst_inverse_algs(); - -static Tester test[] = { - test_fst_consistent_algs, - test_cube_to_fst_to_cube_algs, - test_fst_move_algs, - test_fst_inverse_algs, - NULL -}; - -static char *name[] = { - "Consistency of FST (converted from cube)", - "Cube to FST to cube", - "FST move", - "FST inverse", -}; - -static char *algs[] = { - "", - "U", "U2", "U'", "D", "D2", "D'", "R", "R2", "R'", - "L", "L2", "L'", "F", "F2", "F'", "B", "B2", "B'", - "U2 R2 U2 R2 U2", - "U2 F2 R2 B2 U2 D2 F2 L2 B2", - "RUR'URU2R'", - "L2 D R U2 B2 L", - "R'U'F", - "F2 U' R2 D' B2 D2 R2 D2 R2 U' F L' U' R B F2 R B' D2", - "D L2 F2 R2 D R2 U L2 U' B2 D L' F2 U2 B' L D' U' R' B2 F2", - "F' L2 F' D' R F2 L U L' D2 R2 F2 D2 R2 B' L2 B2 U2 F D2 B", - NULL, -}; - -static bool -fst_consistent(Cube *c, Alg *a) -{ - FstCube fst; - - fst = cube_to_fst(c); - - /* TODO: check consistency of fr_* and rd_* with uf_* */ - - return true; -} - -static bool -cube_to_fst_to_cube(Cube *c, Alg *a) -{ - Cube d; - FstCube fst; - - fst = cube_to_fst(c); - fst_to_cube(fst, &d); - - if (!equal(c, &d)) { - printf("Cubes are different:\n\n"); - printf("Cube 1:\n"); - print_cube(c); - printf("\nCube 2:\n"); - print_cube(&d); - printf("\n"); - return false; - } - - return true; -} - -static bool -fst_move_test(Cube *c, Alg *a) -{ - int i; - Cube d; - FstCube fst; - - fst = cube_to_fst(c); - - for (i = 0; i < a->len; i++) { - if (a->inv[i] || a->move[i] > B3) { - printf("Cannot apply the following alg to FST: "); - print_alg(a, false); - return false; - } - fst = fst_move(a->move[i], fst); - } - - fst_to_cube(fst, &d); - - return equal(c, &d); -} - -static bool -fst_inverse_test(Cube *c, Alg *a) -{ - Cube d; - - fst_to_cube(fst_inverse(cube_to_fst(c)), &d); - invert_cube(c); - - return equal(c, &d); -} - -static bool -try_str(CubeTester f, char *algstr, char *msg) -{ - bool b; - Alg *a; - Cube c; - - a = new_alg(algstr); - make_solved(&c); - apply_alg(a, &c); - - if (!(b = f(&c, a))) - printf("%s with alg %s\n", msg, algstr); - - free_alg(a); - - return b; -} - -static bool -try_all_str(CubeTester f, char *msg) -{ - bool b; - int i; - - b = true; - for (i = 0; algs[i] != NULL; i++) - b = b && try_str(f, algs[i], msg); - - return b; -} - -static bool -test_cube_to_fst_to_cube_algs() -{ - return try_all_str(cube_to_fst_to_cube, "Cube to FST to cube failed"); -} - -static bool -test_fst_consistent_algs() -{ - return try_all_str(fst_consistent, "FST from cube not consistent"); -} - -static bool -test_fst_move_algs() -{ - return try_all_str(fst_move_test, "FST move incorrect"); -} - -static bool -test_fst_inverse_algs() -{ - return try_all_str(fst_inverse_test, "FST test incorrect"); -} - -void test_fst_all() { - int i; - - init_trans(); - - for (i = 0; test[i] != NULL; i++) { - printf("Test: %s\n", name[i]); - if (!test[i]()) { - printf("Failed!\n"); - exit(1); - } - printf("Passed.\n\n"); - } - printf("All FST tests passed.\n\n"); -}