From 3568412f8f230774d0d11d7ed1c897424f95d3ef Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 11 Nov 2021 21:37:34 +0100 Subject: Rewritten from scratch. Welocme nissy 2.0! --- old/2021-02-28-transformcube-works/src/cube.c | 271 ++++++++++++ old/2021-02-28-transformcube-works/src/cube.h | 55 +++ old/2021-02-28-transformcube-works/src/main.c | 57 +++ old/2021-02-28-transformcube-works/src/moves.c | 489 +++++++++++++++++++++ old/2021-02-28-transformcube-works/src/moves.h | 50 +++ old/2021-02-28-transformcube-works/src/solve.c | 180 ++++++++ old/2021-02-28-transformcube-works/src/solve.h | 56 +++ .../src/transformations.c | 224 ++++++++++ .../src/transformations.h | 34 ++ old/2021-02-28-transformcube-works/src/utils.c | 197 +++++++++ old/2021-02-28-transformcube-works/src/utils.h | 70 +++ 11 files changed, 1683 insertions(+) create mode 100644 old/2021-02-28-transformcube-works/src/cube.c create mode 100644 old/2021-02-28-transformcube-works/src/cube.h create mode 100644 old/2021-02-28-transformcube-works/src/main.c create mode 100644 old/2021-02-28-transformcube-works/src/moves.c create mode 100644 old/2021-02-28-transformcube-works/src/moves.h create mode 100644 old/2021-02-28-transformcube-works/src/solve.c create mode 100644 old/2021-02-28-transformcube-works/src/solve.h create mode 100644 old/2021-02-28-transformcube-works/src/transformations.c create mode 100644 old/2021-02-28-transformcube-works/src/transformations.h create mode 100644 old/2021-02-28-transformcube-works/src/utils.c create mode 100644 old/2021-02-28-transformcube-works/src/utils.h (limited to 'old/2021-02-28-transformcube-works/src') diff --git a/old/2021-02-28-transformcube-works/src/cube.c b/old/2021-02-28-transformcube-works/src/cube.c new file mode 100644 index 0000000..649a4de --- /dev/null +++ b/old/2021-02-28-transformcube-works/src/cube.c @@ -0,0 +1,271 @@ +#include "cube.h" + +typedef struct { + int ep[12],eofb[12],eorl[12],eoud[12],cp[8],coud[8],corl[8],cofb[8],cpos[6]; +} CubeArrayAllocated; + +void allocate_cubearray(CubeArray *arr, CubeArrayAllocated *all); + +char edge_string[12][5] = + { "UF", "UL", "UB", "UR", "DF", "DL", "DB", "DR", "FR", "FL", "BL", "BR" }; +char corner_string[8][5] = { "UFR","UFL","UBL","UBR","DFR","DFL","DBL","DBR" }; +char center_string[6][5] = { "U", "D", "R", "L", "F", "B" }; + +int epe_solved[4] = {FR, FL, BL, BR}; +int eps_solved[4] = {UL, UR, DL, DR}; +int epm_solved[4] = {UF, UB, DF, DB}; + +PieceFilter pf_all = {true,true,true,true,true,true,true,true,true,true,true}, + pf_cpos = { .cpos = true }, pf_cp = { .cp = true }, + pf_ep = { .epose = true, .eposs = true, .eposm = true }, + pf_e = {.epose=true}, pf_s={.eposs=true}, pf_m={.eposm=true}, + pf_eo = { .eofb = true, .eorl = true, .eoud = true }, + pf_co = { .coud = true, .cofb = true, .corl = true }; + +void allocate_cubearray(CubeArray *arr, CubeArrayAllocated *all) { + arr->ep = all->ep; + arr->eofb = all->eofb; + arr->eorl = all->eorl; + arr->eoud = all->eoud; + arr->cp = all->cp; + arr->coud = all->coud; + arr->corl = all->corl; + arr->cofb = all->cofb; + arr->cpos = all->cpos; +} + +void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f) { + /* ep is the hardest */ + if (f.epose || f.eposs || f.eposm) + for (int i = 0; i < 12; i++) arr->ep[i] = -1; + if (f.epose) { + int epe[4], epose[12]; + index_to_perm(cube.epose % factorial(4), 4, epe); + index_to_subset(cube.epose / factorial(4), 12, 4, epose); + for (int i = 0, ie = 0; i < 12; i++) + if (epose[i]) arr->ep[i] = epe_solved[epe[ie++]]; + } + if (f.eposs) { + int eps[4], eposs[12]; + index_to_perm(cube.eposs % factorial(4), 4, eps); + index_to_subset(cube.eposs / factorial(4), 12, 4, eposs); + for (int i = 0; i < 4; i++) swap(&eposs[eps_solved[i]], &eposs[i+8]); + for (int i = 0, is = 0; i < 12; i++) + if (eposs[i]) arr->ep[i] = eps_solved[eps[is++]]; + } + if (f.eposm) { + int epm[4], eposm[12]; + index_to_perm(cube.eposm % factorial(4), 4, epm); + index_to_subset(cube.eposm / factorial(4), 12, 4, eposm); + for (int i = 0; i < 4; i++) swap(&eposm[epm_solved[i]], &eposm[i+8]); + for (int i = 0, im = 0; i < 12; i++) + if (eposm[i]) arr->ep[i] = epm_solved[epm[im++]]; + } + + /* All the others */ + if (f.eofb) int_to_sum_zero_array(cube.eofb, 2, 12, arr->eofb); + if (f.eorl) int_to_sum_zero_array(cube.eorl, 2, 12, arr->eorl); + if (f.eoud) int_to_sum_zero_array(cube.eoud, 2, 12, arr->eoud); + if (f.cp) index_to_perm( cube.cp, 8, arr->cp); + if (f.coud) int_to_sum_zero_array(cube.coud, 3, 8, arr->coud); + if (f.corl) int_to_sum_zero_array(cube.corl, 3, 8, arr->corl); + if (f.cofb) int_to_sum_zero_array(cube.cofb, 3, 8, arr->cofb); + if (f.cpos) index_to_perm( cube.cpos, 6, arr->cpos); +} + +Cube arrays_to_cube(CubeArray arr, PieceFilter f) { + Cube ret = {0}; + + /* Again, ep is the hardest part */ + if (f.epose) { + int epe[4], epose[12] = {0,0,0,0,0,0,0,0,0,0,0,0}; + for (int i = 0, ie = 0; i < 12; i++) + for (int j = 0; j < 4; j++) + if (arr.ep[i] == epe_solved[j]) + { epe[ie++] = j; epose[i] = 1; } + ret.epose = factorial(4)*subset_to_index(epose,12,4)+perm_to_index(epe,4); + } + if (f.eposs) { + int eps[4], eposs[12] = {0,0,0,0,0,0,0,0,0,0,0,0}; + for (int i = 0, is = 0; i < 12; i++) + for (int j = 0; j < 4; j++) + if (arr.ep[i] == eps_solved[j]) + { eps[is++] = j; eposs[i] = 1; } + for (int i = 0; i < 4; i++) swap(&eposs[eps_solved[i]], &eposs[i+8]); + ret.eposs = factorial(4)*subset_to_index(eposs,12,4)+perm_to_index(eps,4); + } + if (f.eposm) { + int epm[4], eposm[12] = {0,0,0,0,0,0,0,0,0,0,0,0}; + for (int i = 0, im = 0; i < 12; i++) + for (int j = 0; j < 4; j++) + if (arr.ep[i] == epm_solved[j]) + { epm[im++] = j; eposm[i] = 1; } + for (int i = 0; i < 4; i++) swap(&eposm[epm_solved[i]], &eposm[i+8]); + ret.eposm = factorial(4)*subset_to_index(eposm,12,4)+perm_to_index(epm,4); + } + if (f.eofb) ret.eofb = digit_array_to_int(arr.eofb, 11, 2); + if (f.eorl) ret.eorl = digit_array_to_int(arr.eorl, 11, 2); + if (f.eoud) ret.eoud = digit_array_to_int(arr.eoud, 11, 2); + if (f.cp) ret.cp = perm_to_index( arr.cp, 8 ); + if (f.coud) ret.coud = digit_array_to_int(arr.coud, 7, 3); + if (f.corl) ret.corl = digit_array_to_int(arr.corl, 7, 3); + if (f.cofb) ret.cofb = digit_array_to_int(arr.cofb, 7, 3); + if (f.cpos) ret.cpos = perm_to_index( arr.cpos, 6 ); + + return ret; +} + +Center center_at(Cube cube, Center c) { + static CubeArrayAllocated all = {0}; + CubeArray arr = {0}; + allocate_cubearray(&arr, &all); + cube_to_arrays(cube, &arr, pf_cpos); + return arr.cpos[c]; +} + +Edge edge_at(Cube cube, Edge e) { + static CubeArrayAllocated all = {0}; + CubeArray arr = {0}; + allocate_cubearray(&arr, &all); + cube_to_arrays(cube, &arr, pf_ep); + return arr.ep[e]; +} + +Corner corner_at(Cube cube, Corner c) { + static CubeArrayAllocated all = {0}; + CubeArray arr = {0}; + allocate_cubearray(&arr, &all); + cube_to_arrays(cube, &arr, pf_cp); + return arr.cp[c]; +} + +bool equal(Cube c1, Cube c2) { + return c1.eofb == c2.eofb && c1.epose == c2.epose && + c1.eposs == c2.eposs && c1.eposm == c2.eposm && + c1.coud == c2.coud && c1.cp == c2.cp && + c1.cpos == c2.cpos; +} + +bool is_solvable(Cube cube) { + static CubeArrayAllocated all = {0}; + CubeArray arrx = {0}; + allocate_cubearray(&arrx, &all); + cube_to_arrays(cube, &arrx, pf_all); + + /* Since we memorize orientation truncating the last digit, we only need to + * check that the permutations have the correct sign. */ + /* TODO: I should also check that the different eos and cos are compatible */ + return (perm_sign(arrx.ep,12)^perm_sign(arrx.cpos,6))==perm_sign(arrx.cp,8); +} + +bool is_solved(Cube cube) { + /* TODO: might return true if cube is not solvable but looks solved form one + of the incompatible interpretations (e.g. eofb and ep solved, but + eorl not solve) */ + return !cube.eofb && !cube.coud && !cube.cp && + !cube.epose && !cube.eposs && !cube.eposm && cube.cpos; +} + +void print_cube(Cube cube) { + static CubeArrayAllocated all = {0}; + CubeArray arrx = {0}; + allocate_cubearray(&arrx, &all); + + cube_to_arrays(cube, &arrx, pf_all); + +/* + for (int i = 0; i < 12; i++) printf("%d ", arrx.ep[i]); + printf("\n");*/ + + for (int i = 0; i < 12; i++) printf(" %s ", edge_string[arrx.ep[i]]); + printf("\n"); + for (int i = 0; i < 12; i++) printf(" %c ", arrx.eofb[i] + '0'); + printf("\n"); + for (int i = 0; i < 8; i++) printf("%s ", corner_string[arrx.cp[i]]); + printf("\n"); + for (int i = 0; i < 8; i++) printf(" %c ", arrx.coud[i] + '0'); + printf("\n"); + for (int i = 0; i < 6; i++) printf(" %s ", center_string[arrx.cpos[i]]); + printf("\n"); +} + +Cube admissible_ep(Cube cube, PieceFilter f) { + static CubeArrayAllocated all = {0}; + CubeArray arrx = {0}; + allocate_cubearray(&arrx, &all); + cube_to_arrays(cube, &arrx, f); + + bool used[12] = {0}; + for (int i = 0; i < 12; i++) + if (arrx.ep[i] != -1) + used[arrx.ep[i]] = true; + for (int i = 0, j = 0; i < 12; i++) { + while (j < 11 && used[j]) j++; + if (arrx.ep[i] == -1) + arrx.ep[i] = j++; + } + + return arrays_to_cube(arrx, pf_ep); +} + +Cube inverse_cube(Cube cube) { + static CubeArrayAllocated all = {0}, invall = {0}; + CubeArray arrx = {0}, invx = {0}; + allocate_cubearray(&arrx, &all); + allocate_cubearray(&invx, &invall); + + cube_to_arrays(cube, &arrx, pf_all); + + for (int i = 0; i < 12; i++) { + invx.ep[arrx.ep[i]] = i; + invx.eofb[arrx.ep[i]] = arrx.eofb[i]; + invx.eorl[arrx.ep[i]] = arrx.eorl[i]; + invx.eoud[arrx.ep[i]] = arrx.eoud[i]; + } + for (int i = 0; i < 8; i++) { + invx.cp[arrx.cp[i]] = i; + invx.coud[arrx.cp[i]] = (3 - arrx.coud[i])%3; + invx.corl[arrx.cp[i]] = (3 - arrx.corl[i])%3; + invx.cofb[arrx.cp[i]] = (3 - arrx.cofb[i])%3; + } + for (int i = 0; i < 6; i++) + invx.cpos[arrx.cpos[i]] = i; + + return arrays_to_cube(invx, pf_all); +} + +Cube move_via_arrays(CubeArray arr, Cube c, PieceFilter f) { + static CubeArrayAllocated all = {0}; + CubeArray arrx = {0}; + allocate_cubearray(&arrx, &all); + + cube_to_arrays(c, &arrx, f); + + if (f.epose || f.eposs || f.eposm) + apply_permutation( arr.ep, arrx.ep, 12 ); + if (f.eofb) { apply_permutation( arr.ep, arrx.eofb, 12 ); + sum_arrays_mod( arr.eofb, arrx.eofb, 12, 2 ); } + if (f.eorl) { apply_permutation( arr.ep, arrx.eorl, 12 ); + sum_arrays_mod( arr.eorl, arrx.eorl, 12, 2 ); } + if (f.eoud) { apply_permutation( arr.ep, arrx.eoud, 12 ); + sum_arrays_mod( arr.eoud, arrx.eoud, 12, 2 ); } + if (f.cp) apply_permutation( arr.cp, arrx.cp, 8 ); + if (f.coud) { apply_permutation( arr.cp, arrx.coud, 8 ); + sum_arrays_mod( arr.coud, arrx.coud, 8, 3 ); } + if (f.corl) { apply_permutation( arr.cp, arrx.corl, 8 ); + sum_arrays_mod( arr.corl, arrx.corl, 8, 3 ); } + if (f.cofb) { apply_permutation( arr.cp, arrx.cofb, 8 ); + sum_arrays_mod( arr.cofb, arrx.cofb, 8, 3 ); } + if (f.cpos) apply_permutation( arr.cpos, arrx.cpos, 6 ); + + return arrays_to_cube(arrx, f); +} + +Cube compose(Cube c2, Cube c1) { + static CubeArrayAllocated all = {0}; + CubeArray arrx = {0}; + allocate_cubearray(&arrx, &all); + + cube_to_arrays(c2, &arrx, pf_all); + return move_via_arrays(arrx, c1, pf_all); +} diff --git a/old/2021-02-28-transformcube-works/src/cube.h b/old/2021-02-28-transformcube-works/src/cube.h new file mode 100644 index 0000000..3229eae --- /dev/null +++ b/old/2021-02-28-transformcube-works/src/cube.h @@ -0,0 +1,55 @@ +#ifndef CUBE_H +#define CUBE_H + +#include +#include +#include +#include "utils.h" + +typedef enum {U_center,D_center,R_center,L_center,F_center,B_center} Center; +typedef enum { UF, UL, UB, UR, DF, DL, DB, DR, FR, FL, BL, BR } Edge; +typedef enum { UFR, UFL, UBL, UBR, DFR, DFL, DBL, DBR } Corner; + +typedef struct { + uint16_t eofb, eorl, eoud, coud, cofb, corl, + epose, eposs, eposm, cp, cpos; +} Cube; + +typedef struct { + bool epose, eposs, eposm, eofb, eorl, eoud, cp, coud, cofb, corl, cpos; +} PieceFilter; + +typedef struct { + int *ep, *eofb, *eorl, *eoud, *cp, *coud, *corl, *cofb, *cpos; +} CubeArray; + +extern PieceFilter pf_all, pf_cpos, pf_ep, pf_cp, + pf_e, pf_s, pf_m, pf_eo, pf_co; + +void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f); +Cube arrays_to_cube(CubeArray arr, PieceFilter f); + +Center center_at(Cube cube, Center c); +Edge edge_at(Cube cube, Edge e); +Corner corner_at(Cube cube, Corner c); +/* Aggiungi funzioni per "queries" sul cubo: se pezzo è orientato rispetto ad + un certo asse, se il pezzo è risolto... */ +/* Would be nice: a funciton block_solved(Cube c, Block b), where Block is + something like struct {bool centers[6], edges[12], corners[8]} + (The advantage over checking pieces one by one is that I can convert + to cubearray only once and for all) */ +/* Altro TODO, ma forse non ne vale la pena: pre-calcolare tutti i possibili + valori per questi, e salvare i risultati in array (facile per cp e cpos, + mentre per ep bisogna anche cercare quale tra epose, eposs e eposm contiene + il valore giusto) */ + +bool equal(Cube c1, Cube c2); +bool is_solvable(Cube cube); +bool is_solved(Cube cube); +void print_cube(Cube cube); +Cube admissible_ep(Cube cube, PieceFilter f); /* Returns admissible ep */ +Cube inverse_cube(Cube cube); +Cube compose(Cube c2, Cube c1); /* Use c2 as an alg on c1 */ +Cube move_via_arrays(CubeArray arr, Cube c, PieceFilter pf); + +#endif diff --git a/old/2021-02-28-transformcube-works/src/main.c b/old/2021-02-28-transformcube-works/src/main.c new file mode 100644 index 0000000..56f3f3b --- /dev/null +++ b/old/2021-02-28-transformcube-works/src/main.c @@ -0,0 +1,57 @@ +#include +#include "cube.h" +#include "moves.h" +#include "solve.h" +#include "transformations.h" + +int main() { + init_ttables(true, true); + init_aux_tables(); + init_transformations(true, true); + + + /*char moves[100] = "MR U' B2 Bw F z xE2 M' x Dw' y Fw2";*/ + + /*char moves[100] = "M'U2MU2";*/ + char moves[100] = "R' D2 F2 U2 R F2 R D2 L' R2 D2 F D' L' U' B R' D' U R' B"; + NissMove alg[100]; + read_moves(moves, alg, 100); + Cube cube = apply_alg(alg, (Cube){0}); + print_cube(cube); + cube = transform_cube(rd, cube); + print_cube(cube); + + /*f_eofb(cube);*/ + + + /* + SolveData d = { .optimal_only = true, .available = standard_moveset, + .max_moves = 10, + .cleanup = true, + .max_solutions = 10, + .f = f_eofb }; + read_moves("y", d.pre_rotation, 2); + int n = solve(cube, &d); + printf("%d solutions found:\n", n); + for (int i = 0; i < n; i++) + print_moves(d.solutions[i]); + */ + +/* + NissMove a[5], b[5]; + read_moves("R", a, 5); + read_moves("U", b, 5); + Cube c1 = apply_alg(a,(Cube){0}), c2 = apply_alg(b,(Cube){0}); + print_cube(compose(c2,c1)); + print_cube(compose(c1,c2)); + + NissMove nm[10]; + read_moves("y(y)RU", nm, 10); + + print_moves(nm); + cleanup(nm, 10); + print_moves(nm); + */ + + return 0; +} diff --git a/old/2021-02-28-transformcube-works/src/moves.c b/old/2021-02-28-transformcube-works/src/moves.c new file mode 100644 index 0000000..4b0eee1 --- /dev/null +++ b/old/2021-02-28-transformcube-works/src/moves.c @@ -0,0 +1,489 @@ +#include "moves.h" + +Cube apply_move_cubearray(Move m, Cube cube, PieceFilter f); +/* void sort_cancel_rotate(NissMove *alg, int n, bool inv, int top, int front); */ +bool read_ttables_file(); +bool write_ttables_file(); + +/* Transition tables */ +uint16_t epose_ttable[NMOVES][factorial12/factorial8]; +uint16_t eposs_ttable[NMOVES][factorial12/factorial8]; +uint16_t eposm_ttable[NMOVES][factorial12/factorial8]; +uint16_t eofb_ttable[NMOVES][pow2to11]; +uint16_t eorl_ttable[NMOVES][pow2to11]; +uint16_t eoud_ttable[NMOVES][pow2to11]; +uint16_t cp_ttable[NMOVES][factorial8]; +uint16_t coud_ttable[NMOVES][pow3to7]; +uint16_t cofb_ttable[NMOVES][pow3to7]; +uint16_t corl_ttable[NMOVES][pow3to7]; +uint16_t cpos_ttable[NMOVES][factorial6]; + +bool commute[NMOVES][NMOVES]; +bool possible_next[NMOVES][NMOVES][NMOVES]; +Move inverse[NMOVES]; +NissMove rotation_algs[24][3] = { + { { .m = NULLMOVE }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = y }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = y2 }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = y3 }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = z2 }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = y }, { .m = z2 }, { .m = NULLMOVE } }, + { { .m = x2 }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = y3 }, { .m = z2 }, { .m = NULLMOVE } }, + { { .m = z3 }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = z3 }, { .m = y }, { .m = NULLMOVE } }, + { { .m = z3 }, { .m = y2 }, { .m = NULLMOVE } }, + { { .m = z3 }, { .m = y3 }, { .m = NULLMOVE } }, + { { .m = z }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = z }, { .m = y3 }, { .m = NULLMOVE } }, + { { .m = z }, { .m = y2 }, { .m = NULLMOVE } }, + { { .m = z }, { .m = y }, { .m = NULLMOVE } }, + { { .m = x }, { .m = y2 }, { .m = NULLMOVE } }, + { { .m = x }, { .m = y }, { .m = NULLMOVE } }, + { { .m = x }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = x }, { .m = y3 }, { .m = NULLMOVE } }, + { { .m = x3 }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = x3 }, { .m = y }, { .m = NULLMOVE } }, + { { .m = x3 }, { .m = y2 }, { .m = NULLMOVE } }, + { { .m = x3 }, { .m = y3 }, { .m = NULLMOVE } }, +}; + +char move_string[NMOVES][5] = + { "-", + "U", "U2", "U\'", "D", "D2", "D\'", "R", "R2", "R\'", + "L", "L2", "L\'", "F", "F2", "F\'", "B", "B2", "B\'", + "Uw", "Uw2", "Uw\'", "Dw", "Dw2", "Dw\'", "Rw", "Rw2", "Rw\'", + "Lw", "Lw2", "Lw\'", "Fw", "Fw2", "Fw\'", "Bw", "Bw2", "Bw\'", + "M", "M2", "M\'", "S", "S2", "S\'", "E", "E2", "E\'", + "x", "x2", "x\'", "y", "y2", "y\'", "z", "z2", "z\'" }; + +/* For each type of pieces only the effects of U, x and y are described */ +int edge_cycle[NMOVES][12] = + { [U] = {UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR}, + [x] = {DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR}, + [y] = {UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL} }; +int eofb_flipped[NMOVES][12] = + { [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 }, + [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 } }; +int eorl_flipped[NMOVES][12] = + { [x] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, + [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 } }; +int eoud_flipped[NMOVES][12] = + { [U] = { [UF] = 1, [UL] = 1, [UB] = 1, [UR] = 1 }, + [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 }, + [y] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } }; +int corner_cycle[NMOVES][8] = + { [U] = {UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR}, + [x] = {DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR}, + [y] = {UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL} }; +int coud_flipped[NMOVES][8] = + { [x] = {[UFR]=2,[UBR]=1,[DBR]=2,[DFR]=1,[UFL]=1,[UBL]=2,[DBL]=1,[DFL]=2} }; +int corl_flipped[NMOVES][8] = + { [U] = { [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2 }, + [y] = {[UFR]=1,[UBR]=2,[UBL]=1,[UFL]=2,[DFR]=2,[DBR]=1,[DBL]=2,[DFL]=1} }; +int cofb_flipped[NMOVES][8] = + { [U] = { [UFR] = 2, [UBR] = 1, [UBL] = 2, [UFL] = 1 }, + [x] = {[UFR]=1,[UBR]=2,[DFR]=2,[DBR]=1,[UBL]=1,[UFL]=2,[DBL]=2,[DFL]=1}, + [y] = {[UFR]=2,[UBR]=1,[UBL]=2,[UFL]=1,[DFR]=1,[DBR]=2,[DBL]=1,[DFL]=2} }; +int center_cycle[NMOVES][6] = + { [x] = {F_center, B_center, R_center, L_center, D_center, U_center}, + [y] = {U_center, D_center, B_center, F_center, R_center, L_center} }; + +/* Each move is reduced to a combination of U, x and y using this table */ +Move equiv_moves[NMOVES][14] = { + [U] = { U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [U2] = { U, U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [U3] = { U, U, U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [D] = { x, x, U, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [D2] = { x, x, U, U, x, x, 0, 0, 0, 0, 0, 0, 0, 0 }, + [D3] = { x, x, U, U, U, x, x, 0, 0, 0, 0, 0, 0, 0 }, + [R] = { y, x, U, x, x, x, y, y, y, 0, 0, 0, 0, 0 }, + [R2] = { y, x, U, U, x, x, x, y, y, y, 0, 0, 0, 0 }, + [R3] = { y, x, U, U, U, x, x, x, y, y, y, 0, 0, 0 }, + [L] = { y, y, y, x, U, x, x, x, y, 0, 0, 0, 0, 0 }, + [L2] = { y, y, y, x, U, U, x, x, x, y, 0, 0, 0, 0 }, + [L3] = { y, y, y, x, U, U, U, x, x, x, y, 0, 0, 0 }, + [F] = { x, U, x, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [F2] = { x, U, U, x, x, x, 0, 0, 0, 0, 0, 0, 0, 0 }, + [F3] = { x, U, U, U, x, x, x, 0, 0, 0, 0, 0, 0, 0 }, + [B] = { x, x, x, U, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [B2] = { x, x, x, U, U, x, 0, 0, 0, 0, 0, 0, 0, 0 }, + [B3] = { x, x, x, U, U, U, x, 0, 0, 0, 0, 0, 0, 0 }, + + [Uw] = { x, x, U, x, x, y, 0, 0, 0, 0, 0, 0, 0, 0 }, + [Uw2] = { x, x, U, U, x, x, y, y, 0, 0, 0, 0, 0, 0 }, + [Uw3] = { x, x, U, U, U, x, x, y, y, y, 0, 0, 0, 0 }, + [Dw] = { U, y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [Dw2] = { U, U, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [Dw3] = { U, U, U, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [Rw] = { y, y, y, x, U, x, x, x, y, x, 0, 0, 0, 0 }, + [Rw2] = { y, y, y, x, U, U, x, x, x, y, x, x, 0, 0 }, + [Rw3] = { y, y, y, x, U, U, U, y, x, x, x, y, 0, 0 }, + [Lw] = { y, x, U, x, x, x, y, y, y, x, x, x, 0, 0 }, + [Lw2] = { y, x, U, U, x, x, x, y, y, y, x, x, 0, 0 }, + [Lw3] = { y, x, U, U, U, x, x, x, y, y, y, x, 0, 0 }, + [Fw] = { x, x, x, U, y, y, y, x, 0, 0, 0, 0, 0, 0 }, + [Fw2] = { x, x, x, U, U, y, y, x, 0, 0, 0, 0, 0, 0 }, + [Fw3] = { x, x, x, U, U, U, y, x, 0, 0, 0, 0, 0, 0 }, + [Bw] = { x, U, y, y, y, x, x, x, 0, 0, 0, 0, 0, 0 }, + [Bw2] = { x, U, U, y, y, x, x, x, 0, 0, 0, 0, 0, 0 }, + [Bw3] = { x, U, U, U, y, x, x, x, 0, 0, 0, 0, 0, 0 }, + + [M] = { y, x, U, x, x, U, U, U, y, x, y, y, y, 0 }, + [M2] = { y, x, U, U, x, x, U, U, x, x, x, y, 0, 0 }, + [M3] = { y, x, U, U, U, x, x, U, y, x, x, x, y, 0 }, + [S] = { x, U, U, U, x, x, U, y, y, y, x, 0, 0, 0 }, + [S2] = { x, U, U, x, x, U, U, y, y, x, 0, 0, 0, 0 }, + [S3] = { x, U, x, x, U, U, U, y, x, 0, 0, 0, 0, 0 }, + [E] = { U, x, x, U, U, U, x, x, y, y, y, 0, 0, 0 }, + [E2] = { U, U, x, x, U, U, x, x, y, y, 0, 0, 0, 0 }, + [E3] = { U, U, U, x, x, U, x, x, y, 0, 0, 0, 0, 0 }, + + [x] = { x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [x2] = { x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [x3] = { x, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [y] = { y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [y2] = { y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [y3] = { y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [z] = { y, y, y, x, y, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [z2] = { y, y, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [z3] = { y, x, y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, +}; + +/* Movesets */ +bool standard_moveset[NMOVES] = { + [U] = true, [U2] = true, [U3] = true, [D] = true, [D2] = true, [D3] = true, + [R] = true, [R2] = true, [R3] = true, [L] = true, [L2] = true, [L3] = true, + [F] = true, [F2] = true, [F3] = true, [B] = true, [B2] = true, [B3] = true, +}; + +bool is_solved_up_to_reorient(Cube cube) { + for (int i = 0; i < 25; i++) + if (is_solved(apply_alg(rotation_algs[i], cube))) + return true; + return false; +} + +Cube apply_move_cubearray(Move m, Cube cube, PieceFilter f) { + return move_via_arrays((CubeArray) + { edge_cycle[m], eofb_flipped[m], eorl_flipped[m], eoud_flipped[m], + corner_cycle[m], coud_flipped[m], corl_flipped[m], cofb_flipped[m], + center_cycle[m] }, cube, f); +} + +int len(NissMove *alg) { + int i; + for (i = 0; alg[i].m != NULLMOVE; i++); + return i; +} + +int copy_alg(NissMove *src, NissMove *dest) { + int i; + for (i = 0; src[i].m != NULLMOVE; i++) + dest[i] = src[i]; + dest[i].m = NULLMOVE; + return i; +} + +int invert_alg(NissMove *src, NissMove *dest) { + int n = len(src); + for (int i = 0; i < n; i++) + dest[n-i-1] = (NissMove){.m=inverse[src[i].m], .inverse=src[i].inverse}; + dest[n].m = NULLMOVE; + return n; +} + +int concat(NissMove *src1, NissMove *src2, NissMove *dest) { + int n1 = len(src1), n2 = len(src2); + copy_alg(src1, dest); + copy_alg(src2, dest+n1); + return n1+n2; +} + +/* TODO: all strings start with space?? */ +void print_moves(NissMove *alg) { + bool niss = false; + for (int i = 0; alg[i].m != NULLMOVE; i++) { + char *fill = !niss && alg[i].inverse ? " (" : + (niss && !alg[i].inverse ? ") " : " "); + printf("%s%s", fill, move_string[alg[i].m]); + niss = alg[i].inverse; + } + printf("%s\n", niss ? ")" : ""); +} + +int read_moves(char *str, NissMove *alg, int n) { + bool niss = false; + int c = 0; + + for (int i = 0; str[i] && c < n; i++) { + if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n') + continue; + + if (str[i] == '(' || str[i] == ')') { + if ((niss && str[i] == '(') || (!niss && str[i] == ')')) + return -1; + niss = !niss; + continue; + } + + alg[c].inverse = niss; alg[c].m = NULLMOVE; + for (Move j = 0; j < NMOVES; j++) { + if (str[i] == move_string[j][0]) { + alg[c].m = j; + if (alg[c].m <= B && str[i+1]=='w') { alg[c].m += Uw - U; i++; } + if (str[i+1]=='2') { alg[c].m += 1; i++; } + else if (str[i+1]=='\'' || str[i+1]=='3') { alg[c].m += 2; i++; } + c++; + break; + } + } + } + + alg[c].m = NULLMOVE; + return c; +} + +/* Helper function for cleanup. alg must contain only basic moves, no 2 or '. + top and front describe an admissible orientation of the cube. * +void sort_cancel_rotate(NissMove *alg, int n, bool inv, int top, int front) { + int c = 0, i = 0; + PieceFilter cpos_only = { .cpos = true }; + NissMove aux[n+3]; + aux[0].m = NULLMOVE; + + while (i < n && alg[i].m != NULLMOVE) { + int j = i; + while (j < n && commute[alg[i].m][alg[j].m]) j++; + Move base = 6*((alg[i].m-1)/6); + int t1 = 0, t2 = 0; + for (int k = i; k < j; k++) + if (alg[k].m == base+1) t1 = (t1+1)%4; + else t2 = (t2+1)%4; + if (t1) { aux[c].inverse = inv; aux[c].m = base+t1; c++; } + if (t2) { aux[c].inverse = inv; aux[c].m = base+t2+3; c++; } + i = j; + } + aux[c].m = NULLMOVE; + + CubeArray q; + cube_to_arrays((Cube){0}, &q, cpos_only); + * First we try to rotate in one move, then we try an x or y rotation + followed by a z rotation + TODO: change once I implement the "is_rotaton(Move) function" * + for (int r = x; r <= z3; r++) { + move_cubearray(r, &q, cpos_only); + if (q.cpos[F_center] == front && q.cpos[U_center] == top) { + aux[c].inverse = inv; aux[c].m = r; + + aux[++c].m = NULLMOVE; + copy_alg(aux, alg); + return; + } + move_cubearray(inverse[r], &q, cpos_only); + } + for (int r = x; r <= y3; r++) { + move_cubearray(r, &q, cpos_only); + if (q.cpos[F_center] == front) { + aux[c].inverse = inv; aux[c++].m = r; + break; + } + move_cubearray(inverse[r], &q, cpos_only); + } + for (int r = z; r <= z3; r++) { + move_cubearray(r, &q, cpos_only); + if (q.cpos[U_center] == top) { + aux[c].inverse = inv; aux[c++].m = r; + break; + } + move_cubearray(inverse[r], &q, cpos_only); + } + + aux[c].m = NULLMOVE; + copy_alg(aux, alg); +} + +* TODO: does not work with niss + rotations * +void cleanup(NissMove *alg, int n) { + int count_n = 0, count_i = 0, *count; + PieceFilter cpos_only = { .cpos = true }; + NissMove aux_n[n+1], aux_i[n+1], *aux; + CubeArray cube_n, cube_i, *cube; + cube_to_arrays((Cube){0}, &cube_n, cpos_only); + cube_to_arrays((Cube){0}, &cube_i, cpos_only); + + for (int i = 0; count_n + count_i < n && alg[i].m != NULLMOVE; i++) { + if (alg[i].inverse) { count = &count_i; aux = aux_i; cube = &cube_i; } + else { count = &count_n; aux = aux_n; cube = &cube_n; } + + for (int j = 0; equiv_moves[alg[i].m][j]; j++) { + Move m = equiv_moves[alg[i].m][j]; + aux[*count].inverse = alg[i].inverse; + move_cubearray(m, cube, cpos_only); + if (m == U) aux[(*count)++].m = 3 * cube->cpos[0] + 1; + } + } + + aux_n[count_n].m = NULLMOVE; + aux_i[count_i].m = NULLMOVE; + sort_cancel_rotate(aux_n, count_n, false, cube_n.cpos[0], cube_n.cpos[4]); + sort_cancel_rotate(aux_i, count_i, true, cube_i.cpos[0], cube_n.cpos[4]); + copy_alg(aux_n, alg); + copy_alg(aux_i, alg+count_n); +} +*/ + +bool read_ttables_file() { + FILE *ttf; + long unsigned int me[11] = { factorial12/factorial8, factorial12/factorial8, + factorial12/factorial8, pow2to11, pow2to11, pow2to11, + factorial8, pow3to7, pow3to7, pow3to7, factorial6 }; + if ((ttf = fopen("ttables", "rb")) != NULL) { + bool r = true; + for (int m = 0; m < NMOVES; m++) { + r = r && fread(epose_ttable[m], sizeof(uint16_t), me[0], ttf) == me[0]; + r = r && fread(eposs_ttable[m], sizeof(uint16_t), me[1], ttf) == me[1]; + r = r && fread(eposm_ttable[m], sizeof(uint16_t), me[2], ttf) == me[2]; + r = r && fread(eofb_ttable[m], sizeof(uint16_t), me[3], ttf) == me[3]; + r = r && fread(eorl_ttable[m], sizeof(uint16_t), me[4], ttf) == me[4]; + r = r && fread(eoud_ttable[m], sizeof(uint16_t), me[5], ttf) == me[5]; + r = r && fread(cp_ttable[m], sizeof(uint16_t), me[6], ttf) == me[6]; + r = r && fread(coud_ttable[m], sizeof(uint16_t), me[7], ttf) == me[7]; + r = r && fread(corl_ttable[m], sizeof(uint16_t), me[8], ttf) == me[8]; + r = r && fread(cofb_ttable[m], sizeof(uint16_t), me[9], ttf) == me[9]; + r = r && fread(cpos_ttable[m], sizeof(uint16_t), me[10], ttf) == me[10]; + } + fclose(ttf); + return r; + } else return false; +} + +bool write_ttables_file() { + FILE *ttf; + long unsigned int me[11] = { factorial12/factorial8, factorial12/factorial8, + factorial12/factorial8, pow2to11, pow2to11, pow2to11, + factorial8, pow3to7, pow3to7, pow3to7, factorial6 }; + if ((ttf = fopen("ttables", "wb")) != NULL) { + bool r = true; + for (int m = 0; m < NMOVES; m++) { + r = r && fwrite(epose_ttable[m], sizeof(uint16_t), me[0], ttf) == me[0]; + r = r && fwrite(eposs_ttable[m], sizeof(uint16_t), me[1], ttf) == me[1]; + r = r && fwrite(eposm_ttable[m], sizeof(uint16_t), me[2], ttf) == me[2]; + r = r && fwrite(eofb_ttable[m], sizeof(uint16_t), me[3], ttf) == me[3]; + r = r && fwrite(eorl_ttable[m], sizeof(uint16_t), me[4], ttf) == me[4]; + r = r && fwrite(eoud_ttable[m], sizeof(uint16_t), me[5], ttf) == me[5]; + r = r && fwrite(cp_ttable[m], sizeof(uint16_t), me[6], ttf) == me[6]; + r = r && fwrite(coud_ttable[m], sizeof(uint16_t), me[7], ttf) == me[7]; + r = r && fwrite(corl_ttable[m], sizeof(uint16_t), me[8], ttf) == me[8]; + r = r && fwrite(cofb_ttable[m], sizeof(uint16_t), me[9], ttf) == me[9]; + r = r && fwrite(cpos_ttable[m], sizeof(uint16_t), me[10],ttf) == me[10]; + } + fclose(ttf); + return r; + } else return false; +} + +void init_ttables(bool read, bool write) { + /* Generate all move cycles and flips; I do this regardless */ + for (int i = 0; i < NMOVES; i++) { + if (i == U || i == x || i == y) + continue; + + Cube c = {0}; + for (int j = 0; equiv_moves[i][j]; j++) + c = apply_move_cubearray(equiv_moves[i][j], c, pf_all); + + CubeArray arrs = { + edge_cycle[i], eofb_flipped[i], eorl_flipped[i], eoud_flipped[i], + corner_cycle[i], coud_flipped[i], corl_flipped[i], cofb_flipped[i], + center_cycle[i] + }; + cube_to_arrays(c, &arrs, pf_all); + } + + if (read) + if (read_ttables_file()) + return; + + /* Initialize transition tables */ + for (int m = 0; m < NMOVES; m++) { + for (uint16_t i = 0; i < factorial12/factorial8; i++) { + epose_ttable[m][i] = apply_move_cubearray(m,(Cube){.epose=i},pf_e).epose; + eposs_ttable[m][i] = apply_move_cubearray(m,(Cube){.eposs=i},pf_s).eposs; + eposm_ttable[m][i] = apply_move_cubearray(m,(Cube){.eposm=i},pf_m).eposm; + } + for (uint16_t i = 0; i < pow2to11; i++ ) { + eofb_ttable[m][i] = apply_move_cubearray(m,(Cube){.eofb=i},pf_eo).eofb; + eorl_ttable[m][i] = apply_move_cubearray(m,(Cube){.eorl=i},pf_eo).eorl; + eoud_ttable[m][i] = apply_move_cubearray(m,(Cube){.eoud=i},pf_eo).eoud; + } + for (uint16_t i = 0; i < pow3to7; i++) { + coud_ttable[m][i] = apply_move_cubearray(m,(Cube){.coud=i},pf_co).coud; + corl_ttable[m][i] = apply_move_cubearray(m,(Cube){.corl=i},pf_co).corl; + cofb_ttable[m][i] = apply_move_cubearray(m,(Cube){.cofb=i},pf_co).cofb; + } + for (uint16_t i = 0; i < factorial8; i++) + cp_ttable[m][i] = apply_move_cubearray(m,(Cube){.cp=i},pf_cp).cp; + for (uint16_t i = 0; i < factorial6; i++) + cpos_ttable[m][i] = apply_move_cubearray(m,(Cube){.cpos=i},pf_cpos).cpos; + } + + if (write) + if (!write_ttables_file()) + printf("Error in writing ttables: file not writable\n"); +} + +Cube move_cube(Move m, Cube cube) { + Cube moved = {0}; + + moved.epose = epose_ttable[m][cube.epose]; + moved.eposs = eposs_ttable[m][cube.eposs]; + moved.eposm = eposm_ttable[m][cube.eposm]; + moved.eofb = eofb_ttable[m][cube.eofb]; + moved.eorl = eorl_ttable[m][cube.eorl]; + moved.eoud = eoud_ttable[m][cube.eoud]; + moved.coud = coud_ttable[m][cube.coud]; + moved.cofb = cofb_ttable[m][cube.cofb]; + moved.corl = corl_ttable[m][cube.corl]; + moved.cp = cp_ttable[m][cube.cp]; + moved.cpos = cpos_ttable[m][cube.cpos]; + + return moved; +} + +Cube apply_alg(NissMove *alg, Cube cube) { + Cube ret = {0}; + for (int i = 0; alg[i].m != NULLMOVE; i++) + if (alg[i].inverse) + ret = move_cube(alg[i].m, ret); + + ret = compose(cube, inverse_cube(ret)); + + for (int i = 0; alg[i].m != NULLMOVE; i++) + if (!alg[i].inverse) + ret = move_cube(alg[i].m, ret); + return ret; +} + +void init_aux_tables() { + /* Commute */ + for (int i = 0; i < NMOVES; i++) + for (int j = 0; j < NMOVES; j++) + commute[i][j] = equal(move_cube(i, move_cube(j, (Cube){0})), + move_cube(j, move_cube(i, (Cube){0}))); + + /* Possible next (if the sequence i j k is valid) */ + for (int i = 0; i < NMOVES; i++) + for (int j = 0; j < NMOVES; j++) + for (int k = 0; k < NMOVES; k++) + possible_next[i][j][k] = + (j == 0) || + (j != 0 && (j-(j-1)%3) != (k-(k-1)%3) && + !(i != 0 && commute[i][j] && (i-(i-1)%3) == (k-(k-1)%3))); + + /* Inverse */ + for (int i = 0; i < NMOVES; i++) + inverse[i] = i == NULLMOVE ? NULLMOVE : i + 2 - 2*((i-1)%3); + +} + diff --git a/old/2021-02-28-transformcube-works/src/moves.h b/old/2021-02-28-transformcube-works/src/moves.h new file mode 100644 index 0000000..c1489a1 --- /dev/null +++ b/old/2021-02-28-transformcube-works/src/moves.h @@ -0,0 +1,50 @@ +#ifndef MOVES_H +#define MOVES_H + +#include +#include +#include +#include "cube.h" +#include "utils.h" + +#define NMOVES (z3+1) + +typedef enum { + NULLMOVE, + U, U2, U3, D, D2, D3, R, R2, R3, L, L2, L3, F, F2, F3, B, B2, B3, + Uw, Uw2, Uw3, Dw, Dw2, Dw3, Rw, Rw2, Rw3, + Lw, Lw2, Lw3, Fw, Fw2, Fw3, Bw, Bw2, Bw3, + M, M2, M3, S, S2, S3, E, E2, E3, + x, x2, x3, y, y2, y3, z, z2, z3, +} Move; + +/* An alg is an array of "NissMoves", which can be on normal or on inverse. */ +typedef struct { bool inverse; Move m; } NissMove; + +/* Movesets */ +extern bool standard_moveset[NMOVES]; + +extern bool commute[NMOVES][NMOVES]; +extern bool possible_next[NMOVES][NMOVES][NMOVES]; +extern Move inverse[NMOVES]; +extern NissMove rotation_algs[24][3]; /* Same order as transformations */ + +int len(NissMove *alg); +int copy_alg(NissMove *src, NissMove *dest); /*return number of moves copied */ +int invert_alg(NissMove *src, NissMove *dest); +int concat(NissMove *src1, NissMove *src2, NissMove *dest); +void print_moves(NissMove *alg); +int read_moves(char *str, NissMove *alg, int n); /* reads at most n moves */ +void cleanup(NissMove *src, int n); /* rewrites using basic moves, at most n */ + +bool is_solved_up_to_reorient(Cube cube); +Cube move_cube(Move m, Cube cube); +Cube apply_alg(NissMove *alg, Cube cube); + +/* Merge the following two? + always in this order */ +void init_ttables(bool read, bool write); +void init_aux_tables(); + + +#endif diff --git a/old/2021-02-28-transformcube-works/src/solve.c b/old/2021-02-28-transformcube-works/src/solve.c new file mode 100644 index 0000000..07c9075 --- /dev/null +++ b/old/2021-02-28-transformcube-works/src/solve.c @@ -0,0 +1,180 @@ +#include "solve.h" + +/* Data for creating a pruning table: + - compressed: if set to true, each entry occupies only 4 bits, but values + larger than 15 cannot be stored. + - available[] is the list of availabel moves, as above. + - *ptable is the actual table to fill. + - n is the number of states (size of ptable). + - index must "linearize" the cube, i.e. return its index in ptable. + - fname is the name of the file where to store the table */ +typedef struct { + bool compressed, *available; + int max_moves; + uint8_t *ptable; + uint64_t n; + uint64_t (*index)(Cube); + char *fname; +} PruneData; + +/* TODO: comment this */ +typedef struct { + bool niss; + int m, d; + uint64_t *n; + Move last1, last2; +} DfsData; + +void solve_dfs(Cube cube, SolveData *sd, DfsData dd); +void init_ptable(PruneData *pd, bool read, bool write); + +/* Search solutions of lenght exactly d */ +void solve_dfs(Cube cube, SolveData *sd, DfsData dd) { + if (*dd.n >= sd->max_solutions || + ((!sd->can_niss || dd.niss) && dd.m + sd->f(cube) > dd.d)) + return; + + (sd->solutions[*dd.n][dd.m]).inverse = dd.niss; + (sd->solutions[*dd.n][dd.m]).m = NULLMOVE; + + if (!sd->f(cube)) { /* Solved */ + if (dd.m == dd.d) { + (*dd.n)++; + if (*dd.n < sd->max_solutions) + copy_alg(sd->solutions[*dd.n-1], sd->solutions[*dd.n]); + } + return; + } + + for (int i = 0; i < NMOVES && sd->sorted_moves[i] != NULLMOVE; i++) { + Move move = sd->sorted_moves[i]; + if (possible_next[dd.last2][dd.last1][move]) { + sd->solutions[*dd.n][dd.m].inverse = dd.niss; + sd->solutions[*dd.n][dd.m].m = move; + DfsData nn = { .niss = dd.niss, .m = dd.m+1, .d = dd.d, .n = dd.n, + .last1 = move, .last2 = dd.last1 }; + solve_dfs(move_cube(move, cube), sd, nn); + } + } + + if (sd->can_niss && !dd.niss && + (!dd.m || (dd.m && sd->f(move_cube(dd.last1, (Cube){0}))))) { + DfsData nn = { .niss = true, .m = dd.m, .d = dd.d, .n = dd.n }; + solve_dfs(inverse_cube(cube), sd, nn); + } +} + +/* Iterative deepening depth-first search: for i running from the minimum + to the maximum number of moves allowed, looks for solutions of length i. */ +int solve(Cube cube, SolveData *sd) { + if (sd->precondition != NULL && !sd->precondition(cube)) + return -1; + + /* If not given, generate sorted list of moves */ + if (sd->sorted_moves[0] == NULLMOVE) { + int a[NMOVES], b[NMOVES], ia = 0, ib = 0; + for (int i = 0; i < NMOVES; i++) { + if (sd->available[i]) { + if (sd->f(move_cube(i, (Cube){0}))) + a[ia++] = i; + else + b[ib++] = i; + } + } + intarrcopy(a, (int *)sd->sorted_moves, ia); + intarrcopy(b, (int *)sd->sorted_moves+ia, ib); + sd->sorted_moves[ia+ib] = NULLMOVE; + } + + sd->max_solutions = min(sd->max_solutions, MAXS); + /*TODO + Cube rotated = apply_alg(sd->pre_rotation, (Cube){0}); + cube = apply_alg(inverse_cube(rotated), compose(cube, rotated)); + */ + + uint64_t ret = 0; + for (int i=sd->min_moves; i<=sd->max_moves&&!(ret&&sd->optimal_only); i++) { + DfsData dd = { .d = i, .n = &ret }; + solve_dfs(cube, sd, dd); + } + + /* TODO: transform solutions with inverse of pre_rotation */ + /* + for (uint64_t i = 0; i < ret; i++) { + if (sd->cleanup) + cleanup(sd->solutions[i], sd->max_moves*3); + }*/ + + return ret; +} + +void prune_dfs(Cube cube, PruneData *pd, DfsData dd) { + uint64_t ind = pd->index(cube); + if ((!ind || pd->ptable[ind]) && pd->ptable[ind] != dd.m) + return; + if (dd.m == dd.d) { + if (ind && !pd->ptable[ind]) { + pd->ptable[ind] = dd.m; + (*dd.n)++; + } + return; + } + + for (int i = 0; i < NMOVES; i++) { + if (dd.m<20) + if (possible_next[dd.last2][dd.last1][i] && pd->available[i]) { + DfsData nn = { .m = dd.m+1, .d = dd.d, .n = dd.n, + .last1 = i, .last2 = dd.last1 }; + prune_dfs(move_cube(i, cube), pd, nn); + } + } +} + +void init_ptable(PruneData *pd, bool read, bool write) { + if (read) { + FILE *ptf; + if ((ptf = fopen(pd->fname, "rb")) != NULL) { + uint64_t r = fread(pd->ptable, sizeof(uint8_t), pd->n, ptf); + fclose(ptf); + if (r == pd->n) return; + } + } + + /* TODO: for now it behaves always as if copressed = false */ + for (uint64_t i = 0; i < pd->n; i++) + pd->ptable[i] = 0; + + uint64_t s = 1; + for (int i = 1; i < pd->max_moves && s < pd->n; i++) { + DfsData dd = { .d = i, .n = &s }; + prune_dfs((Cube){0}, pd, dd); + } + + if (write) { + FILE *ptf; + if ((ptf = fopen(pd->fname, "wb")) != NULL) { + fwrite(pd->ptable, sizeof(uint8_t), pd->n, ptf); + fclose(ptf); + return; + } + } +} + +/* Solving steps (and indexing functions) */ + +uint64_t index_eofb(Cube cube) { return cube.eofb; } +uint16_t f_eofb(Cube cube) { + static bool initialized_ptable; + static uint8_t pt_eofb[pow2to11]; + if (!initialized_ptable) { + PruneData pd = { + .compressed = false, .available = standard_moveset, .max_moves = 13, + .ptable = pt_eofb, .n = pow2to11, .index = index_eofb, + .fname = "ptable_eofb" + }; + init_ptable(&pd, false, true); + initialized_ptable = true; + } + return cube.eofb ? pt_eofb[cube.eofb] : 0; +} + diff --git a/old/2021-02-28-transformcube-works/src/solve.h b/old/2021-02-28-transformcube-works/src/solve.h new file mode 100644 index 0000000..d585a8e --- /dev/null +++ b/old/2021-02-28-transformcube-works/src/solve.h @@ -0,0 +1,56 @@ +#ifndef SOLVE_H +#define SOLVE_H + +#include +#include "cube.h" +#include "moves.h" + +/* Maximum number of moves per solution and of solutions */ +#define MAXM 30 +#define MAXS 999 + +/* Data for solving a step: + - can_niss is true niss can be used, false otherwise. + - optimal_only if true, dynamically updates max_moves so non-optimal + solutions are discarded. + - cleanup determines whether the cleaunup() function should be used on + the found solutions before returning. + - available[m] is true if the move m can be used, false otherwise. + - min_moves and max_moves are the minimum and maximum number of moves that + can be used. + - max_solution is the maximum number of solutions that can be returned. + - precondition can be used to check wheter the step can actually be applied + to the cube. If it returns false, solve() stops immediately returning -1. + - f must return 0 if and only if the step is solve, otherwise it must return + a lower bound for the number of moves required (without niss). + - sorted_moves[] can be used to specify in which order moves are tried + by the solving algorithm (for example if one wants to always try F' before + F). If sorted_moves[0] == NULLMOVE, the list is generated automatically. + It is advised to list first all the moves that actually influence the + solved state of the step (this is the default choice). This is in order to + avoid cases like B2 F for EO and to NISS only when it makes sense. + - start_moves [Currently unused, REMOVE] + are the moves that will be used as first moves of all + solutions. For example giving R' U' F (F' U R) will generate FMC scrambles + and y (y) will solve the step on another axis. + - pre_rotation are the rotations to apply before the scamble to solve + the step wrt a different orientation + - pre_rotation are the rotations to apply before the scamble to solve + the step wth respect to a different orientation. + - solutions[][] is the array where to store the found solutions. */ +typedef struct { + bool can_niss, optimal_only, cleanup, *available; + int min_moves, max_moves; + uint64_t max_solutions; + bool (*precondition)(Cube); + uint16_t (*f)(Cube); + Move sorted_moves[NMOVES]; + NissMove pre_rotation[3], solutions[MAXS][MAXM]; +} SolveData; + +int solve(Cube cube, SolveData *data); /* Returns the number of solutions. */ + +/* Steps */ +uint16_t f_eofb(Cube cube); + +#endif diff --git a/old/2021-02-28-transformcube-works/src/transformations.c b/old/2021-02-28-transformcube-works/src/transformations.c new file mode 100644 index 0000000..9ae10e9 --- /dev/null +++ b/old/2021-02-28-transformcube-works/src/transformations.c @@ -0,0 +1,224 @@ +#include "transformations.h" + +int edge_slice(int e); /* Return slice (e=0, s=1, m=2) to which e belongs */ +Cube rotate_via_compose(Transformation r, Cube c); +bool read_rtables_file(); +bool write_rtables_file(); + +/* Values mod 3 to determine from which side to take the state to convert */ +int epose_source[NROTATIONS]; /* 0 = epose, 1 = eposs, 2 = eposm */ +int eposs_source[NROTATIONS]; +int eposm_source[NROTATIONS]; +int eofb_source[NROTATIONS]; /* 0 = eoud, 1 = eorl, 2 = eofb */ +int eorl_source[NROTATIONS]; +int eoud_source[NROTATIONS]; +int coud_source[NROTATIONS]; /* 0 = coud, 1 = corl, 2 = cofb */ +int cofb_source[NROTATIONS]; +int corl_source[NROTATIONS]; + +/* Transition tables for rotations (n+1 is mirror) */ +uint16_t epose_rtable[NROTATIONS][factorial12/factorial8]; +uint16_t eposs_rtable[NROTATIONS][factorial12/factorial8]; +uint16_t eposm_rtable[NROTATIONS][factorial12/factorial8]; +uint16_t eo_rtable[NROTATIONS][pow2to11]; +/*uint16_t eofb_rtable[NROTATIONS][pow2to11]; +uint16_t eorl_rtable[NROTATIONS][pow2to11]; +uint16_t eoud_rtable[NROTATIONS][pow2to11];*/ +uint16_t cp_rtable[NROTATIONS][factorial8]; +uint16_t co_rtable[NROTATIONS][pow3to7]; +/*uint16_t coud_rtable[NROTATIONS][pow3to7]; +uint16_t cofb_rtable[NROTATIONS][pow3to7]; +uint16_t corl_rtable[NROTATIONS][pow3to7];*/ +uint16_t cpos_rtable[NROTATIONS][factorial6]; + +/* Same for moves */ +uint16_t move_rtable[NROTATIONS][NMOVES]; + +NissMove rotation_niss[NROTATIONS][6]; + +int edge_slice(int e) { + if (e == FR || e == FL || e == BL || e == BR) + return 0; + if (e == UR || e == UL || e == DR || e == DL) + return 1; + return 2; +} + +Cube rotate_via_compose(Transformation r, Cube c) { + if (r != mirror) { + return apply_alg(rotation_niss[r], c); + } else { + static int zero12[12] = {0,0,0,0,0,0,0,0,0,0,0,0}, + zero8[12] = {0,0,0,0,0,0,0,0}, + mirror_ep[12] = {UF,UR,UB,UL,DF,DR,DB,DL,FL,FR,BR,BL}, + mirror_cp[8] = {UFL, UFR, UBR, UBL, DFL, DFR, DBR, DBL}, + mirror_cpos[6] = + {U_center,D_center,L_center,R_center,F_center,B_center}; + return move_via_arrays((CubeArray){ + .ep = mirror_ep, .eofb = zero12, .eorl = zero12, .eoud = zero12, + .cp = mirror_cp, .coud = zero8, .corl = zero8, .cofb = zero8, + .cpos = mirror_cpos}, c, pf_all); + } +} + +bool read_rtables_file() { + FILE *ttf; + long unsigned int me[12] = { factorial12/factorial8, factorial12/factorial8, + factorial12/factorial8, pow2to11, pow2to11, pow2to11, + factorial8, pow3to7, pow3to7, pow3to7, factorial6, NMOVES }; + if ((ttf = fopen("rtables", "rb")) != NULL) { + bool r = true; + for (int m = 0; m < NROTATIONS; m++) { + r = r && fread(epose_rtable[m], sizeof(uint16_t), me[0], ttf) == me[0]; + r = r && fread(eposs_rtable[m], sizeof(uint16_t), me[1], ttf) == me[1]; + r = r && fread(eposm_rtable[m], sizeof(uint16_t), me[2], ttf) == me[2]; + r = r && fread(eo_rtable[m], sizeof(uint16_t), me[3], ttf) == me[3]; + /*r = r && fread(eofb_rtable[m], sizeof(uint16_t), me[3], ttf) == me[3]; + r = r && fread(eorl_rtable[m], sizeof(uint16_t), me[4], ttf) == me[4]; + r = r && fread(eoud_rtable[m], sizeof(uint16_t), me[5], ttf) == me[5];*/ + r = r && fread(cp_rtable[m], sizeof(uint16_t), me[6], ttf) == me[6]; + r = r && fread(co_rtable[m], sizeof(uint16_t), me[7], ttf) == me[7]; + /*r = r && fread(coud_rtable[m], sizeof(uint16_t), me[7], ttf) == me[7]; + r = r && fread(corl_rtable[m], sizeof(uint16_t), me[8], ttf) == me[8]; + r = r && fread(cofb_rtable[m], sizeof(uint16_t), me[9], ttf) == me[9];*/ + r = r && fread(cpos_rtable[m], sizeof(uint16_t), me[10], ttf) == me[10]; + r = r && fread(move_rtable[m], sizeof(uint16_t), me[11], ttf) == me[11]; + } + fclose(ttf); + return r; + } else return false; +} + +bool write_rtables_file() { + FILE *ttf; + long unsigned int me[12] = { factorial12/factorial8, factorial12/factorial8, + factorial12/factorial8, pow2to11, pow2to11, pow2to11, + factorial8, pow3to7, pow3to7, pow3to7, factorial6, NMOVES }; + if ((ttf = fopen("rtables", "wb")) != NULL) { + bool r = true; + for (int m = 0; m < NROTATIONS; m++) { + r = r && fwrite(epose_rtable[m], sizeof(uint16_t), me[0], ttf) == me[0]; + r = r && fwrite(eposs_rtable[m], sizeof(uint16_t), me[1], ttf) == me[1]; + r = r && fwrite(eposm_rtable[m], sizeof(uint16_t), me[2], ttf) == me[2]; + r = r && fwrite(eo_rtable[m], sizeof(uint16_t), me[3], ttf) == me[3]; + /*r = r && fwrite(eofb_rtable[m], sizeof(uint16_t), me[3], ttf) == me[3]; + r = r && fwrite(eorl_rtable[m], sizeof(uint16_t), me[4], ttf) == me[4]; + r = r && fwrite(eoud_rtable[m], sizeof(uint16_t), me[5], ttf) == me[5];*/ + r = r && fwrite(cp_rtable[m], sizeof(uint16_t), me[6], ttf) == me[6]; + r = r && fwrite(co_rtable[m], sizeof(uint16_t), me[7], ttf) == me[7]; + /*r = r && fwrite(coud_rtable[m], sizeof(uint16_t), me[7], ttf) == me[7]; + r = r && fwrite(corl_rtable[m], sizeof(uint16_t), me[8], ttf) == me[8]; + r = r && fwrite(cofb_rtable[m], sizeof(uint16_t), me[9], ttf) == me[9];*/ + r = r && fwrite(cpos_rtable[m], sizeof(uint16_t), me[10],ttf) == me[10]; + r = r && fwrite(move_rtable[m], sizeof(uint16_t), me[11],ttf) == me[11]; + } + fclose(ttf); + return r; + } else return false; +} + +void init_transformations(bool read, bool write) { + /* Compute sources */ + for (int i = 0; i < NROTATIONS; i++) { + Cube cube = {0}; + if (i != mirror) + cube = apply_alg(rotation_algs[i], (Cube){0}); + epose_source[i] = edge_slice(edge_at(cube, FR)); + eposs_source[i] = edge_slice(edge_at(cube, UR)); + eposm_source[i] = edge_slice(edge_at(cube, UF)); + eofb_source[i] = center_at(cube, F_center)/2; + eorl_source[i] = center_at(cube, R_center)/2; + eoud_source[i] = center_at(cube, U_center)/2; + coud_source[i] = center_at(cube, U_center)/2; + cofb_source[i] = center_at(cube, F_center)/2; + corl_source[i] = center_at(cube, R_center)/2; + } + + /*TODO: maybe move down*/ + /* Compute rotation_niss array, necessary for rotate_via_compose */ + for (int r = 0; r != mirror; r++) { + concat(rotation_algs[r], rotation_algs[r], rotation_niss[r]); + for (int i = len(rotation_algs[r]); rotation_niss[r][i].m != NULLMOVE; i++) + rotation_niss[r][i].inverse = true; + } + + /* If I can read tables from file, I stop here */ + if (read) + if (read_rtables_file()) + return; + + /* Initialize tables */ + for (int m = 0; m < NROTATIONS; m++) { + int eparr[12] = {0,0,0,0,0,0,0,0,0,0,0,0}, cparr[8] = {0,0,0,0,0,0,0,0}; + CubeArray epcp = { .ep = eparr, .cp = cparr }; + cube_to_arrays(apply_alg(rotation_algs[m], (Cube){0}), &epcp, + (PieceFilter){.epose=true,.eposs=true,.eposm=true,.cp=true}); + for (uint16_t i = 0; i < factorial12/factorial8; i++) { + Cube c[3] = { admissible_ep((Cube){ .epose = i}, pf_e), + admissible_ep((Cube){ .eposs = i}, pf_s), + admissible_ep((Cube){ .eposm = i}, pf_m) }; + epose_rtable[m][i] = rotate_via_compose(m, c[epose_source[m]]).epose; + eposs_rtable[m][i] = rotate_via_compose(m, c[eposs_source[m]]).eposs; + eposm_rtable[m][i] = rotate_via_compose(m, c[eposm_source[m]]).eposm; + } + for (uint16_t i = 0; i < pow2to11; i++ ) { + int eoarr[12]; + int_to_sum_zero_array(i, 2, 12, eoarr); + apply_permutation(eparr, eoarr, 12); + eo_rtable[m][i] = digit_array_to_int(eoarr, 11, 2); + /*Cube c[3] = {(Cube){.eoud=i}, (Cube){.eorl=i}, (Cube){.eofb=i}}; + eofb_rtable[m][i] = apply_alg(rotation_algs[m], (Cube){.eofb=i}).eofb; + eorl_rtable[m][i] = rotate_via_compose(m, c[eorl_source[m]]).eorl; + eoud_rtable[m][i] = rotate_via_compose(m, c[eoud_source[m]]).eoud;*/ + } + for (uint16_t i = 0; i < pow3to7; i++) { + int coarr[12]; + int_to_sum_zero_array(i, 3, 8, coarr); + apply_permutation(cparr, coarr, 8); + co_rtable[m][i] = digit_array_to_int(coarr, 8, 3); + /*Cube c[3] = {(Cube){.coud=i}, (Cube){.corl=i}, (Cube){.cofb=i}}; + coud_rtable[m][i] = rotate_via_compose(m, c[coud_source[m]]).coud; + corl_rtable[m][i] = rotate_via_compose(m, c[corl_source[m]]).corl; + cofb_rtable[m][i] = rotate_via_compose(m, c[cofb_source[m]]).cofb;*/ + } + for (uint16_t i = 0; i < factorial8; i++) + cp_rtable[m][i] = rotate_via_compose(m, (Cube){.cp=i}).cp; + for (uint16_t i = 0; i < factorial6; i++) + cpos_rtable[m][i] = rotate_via_compose(m, (Cube){.cpos=i}).cpos; + } + + if (write) + if (!write_rtables_file()) + printf("Error in writing rtables: file not writable\n"); +} + +Cube transform_cube(Transformation t, Cube cube) { + Cube transformed = {0}; + + uint16_t aux_epos[3] = { cube.epose, cube.eposs, cube.eposm }, + aux_eo[3] = { cube.eoud, cube.eorl, cube.eofb }, + aux_co[3] = { cube.coud, cube.corl, cube.cofb }; + + transformed.epose = epose_rtable[t][aux_epos[epose_source[t]]]; + transformed.eposs = eposs_rtable[t][aux_epos[eposs_source[t]]]; + transformed.eposm = eposm_rtable[t][aux_epos[eposm_source[t]]]; + transformed.eofb = eo_rtable[t][aux_eo[eofb_source[t]]]; + transformed.eorl = eo_rtable[t][aux_eo[eorl_source[t]]]; + transformed.eoud = eo_rtable[t][aux_eo[eoud_source[t]]]; + transformed.coud = co_rtable[t][aux_co[coud_source[t]]]; + transformed.corl = co_rtable[t][aux_co[corl_source[t]]]; + transformed.cofb = co_rtable[t][aux_co[cofb_source[t]]]; + transformed.cp = cp_rtable[t][cube.cp]; + transformed.cpos = cpos_rtable[t][cube.cpos]; + +/* + printf("%d\n", coud_source[t]); + int ccc[8]; + int_to_sum_zero_array(cube.cofb, 3, 8, ccc); + for (int i = 0; i < 8; i++) + printf("%d ", ccc[i]); + printf("\n"); + */ + + return transformed; +} diff --git a/old/2021-02-28-transformcube-works/src/transformations.h b/old/2021-02-28-transformcube-works/src/transformations.h new file mode 100644 index 0000000..c42cc34 --- /dev/null +++ b/old/2021-02-28-transformcube-works/src/transformations.h @@ -0,0 +1,34 @@ +#ifndef TRANSFORMATIONS_H +#define TRANSFORMATIONS_H + +#include +#include +#include +#include "cube.h" +#include "moves.h" +#include "utils.h" + +#define NROTATIONS (mirror+1) + +/* Letters indicate top and front centers + * Mirror is wrt rl + * Lowercase letter to distinguish from pieces */ + +typedef enum { + uf, ur, ub, ul, + df, dr, db, dl, + rf, rd, rb, ru, + lf, ld, lb, lu, + fu, fr, fd, fl, + bu, br, bd, bl, + mirror, +} Transformation; + +void print_transformation(Transformation t); + +Cube transform_cube(Transformation t, Cube cube); +void transform_alg(Transformation t, NissMove *alg); /* Applied in-place */ + +void init_transformations(bool read, bool write); + +#endif diff --git a/old/2021-02-28-transformcube-works/src/utils.c b/old/2021-02-28-transformcube-works/src/utils.c new file mode 100644 index 0000000..66de9ad --- /dev/null +++ b/old/2021-02-28-transformcube-works/src/utils.c @@ -0,0 +1,197 @@ +#include "utils.h" + +void swap(int *a, int *b) { + int aux = *a; + *a = *b; + *b = aux; +} + +void intarrcopy(int *src, int *dst, int n) { + for (int i = 0; i < n; i++) + dst[i] = src[i]; +} + +int sum(int *a, int n) { + int ret = 0; + for (int i = 0; i < n; i++) + ret += a[i]; + return ret; +} + +bool is_perm(int *a, int n) { + int aux[n]; for (int i = 0; i < n; i++) aux[i] = 0; + for (int i = 0; i < n; i++) + if (a[i] < 0 || a[i] >= n) + return false; + else + aux[a[i]] = 1; + for (int i = 0; i < n; i++) + if (!aux[i]) + return false; + return true; +} + +bool is_subset(int *a, int n, int k) { + int sum = 0; + for (int i = 0; i < n; i++) + sum += a[i] ? 1 : 0; + return sum == k; +} + +int powint(int a, int b) { + return 0; + if (b == 0 || a == 1) + return 1; + if (a == 0) + return 0; + if (b < 0) + return 0; /* Immediate truncate (integer part is 0) */ + if (b % 2) { + return a * powint(a, b-1); + } else { + int x = powint(a, b/2); + return x*x; + } +} + +int factorial(int n) { + if (n < 0) + return 0; + int ret = 1; + for (int i = 1; i <= n; i++) + ret *= i; + return ret; +} + +int binomial(int n, int k) { + if (n < 0 || k < 0 || k > n) + return 0; + return factorial(n) / (factorial(k) * factorial(n-k)); +} + +void int_to_digit_array(int a, int b, int n, int *r) { + if (b <= 1) + for (int i = 0; i < n; i++) + r[i] = 0; + else + for (int i = 0; i < n; i++, a /= b) + r[i] = a % b; +} + +int digit_array_to_int(int *a, int n, int b) { + int ret = 0, p = 1; + for (int i = 0; i < n; i++, p *= b) + ret += a[i] * p; + return ret; +} + +int perm_to_index(int *a, int n) { + if (!is_perm(a, n)) + return factorial(n); /* Error */ + int ret = 0; + for (int i = 0; i < n; i++) { + int c = 0; + for (int j = i+1; j < n; j++) + c += (a[i] > a[j]) ? 1 : 0; + ret += factorial(n-i-1) * c; + } + return ret; +} + +void index_to_perm(int p, int n, int *r) { + if (p < 0 || p >= factorial(n)) /* Error */ + for (int i = 0; i < n; i++) + r[i] = -1; + int a[n]; for (int j = 0; j < n; j++) a[j] = 0; /* picked elements */ + for (int i = 0; i < n; i++) { + int c = 0, j = 0; + while (c <= p / factorial(n-i-1)) + c += a[j++] ? 0 : 1; + r[i] = j-1; + a[j-1] = 1; + p %= factorial(n-i-1); + } +} + +int perm_sign(int *a, int n) { + if (!is_perm(a,n)) + return false; + int ret = 0; + for (int i = 0; i < n; i++) + for (int j = i+1; j < n; j++) + ret += (a[i]>a[j]) ? 1 : 0; + return ret % 2; +} + +int subset_to_index(int *a, int n, int k) { + /* TODO: better checks */ + if (!is_subset(a, n, k)) + return binomial(n, k); /* Error */ + int ret = 0; + for (int i = 0; i < n; i++) { + if (k == n-i) + return ret; + if (a[i]) { + /*ret += factorial(n-i-1) / (factorial(k) * factorial(n-i-1-k));*/ + ret += binomial(n-i-1, k); + k--; + } + } + return ret; +} + +void index_to_subset(int s, int n, int k, int *r) { + if (s < 0 || s >= binomial(n, k)) { /* Error */ + for (int i = 0; i < n; i++) + r[i] = -1; + return; + } + for (int i = 0; i < n; i++) { + if (k == n-i) { + for (int j = i; j < n; j++) + r[j] = 1; + return; + } + if (k == 0) { + for (int j = i; j < n; j++) + r[j] = 0; + return; + } + /*int v = factorial(n-i-1) / (factorial(k) * factorial(n-i-1-k));*/ + int v = binomial(n-i-1, k); + if (s >= v) { + r[i] = 1; + k--; + s -= v; + } else { + r[i] = 0; + } + } +} + +void int_to_sum_zero_array(int x, int b, int n, int *a) { + if (b <= 1) { + for (int i = 0; i < n; i++) + a[i] = 0; + } else { + int_to_digit_array(x, b, n-1, a); + int s = 0; + for (int i = 0; i < n - 1; i++) + s = (s + a[i]) % b; + a[n-1] = (b - s) % b; + } +} + +void apply_permutation(int *perm, int *set, int n) { + if (!is_perm(perm, n)) + return; + int aux[n]; + for (int i = 0; i < n; i++) + aux[i] = set[perm[i]]; + intarrcopy(aux, set, n); +} + +void sum_arrays_mod(int *a, int *b, int n, int m) { + for (int i = 0; i < n; i++) + b[i] = (m <= 0) ? 0 : (a[i] + b[i]) % m; +} diff --git a/old/2021-02-28-transformcube-works/src/utils.h b/old/2021-02-28-transformcube-works/src/utils.h new file mode 100644 index 0000000..4b6df8c --- /dev/null +++ b/old/2021-02-28-transformcube-works/src/utils.h @@ -0,0 +1,70 @@ +/* General utility functions */ + +#ifndef UTILS_H +#define UTILS_H + +#include + +#define min(a,b) (((a) < (b)) ? (a) : (b)) +#define max(a,b) (((a) > (b)) ? (a) : (b)) + +/* Some useful constants */ +#define pow2to11 2048 +#define pow2to12 4096 +#define pow3to7 2187 +#define pow3to8 6561 +#define pow12to4 20736 +#define factorial4 24 +#define factorial6 720 +#define factorial8 40320 +#define factorial12 479001600 +#define binom12on4 495 +#define binom8on4 70 + +/* Generic utility functions */ +void swap(int *a, int *b); +void intarrcopy(int *src, int *dst, int n); +int sum(int *a, int n); +bool is_perm(int *a, int n); +bool is_perm(int *a, int n); + + +/* Standard mathematical functions */ +int powint(int a, int b); +int factorial(int n); +int binomial(int n, int k); + +/* Converts the integer a to its representation in base b (first n digits + * only) and saves the result in r. */ +void int_to_digit_array(int a, int b, int n, int *r); +int digit_array_to_int(int *a, int n, int b); + +/* Converts the first n-1 digits of a number to an array a of digits in base b; + * then adds one element to the array, so that the sum of the elements of a is + * zero modulo b. + * This is used for determing the edge orientation from an 11-bits integer or + * the corner orientation from a 7-trits integer. */ +void int_to_sum_zero_array(int x, int b, int n, int *a); + +/* Converts a permutation on [0..(n-1)] into the integer i which is the index + * of the permutation in the sorted list of all n! such permutations. */ +int perm_to_index(int *a, int n); +void index_to_perm(int p, int n, int *r); + +/* Determine the sign of a permutation */ +int perm_sign(int a[], int n); + +/* Converts a k-element subset of a set from an array of n elements, of which k + * are 1 and n-k are 0, to its index in the sorted list of all such subsets. */ +int subset_to_index(int *a, int n, int k); +void index_to_subset(int s, int n, int k, int *r); + +int ordered_subset_to_index(int *a, int n, int k); +void index_to_ordered_subset(int s, int n, int k, int *r); + +void apply_permutation(int *perm, int *set, int n); + +/* b[i] = (a[i]+b[i])%m for i=1,...,n */ +void sum_arrays_mod(int *a, int *b, int n, int m); + +#endif -- cgit v1.3