From cecdb7c5a0fc4821bc56c6aae5428925ec1baa15 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 26 Dec 2022 12:41:36 +0100 Subject: Fixed fst_inverse --- src/cube.c | 126 +++++++++++++++++++++++++++++++++++++++++++++++++----------- src/cube.h | 12 ++++++ src/fst.c | 75 ++++++++++++++++++++++++------------ src/fst.h | 1 + src/moves.c | 18 +++++++++ src/moves.h | 3 ++ 6 files changed, 189 insertions(+), 46 deletions(-) (limited to 'src') diff --git a/src/cube.c b/src/cube.c index c2a457c..92c6713 100644 --- 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 index 789bb2e..f182b27 100644 --- 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 index aa9e41e..df5b81f 100644 --- 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 index c3b226c..be5e99b 100644 --- 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 index 51012db..a9dfdc0 100644 --- 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 index 4afe8fb..4e8be7f 100644 --- 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(); -- cgit v1.3