From 4fb67201414169a2687f41c4056b2e284b4938cb Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 11 Nov 2021 22:05:00 +0100 Subject: Removed old files --- old/2021-02-06/cube.c | 664 ------------------------------------------------- old/2021-02-06/cube.h | 60 ----- old/2021-02-06/main.c | 46 ---- old/2021-02-06/solve.c | 177 ------------- old/2021-02-06/solve.h | 55 ---- old/2021-02-06/utils.c | 197 --------------- old/2021-02-06/utils.h | 70 ------ 7 files changed, 1269 deletions(-) delete mode 100644 old/2021-02-06/cube.c delete mode 100644 old/2021-02-06/cube.h delete mode 100644 old/2021-02-06/main.c delete mode 100644 old/2021-02-06/solve.c delete mode 100644 old/2021-02-06/solve.h delete mode 100644 old/2021-02-06/utils.c delete mode 100644 old/2021-02-06/utils.h (limited to 'old/2021-02-06') diff --git a/old/2021-02-06/cube.c b/old/2021-02-06/cube.c deleted file mode 100644 index 9185281..0000000 --- a/old/2021-02-06/cube.c +++ /dev/null @@ -1,664 +0,0 @@ -#include "cube.h" - -typedef struct { - int ep[12], eofb[12], eorl[12], eoud[12], - cp[8], coud[8], corl[8], cofb[8], cpos[6]; -} CubeArray; - -typedef struct { - bool epose, eposs, eposm, eofb, eorl, eoud, cp, coud, cofb, corl, cpos; -} PieceFilter; - -PieceFilter fAll = {true,true,true,true,true,true,true,true,true,true,true}; -PieceFilter cpos_only = { .cpos = true }; - -void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f); -Cube arrays_to_cube(CubeArray arr, PieceFilter f); -void move_cubearray(Move m, CubeArray *arr, PieceFilter f); -Cube move_via_array(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]; - -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" }; -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]=2,[UFL]=1,[DBL]=1,[DFL]=2}, - [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, -}; - -int epe_solved[] = {FR, FL, BL, BR}; -int eps_solved[] = {UL, UR, DL, DR}; -int epm_solved[] = {UF, UB, DF, DB}; - -Cube blank_cube() { - Cube c = {0}; - return c; -} - -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; -} - -void move_cubearray(Move m, CubeArray *arr, PieceFilter f) { - if (f.epose || f.eposs || f.eposm) - apply_permutation(edge_cycle[m], arr->ep, 12); - if (f.eofb) { - apply_permutation(edge_cycle[m], arr->eofb, 12); - sum_arrays_mod(eofb_flipped[m], arr->eofb, 12, 2); - } - if (f.eofb) { - apply_permutation(edge_cycle[m], arr->eorl, 12); - sum_arrays_mod(eorl_flipped[m], arr->eorl, 12, 2); - } - if (f.eofb) { - apply_permutation(edge_cycle[m], arr->eoud, 12); - sum_arrays_mod(eoud_flipped[m], arr->eoud, 12, 2); - } - if (f.cp) - apply_permutation(corner_cycle[m], arr->cp, 8); - if (f.coud) { - apply_permutation(corner_cycle[m], arr->coud, 8); - sum_arrays_mod(coud_flipped[m], arr->coud, 8, 3); - } - if (f.corl) { - apply_permutation(corner_cycle[m], arr->corl, 8); - sum_arrays_mod(corl_flipped[m], arr->corl, 8, 3); - } - if (f.cofb) { - apply_permutation(corner_cycle[m], arr->cofb, 8); - sum_arrays_mod(cofb_flipped[m], arr->cofb, 8, 3); - } - if (f.cpos) - apply_permutation(center_cycle[m], arr->cpos, 6); -} - -Cube move_via_array(Move m, Cube cube, PieceFilter f) { - CubeArray arr = {0}; - cube_to_arrays(cube, &arr, f); - move_cubearray(m, &arr, f); - return arrays_to_cube(arr, f); -} - -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; -} - -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 solvable(Cube cube) { - /* Since we memorize orientation truncating the last digit, we only need to - * check that the permutations have the correct sign. */ - CubeArray arr = {0}; - cube_to_arrays(cube, &arr, fAll); - return (perm_sign(arr.ep,12) ^ perm_sign(arr.cpos,6)) == perm_sign(arr.cp,8); -} - -bool is_solved(Cube cube, bool reorient) { - if (!reorient || !cube.cpos) - return !cube.eofb && !cube.coud && !cube.cp && - !cube.epose && !cube.eposs && !cube.eposm; - - bool ret = false; - for (int i = x; i <= z3; i++) { - ret = ret || is_solved(move_cube(i, cube), false); - for (int j = x; j <= z3; j++) - ret = ret || is_solved(move_cube(i, move_cube(j, cube)), false); - } - return ret; -} - -void print_cube(Cube cube) { - CubeArray arr = {0}; - cube_to_arrays(cube, &arr, fAll); - - for (int i = 0; i < 12; i++) printf(" %s ", edge_string[arr.ep[i]]); - printf("\n"); - for (int i = 0; i < 12; i++) printf(" %c ", arr.eofb[i] + '0'); - printf("\n"); - for (int i = 0; i < 8; i++) printf("%s ", corner_string[arr.cp[i]]); - printf("\n"); - for (int i = 0; i < 8; i++) printf(" %c ", arr.coud[i] + '0'); - printf("\n"); - for (int i = 0; i < 6; i++) printf(" %s ", center_string[arr.cpos[i]]); - printf("\n"); -} - -/* 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; - 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(blank_cube(), &q, cpos_only); - /* First we try to rotate in one move, then we try an x or y rotation - followed by a z rotation */ - 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); -} - -void cleanup(NissMove *alg, int n) { - int count_n = 0, count_i = 0, *count; - NissMove aux_n[n+1], aux_i[n+1], *aux; - CubeArray cube_n, cube_i, *cube; - cube_to_arrays(blank_cube(), &cube_n, cpos_only); - cube_to_arrays(blank_cube(), &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); -} - -Cube inverse_cube(Cube cube) { - CubeArray arr = {0}, inv = {0}; - cube_to_arrays(cube, &arr, fAll); - - for (int i = 0; i < 12; i++) { - inv.ep[arr.ep[i]] = i; - inv.eofb[arr.ep[i]] = arr.eofb[i]; - inv.eorl[arr.ep[i]] = arr.eorl[i]; - inv.eoud[arr.ep[i]] = arr.eoud[i]; - } - for (int i = 0; i < 8; i++) { - inv.cp[arr.cp[i]] = i; - inv.coud[arr.cp[i]] = arr.coud[i]; - inv.corl[arr.cp[i]] = arr.corl[i]; - inv.cofb[arr.cp[i]] = arr.cofb[i]; - } - for (int i = 0; i < 6; i++) - inv.cpos[arr.cpos[i]] = i; - - return arrays_to_cube(inv, fAll); -} - -bool read_ttables_file() { - FILE *ttf; - if ((ttf = fopen("ttables", "rb")) != NULL) { - for (int m = 0; m < NMOVES; m++) { - fread(epose_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf); - fread(eposs_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf); - fread(eposm_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf); - fread(eofb_ttable[m], sizeof(uint16_t), pow2to11, ttf); - fread(eorl_ttable[m], sizeof(uint16_t), pow2to11, ttf); - fread(eoud_ttable[m], sizeof(uint16_t), pow2to11, ttf); - fread(cp_ttable[m], sizeof(uint16_t), factorial8, ttf); - fread(coud_ttable[m], sizeof(uint16_t), pow3to7, ttf); - fread(corl_ttable[m], sizeof(uint16_t), pow3to7, ttf); - fread(cofb_ttable[m], sizeof(uint16_t), pow3to7, ttf); - fread(cpos_ttable[m], sizeof(uint16_t), factorial6, ttf); - } - fclose(ttf); - return true; - } else return false; -} - -bool write_ttables_file() { - FILE *ttf; - if ((ttf = fopen("ttables", "wb")) != NULL) { - for (int m = 0; m < NMOVES; m++) { - fwrite(epose_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf); - fwrite(eposs_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf); - fwrite(eposm_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf); - fwrite(eofb_ttable[m], sizeof(uint16_t), pow2to11, ttf); - fwrite(eorl_ttable[m], sizeof(uint16_t), pow2to11, ttf); - fwrite(eoud_ttable[m], sizeof(uint16_t), pow2to11, ttf); - fwrite(cp_ttable[m], sizeof(uint16_t), factorial8, ttf); - fwrite(coud_ttable[m], sizeof(uint16_t), pow3to7, ttf); - fwrite(corl_ttable[m], sizeof(uint16_t), pow3to7, ttf); - fwrite(cofb_ttable[m], sizeof(uint16_t), pow3to7, ttf); - fwrite(cpos_ttable[m], sizeof(uint16_t), factorial6, ttf); - } - fclose(ttf); - return true; - } 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; - - CubeArray arr = {0}; - cube_to_arrays(blank_cube(), &arr, fAll); - for (int j = 0; equiv_moves[i][j]; j++) - move_cubearray(equiv_moves[i][j], &arr, fAll); - - intarrcopy(arr.ep, edge_cycle[i], 12); - intarrcopy(arr.eofb, eofb_flipped[i], 12); - intarrcopy(arr.eorl, eorl_flipped[i], 12); - intarrcopy(arr.eoud, eoud_flipped[i], 12); - intarrcopy(arr.cp, corner_cycle[i], 8); - intarrcopy(arr.coud, coud_flipped[i], 8); - intarrcopy(arr.corl, corl_flipped[i], 8); - intarrcopy(arr.cofb, cofb_flipped[i], 8); - intarrcopy(arr.cpos, center_cycle[i], 6); - } - - if (read) - if (read_ttables_file()) - return; - - /* Initialize transition tables */ - Cube c = {0}; - PieceFilter fe = {.epose=true}, fs = {.eposs=true}, fm = {.eposm=true}; - PieceFilter feo = { .eofb = true, .eorl = true, .eoud = true }; - PieceFilter fcp = { .cp = true }; - PieceFilter fco = { .cofb = true, .corl = true, .coud = true }; - PieceFilter fcc = { .cpos = true }; - for (int m = 0; m < NMOVES; m++) { - for (uint16_t i = 0; i < factorial12/factorial8; i++) { - c.epose = i; epose_ttable[m][i] = move_via_array(m, c, fe).epose; - c.eposs = i; eposs_ttable[m][i] = move_via_array(m, c, fs).eposs; - c.eposm = i; eposm_ttable[m][i] = move_via_array(m, c, fm).eposm; - } - for (uint16_t i = 0; i < pow2to11; i++ ) { - c.eofb = i; eofb_ttable[m][i] = move_via_array(m, c, feo).eofb; - c.eorl = i; eorl_ttable[m][i] = move_via_array(m, c, feo).eorl; - c.eoud = i; eoud_ttable[m][i] = move_via_array(m, c, feo).eoud; - } - for (uint16_t i = 0; i < factorial8; i++) { - c.cp = i; cp_ttable[m][i] = move_via_array(m, c, fcp).cp; - } - for (uint16_t i = 0; i < pow3to7; i++) { - c.coud = i; coud_ttable[m][i] = move_via_array(m, c, fco).coud; - c.corl = i; corl_ttable[m][i] = move_via_array(m, c, fco).corl; - c.cofb = i; cofb_ttable[m][i] = move_via_array(m, c, fco).cofb; - } - for (uint16_t i = 0; i < factorial6; i++) { - c.cpos = i; cpos_ttable[m][i] = move_via_array(m, c, fcc).cpos; - } - } - - if (write) write_ttables_file(); -} - -Cube move_cube(Move m, Cube cube) { - Cube moved = cube; - - 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 compose(Cube c2, Cube c1) { - /* This is basically the same as the move_cubearray function above */ - CubeArray arr2 = {0}, arr1 = {0}; - cube_to_arrays(c2, &arr2, fAll); - cube_to_arrays(c1, &arr1, fAll); - - apply_permutation(arr2.ep, arr1.ep, 12); - apply_permutation(arr2.ep, arr1.eofb, 12); - apply_permutation(arr2.ep, arr1.eorl, 12); - apply_permutation(arr2.ep, arr1.eoud, 12); - sum_arrays_mod(arr2.eofb, arr1.eofb, 12, 2); - sum_arrays_mod(arr2.eorl, arr1.eorl, 12, 2); - sum_arrays_mod(arr2.eoud, arr1.eoud, 12, 2); - apply_permutation(arr2.cp, arr1.cp, 8); - apply_permutation(arr2.cp, arr1.coud, 8); - apply_permutation(arr2.cp, arr1.corl, 8); - apply_permutation(arr2.cp, arr1.cofb, 8); - sum_arrays_mod(arr2.coud, arr1.coud, 8, 3); - sum_arrays_mod(arr2.corl, arr1.corl, 8, 3); - sum_arrays_mod(arr2.cofb, arr1.cofb, 8, 3); - apply_permutation(arr2.cpos, arr1.cpos, 6); - - return arrays_to_cube(arr1, fAll); -} - -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, blank_cube())), - move_cube(j, move_cube(i, blank_cube()))); - - /* 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 == 0 ? 0 : i + 2 - 2*((i-1)%3); -} - diff --git a/old/2021-02-06/cube.h b/old/2021-02-06/cube.h deleted file mode 100644 index bc4f14b..0000000 --- a/old/2021-02-06/cube.h +++ /dev/null @@ -1,60 +0,0 @@ -#ifndef CUBE_H -#define CUBE_H - -#include -#include -#include -#include "utils.h" - -#define NMOVES (z3+1) - -/* Constants for moves and pieces */ -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; -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; - -/* An alg is an array of "NissMoves", which can be on normal or on inverse. */ -typedef struct { bool inverse; Move m; } NissMove; - -/* Representation of the cube */ -typedef struct { - uint16_t eofb, eorl, eoud, coud, cofb, corl, - epose, eposs, eposm, cp, cpos; -} Cube; - -extern bool commute[NMOVES][NMOVES]; -extern bool possible_next[NMOVES][NMOVES][NMOVES]; -extern Move inverse[NMOVES]; -/* Movesets */ -extern bool standard_moveset[NMOVES]; - -int copy_alg(NissMove *src, NissMove *dest); /*return number of moves copied */ - -bool equal(Cube c1, Cube c2); -bool is_solvable(Cube cube); -/* reorient=true allows solved in wrong orientation */ -bool is_solved(Cube cube, bool reorient); -void print_cube(Cube cube); -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 */ -Cube blank_cube(); -Cube inverse_cube(Cube cube); -Cube move_cube(Move m, Cube cube); -Cube compose(Cube c2, Cube c1); /* Use c2 as an alg */ -Cube apply_alg(NissMove *alg, Cube cube); - -void init_ttables(bool read, bool write); -void init_aux_tables(); - -void init_dbg(); - -#endif diff --git a/old/2021-02-06/main.c b/old/2021-02-06/main.c deleted file mode 100644 index c7be782..0000000 --- a/old/2021-02-06/main.c +++ /dev/null @@ -1,46 +0,0 @@ -#include -#include "cube.h" -#include "solve.h" - -int main() { - init_ttables(true, true); - init_aux_tables(); - - - char moves[100] = "MR U' B2 Bw F z xE2 M' x Dw' y Fw2 y2"; - NissMove alg[100]; - read_moves(moves, alg, 100); - Cube cube = apply_alg(alg, blank_cube()); - - /*f_eofb(cube);*/ - - -/* NissMove sol[MAXS][MAXM];*/ - 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,blank_cube()), c2 = apply_alg(b,blank_cube()); - print_cube(compose(c2,c1)); - print_cube(compose(c1,c2)); - /*print_cube(compose(c2,blank_cube()));*/ - - 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-06/solve.c b/old/2021-02-06/solve.c deleted file mode 100644 index f6274e9..0000000 --- a/old/2021-02-06/solve.c +++ /dev/null @@ -1,177 +0,0 @@ -#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, blank_cube()))))) { - 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, blank_cube()))) - 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); - Cube rotated = apply_alg(sd->pre_rotation, blank_cube()); - 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); - } - - for (uint64_t i = 0; i < ret; i++) { - /* TODO: transform solutions with inverse of pre_rotation */ - 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) { - fread(pd->ptable, sizeof(uint8_t), pd->n, ptf); - fclose(ptf); - 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(blank_cube(), 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-06/solve.h b/old/2021-02-06/solve.h deleted file mode 100644 index 6479e14..0000000 --- a/old/2021-02-06/solve.h +++ /dev/null @@ -1,55 +0,0 @@ -#ifndef SOLVE_H -#define SOLVE_H - -#include -#include "cube.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-06/utils.c b/old/2021-02-06/utils.c deleted file mode 100644 index 66de9ad..0000000 --- a/old/2021-02-06/utils.c +++ /dev/null @@ -1,197 +0,0 @@ -#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-06/utils.h b/old/2021-02-06/utils.h deleted file mode 100644 index 4b6df8c..0000000 --- a/old/2021-02-06/utils.h +++ /dev/null @@ -1,70 +0,0 @@ -/* 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