nissy-nx

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

commit 445364a4b495c275e2723a05e7f4be0090ba5d0a
parent 2dce2a8a0ebd95e9e65d9d53206c4b2babc2af2f
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Sun,  9 Oct 2022 18:12:39 +0200

Finished fst, added tests. STILL NOT WORKING.

Diffstat:
M.gitignore | 5+++--
MMakefile | 16++++++++++------
MTODO.md | 17+++++++----------
Msrc/cube.c | 32++++++++++++++++++++++++++++++++
Msrc/cube.h | 3+++
Msrc/cubetypes.h | 3++-
Msrc/fst.c | 291+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------
Msrc/fst.h | 1+
Msrc/shell.c | 2++
Msrc/trans.c | 2+-
Atests/inc.h | 1+
Atests/test_all.c | 10++++++++++
Atests/test_fst.c | 88+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
13 files changed, 429 insertions(+), 42 deletions(-)

diff --git a/.gitignore b/.gitignore @@ -1,4 +1,5 @@ -nissy -nissy-* doc/*.html doc/*.pdf +nissy +nissy-* +test diff --git a/Makefile b/Makefile @@ -5,11 +5,12 @@ VERSION = post-2.0.2 PREFIX = /usr/local MANPREFIX = ${PREFIX}/share/man -CPPFLAGS = -DVERSION=\"${VERSION}\" -CFLAGS = -std=c99 -pthread -pedantic -Wall -Wextra \ - -Wno-unused-parameter -O3 ${CPPFLAGS} -DBGFLAGS = -std=c99 -pthread -pedantic -Wall -Wextra \ - -Wno-unused-parameter -g ${CPPFLAGS} +CPPFLAGS = -DVERSION=\"${VERSION}\" +CFLAGS = -std=c99 -pthread -pedantic -Wall -Wextra \ + -Wno-unused-parameter -O3 ${CPPFLAGS} +DBGFLAGS = -std=c99 -pthread -pedantic -Wall -Wextra \ + -Wno-unused-parameter -g ${CPPFLAGS} +TESTFLAGS = ${DBGFLAGS} -DTEST CC = cc @@ -19,6 +20,9 @@ all: nissy nissy: clean ${CC} ${CFLAGS} -o nissy src/*.c +test: + ${CC} ${TESTFLAGS} -o test src/*.c tests/*.c + nissy.exe: x86_64-w64-mingw32-gcc ${CFLAGS} -static -o nissy.exe src/*.c @@ -63,5 +67,5 @@ uninstall: rm -rf ${DESTDIR}${PREFIX}/bin/nissy ${DESTDIR}${MANPREFIX}/man1/nissy.1 for s in ${SCRIPTS}; do rm -rf ${DESTDIR}${PREFIX}/bin/$$s; done -.PHONY: all debug clean dist install uninstall upload +.PHONY: all debug clean dist install test uninstall upload diff --git a/TODO.md b/TODO.md @@ -4,12 +4,13 @@ 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 -### fst_cube -* slightly different from cube in v2.0.2: each "side" coordinate - is a transformation of the other, not an eorl or similar (changes - the permutation!) -* inverse: for edges, just generate ep[12] and convert back -* corners: big table (150Mb if 16bit integers are used) +### generic: +* all files should have an init function, calling the ones + of the files includes + doing more stuff. A static "initiliazed" + variable is probably needed too. +### testing! +* test fst and other things... +* move test_coord to the testing folder ### Solving standard coordinates * add Void * extradata to DfsArg and a custom move function * add optional custom pre-process for generating special table (nx) @@ -42,7 +43,6 @@ It's more of a personal reminder than anything else. check if found enough solutions before checking pruning values) ### Technical * generic option parser -* testing? Maybe just hardcode some examples generated with old nissy ### Commands * Easy: add option -I (inverse) and -L (linear, like inverse + normal) to do only linear NISS @@ -86,9 +86,6 @@ including e.g. solutions that were not shown because -c) ## Technical stuff -### Testing -* write some proper tests, move test_coord to the testing module(s) - ### Memory management * free pruning table after solve is done? if I do this I need to deafault to a small table for < 8 moves solutions or smth diff --git a/src/cube.c b/src/cube.c @@ -2,6 +2,8 @@ #include "cube.h" +static int where_is_piece(int piece, int *arr, int n); + void compose(Cube *c2, Cube *c1) { @@ -154,3 +156,33 @@ print_cube(Cube *cube) printf(" %s ", center_string[cube->xp[i]]); printf("\n"); } + +int +where_is_center(Center x, Cube *c) +{ + return where_is_piece(x, c->xp, 6); +} + +int +where_is_corner(Corner k, Cube *c) +{ + return where_is_piece(k, c->cp, 8); +} + +int +where_is_edge(Edge e, Cube *c) +{ + return where_is_piece(e, c->ep, 12); +} + +static int +where_is_piece(int piece, int *arr, int n) +{ + int i; + + for (i = 0; i < n; i++) + if (arr[i] == piece) + return i; + + return -1; +} diff --git a/src/cube.h b/src/cube.h @@ -15,6 +15,9 @@ bool is_admissible(Cube *cube); bool is_solved(Cube *cube); void make_solved(Cube *cube); void print_cube(Cube *cube); +int where_is_center(Center x, Cube *c); +int where_is_corner(Corner k, Cube *c); +int where_is_edge(Edge e, Cube *c); #endif diff --git a/src/cubetypes.h b/src/cubetypes.h @@ -108,6 +108,7 @@ typedef void (*DfsExtraCopier) (void *, void *); typedef bool (*Validator) (Alg *); typedef void (*Exec) (CommandArgs *); typedef CommandArgs * (*ArgParser) (int, char **); +typedef bool (*Tester) (void); typedef int (*TransFinder) (uint64_t, Trans *); @@ -239,7 +240,7 @@ fstcube uint16_t rd_eofb; uint16_t rd_eposepe; uint16_t rd_coud; -} +}; struct indexer diff --git a/src/fst.c b/src/fst.c @@ -2,7 +2,30 @@ #include "fst.h" -static void fst_to_ep(FstCube fst, int *ep); +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(); +static void init_fst_eo_update(uint64_t, uint64_t, int, Cube *); +static void init_fst_transalg(); +static void init_fst_where_is_edge(); + +static int edge_slice[12] = {[FR] = 0, [FL] = 0, [BL] = 0, [BR] = 0, + [UL] = 1, [UR] = 1, [DR] = 1, [DL] = 1, + [UF] = 2, [UB] = 2, [DF] = 2, [DB] = 2}; + +static uint16_t inv_coud[FACTORIAL8][POW3TO7]; +static uint16_t inv_cp[FACTORIAL8]; +static uint16_t uf_cp_to_fr_cp[FACTORIAL8]; +static uint16_t uf_cp_to_rd_cp[FACTORIAL8]; + +static int16_t eo_invtable[3][POW2TO11][BINOM12ON4*FACTORIAL4]; + +static int trans_ep_alg[NROTATIONS][12]; +static int trans_ep_inv[NROTATIONS][12]; + +static uint16_t fst_where_is_edge_arr[3][12][BINOM12ON4*FACTORIAL4]; FstCube cube_to_fst(Cube *cube) @@ -11,19 +34,39 @@ cube_to_fst(Cube *cube) FstCube ret; copy_cube(cube, &c); - ret.uf_eofb = index_eofb(&c); - ret.uf_eposepe = index_eposepe(&c); - ret.uf_coud = index_coud(&c); - ret.uf_cp = index_cp(&c); + ret.uf_eofb = coord_eofb.i[0]->index(&c); + ret.uf_eposepe = coord_eposepe.i[0]->index(&c); + ret.uf_coud = coord_coud.i[0]->index(&c); + ret.uf_cp = coord_cp.i[0]->index(&c); copy_cube(cube, &c); - transform_cube(fr, &c); - ret.fr_eofb = index_eofb(&c); - ret.fr_eposepe = index_eposepe(&c); - ret.fr_coud = index_coud(&c); - transform_cube(rd, &c); - ret.rd_eofb = index_eofb(&c); - ret.rd_eposepe = index_eposepe(&c); - ret.rd_coud = index_coud(&c); + apply_trans(fr, &c); + ret.fr_eofb = coord_eofb.i[0]->index(&c); + ret.fr_eposepe = coord_eposepe.i[0]->index(&c); + ret.fr_coud = coord_coud.i[0]->index(&c); + apply_trans(rd, &c); + ret.rd_eofb = coord_eofb.i[0]->index(&c); + ret.rd_eposepe = coord_eposepe.i[0]->index(&c); + ret.rd_coud = coord_coud.i[0]->index(&c); + + return ret; +} + +static FstCube +ep_to_fst_epos(int *ep) +{ + /* TODO: maybe optimize? */ + + 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); return ret; } @@ -31,28 +74,232 @@ cube_to_fst(Cube *cube) FstCube fst_inverse(FstCube fst) { - /* TODO */ + FstCube ret; + int i, ep_inv[12]; + + 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]) | + ((uint16_t)eo_invtable[1][fst.uf_eofb][fst.fr_eposepe]) | + ((uint16_t)eo_invtable[2][fst.uf_eofb][fst.rd_eposepe]); + ret.fr_eofb = ((uint16_t)eo_invtable[0][fst.fr_eofb][fst.uf_eposepe]) | + ((uint16_t)eo_invtable[1][fst.fr_eofb][fst.fr_eposepe]) | + ((uint16_t)eo_invtable[2][fst.fr_eofb][fst.rd_eposepe]); + ret.rd_eofb = ((uint16_t)eo_invtable[0][fst.rd_eofb][fst.uf_eposepe]) | + ((uint16_t)eo_invtable[1][fst.rd_eofb][fst.fr_eposepe]) | + ((uint16_t)eo_invtable[2][fst.rd_eofb][fst.rd_eposepe]); + + ret.uf_cp = inv_cp[fst.uf_cp]; + + ret.uf_coud = inv_coud[fst.uf_cp][fst.uf_coud]; + ret.fr_coud = inv_coud[uf_cp_to_fr_cp[fst.uf_cp]][fst.fr_coud]; + ret.rd_coud = inv_coud[uf_cp_to_rd_cp[fst.uf_cp]][fst.rd_coud]; + + return ret; } FstCube fst_move(Move m, FstCube fst) { - /* TODO */ + FstCube ret; + Move m_fr, m_rd; + + m_fr = transform_move(fr, m); + m_rd = transform_move(rd, m); + + ret.uf_eofb = coord_eofb.mtable[m][fst.uf_eofb]; + ret.uf_eposepe = coord_eposepe.mtable[m][fst.uf_eposepe]; + ret.uf_coud = coord_coud.mtable[m][fst.uf_coud]; + ret.uf_cp = coord_cp.mtable[m][fst.uf_cp]; + + ret.fr_eofb = coord_eofb.mtable[m_fr][fst.fr_eofb]; + ret.fr_eposepe = coord_eposepe.mtable[m_fr][fst.fr_eposepe]; + ret.fr_coud = coord_coud.mtable[m_fr][fst.fr_coud]; + + ret.rd_eofb = coord_eofb.mtable[m_rd][fst.rd_eofb]; + ret.rd_eposepe = coord_eposepe.mtable[m_rd][fst.rd_eposepe]; + ret.rd_coud = coord_coud.mtable[m_rd][fst.rd_coud]; + + return ret; } void fst_to_cube(FstCube fst, Cube *cube) { - invindex_eofb((uint64_t)fst.uf_eofb, cube); - fst_to_ep(fst, cube->ep); - invindex_coud((uint64_t)fst.uf_coud, cube); - invindex_cp((uint64_t)fst.uf_cp, cube); + Cube e, s, m; + int i; + + coord_eposepe.i[0]->to_cube(fst.uf_eposepe, &e); + coord_eposepe.i[0]->to_cube(fst.fr_eposepe, &s); + apply_trans(inverse_trans(fr), &s); + coord_eposepe.i[0]->to_cube(fst.rd_eposepe, &m); + apply_trans(inverse_trans(rd), &m); + + for (i = 0; i < 12; i++) { + if (edge_slice[e.ep[i]] == 0) + cube->ep[i] = e.ep[i]; + if (edge_slice[s.ep[i]] == 1) + cube->ep[i] = s.ep[i]; + if (edge_slice[m.ep[i]] == 2) + cube->ep[i] = m.ep[i]; + } + + coord_eofb.i[0]->to_cube((uint64_t)fst.uf_eofb, cube); + coord_coud.i[0]->to_cube((uint64_t)fst.uf_coud, cube); + coord_cp.i[0]->to_cube((uint64_t)fst.uf_cp, cube); +} + +static 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() +{ + init_fst_corner_invtables(); + init_fst_eo_invtables(); + init_fst_transalg(); + init_fst_where_is_edge(); +} + +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); + coord_cp.i[0]->to_cube(cp, &c); + + copy_cube(&c, &d); + invert_cube(&d); + inv_cp[cp] = coord_coud.i[0]->index(&d); + + for (coud = 0; coud < POW3TO7; coud++) { + copy_cube(&c, &d); + coord_coud.i[0]->to_cube(coud, &d); + invert_cube(&d); + inv_coud[cp][coud] = coord_coud.i[0]->index(&d); + } + + copy_cube(&c, &d); + apply_trans(fr, &d); + uf_cp_to_fr_cp[cp] = coord_cp.i[0]->index(&d); + + copy_cube(&c, &d); + apply_trans(rd, &d); + uf_cp_to_rd_cp[cp] = coord_cp.i[0]->index(&d); + } +} + +static void +init_fst_eo_invtables() +{ + uint64_t ep, eo; + Cube c, d; + + for (ep = 0; ep < BINOM12ON4 * FACTORIAL4; ep++) { + 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); + init_fst_eo_update(eo, ep, 0, &d); + apply_trans(inverse_trans(fr), &d); + init_fst_eo_update(eo, ep, 1, &d); + copy_cube(&c, &d); + apply_trans(inverse_trans(rd), &d); + init_fst_eo_update(eo, ep, 2, &d); + } + } } static void -fst_to_ep(FstCube fst, int *ep) +init_fst_eo_update(uint64_t eo, uint64_t ep, int s, Cube *d) { - /* TODO */ + int i; + + for (i = 0; i < 12; i++) + if (d->eo[i]) + eo_invtable[s][eo][ep] |= ((uint16_t)1) << d->ep[i]; } -#endif +static void +init_fst_transalg() +{ + Trans t; + Alg *alg; + Cube c; + int i; + + for (t = uf; t < NROTATIONS; t++) { + make_solved(&c); + alg = rotation_alg(t); + apply_alg(alg, &c); + for (i = 0; i < 12; i++) + trans_ep_alg[t][i] = c.ep[i]; + invert_cube(&c); + for (i = 0; i < 12; i++) + trans_ep_inv[t][i] = c.ep[i]; + } +} + +static void +init_fst_where_is_edge() +{ + Cube c, d; + uint64_t e; + + init_trans(); + + make_solved(&c); + for (e = 0; e < BINOM12ON4 * FACTORIAL4; e++) { + coord_eposepe.i[0]->to_cube(e, &c); + + copy_cube(&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); + 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); + 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); + fst_where_is_edge_arr[2][DF][e] = where_is_edge(DF, &d); + fst_where_is_edge_arr[2][DB][e] = where_is_edge(DB, &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); +void init_fst(); #endif diff --git a/src/shell.c b/src/shell.c @@ -142,6 +142,7 @@ launch(bool batchmode) free(shell_argv); } +#ifndef TEST int main(int argc, char *argv[]) { @@ -187,3 +188,4 @@ main(int argc, char *argv[]) return 0; } +#endif diff --git a/src/trans.c b/src/trans.c @@ -26,7 +26,7 @@ static char rotation_alg_string[100][NROTATIONS] = { [bu] = "x3", [br] = "x3 y", [bd] = "x3 y2", [bl] = "x3 y3", }; -static Alg *rotation_alg_arr[NROTATIONS]; +Alg *rotation_alg_arr[NROTATIONS]; Move moves_ttable[NTRANS][NMOVES]; Trans trans_ttable[NTRANS][NTRANS]; Trans trans_itable[NTRANS]; diff --git a/tests/inc.h b/tests/inc.h @@ -0,0 +1 @@ +#include <stdio.h> diff --git a/tests/test_all.c b/tests/test_all.c @@ -0,0 +1,10 @@ +#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 @@ -0,0 +1,88 @@ +#include "inc.h" +#include "../src/fst.h" + +static bool test_cube_to_fst_to_cube(Cube *c); + +static bool test_cube_to_fst_to_cube_solved(); +static bool test_cube_to_fst_to_cube_unsolved(); + +static Tester test[] = { + test_cube_to_fst_to_cube_solved, + test_cube_to_fst_to_cube_unsolved, + NULL +}; + +static char *name[] = { + "Cube to FST to cube (solved)", + "Cube to FST to cube (unsolved)", +}; + +static bool +test_cube_to_fst_to_cube(Cube *c) +{ + Cube d; + FstCube fst; + + fst = cube_to_fst(c); + fst_to_cube(fst, &d); + + return equal(c, &d); +} + +static bool +test_cube_to_fst_to_cube_solved() +{ + Cube c; + + make_solved(&c); + return test_cube_to_fst_to_cube(&c); +} + +static bool +test_cube_to_fst_to_cube_unsolved() +{ + bool b; + int i; + Alg *a; + Cube c; + char *algs[] = { + "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, + }; + + for (i = 0; algs[i] != NULL; i++) { + make_solved(&c); + a = new_alg(algs[i]); + apply_alg(a, &c); + b = test_cube_to_fst_to_cube(&c); + free_alg(a); + if (!b) { + printf("Failed with alg %s\n", algs[i]); + return false; + } + } + return true; +} + +void test_fst_all() { + 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"); + } + printf("All FST tests passed.\n\n"); +}