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-06-23-uint16t/cube.c | 2762 ----------------------------------------- 1 file changed, 2762 deletions(-) delete mode 100644 old/2021-06-23-uint16t/cube.c (limited to 'old/2021-06-23-uint16t/cube.c') diff --git a/old/2021-06-23-uint16t/cube.c b/old/2021-06-23-uint16t/cube.c deleted file mode 100644 index 0381ba0..0000000 --- a/old/2021-06-23-uint16t/cube.c +++ /dev/null @@ -1,2762 +0,0 @@ -#include "cube.h" - -/* Local functions **********************************************************/ - -static Cube admissible_ep(Cube cube, PieceFilter f); -static bool allowed_next(Move move, DfsData *dd); -static void append_alg(AlgList *l, Alg *alg); -static void append_move(Alg *alg, Move m, bool inverse); -static Cube apply_alg_generic(Alg *alg, Cube c, PieceFilter f, bool a); -static void apply_permutation(int *perm, int *set, int n); -static Cube apply_move_cubearray(Move m, Cube cube, PieceFilter f); -static uint16_t array_ep_to_epos(int *ep, int *eps_solved); -static Cube arrays_to_cube(CubeArray *arr, PieceFilter f); -static int binomial(int n, int k); -static Cube compose_filtered(Cube c2, Cube c1, PieceFilter f); -static void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f); -static void dfs(Cube c, Step s, SolveOptions *opts, DfsData *dd); -static void dfs_branch(Cube c, Step s, SolveOptions *opts, DfsData *dd); -static bool dfs_check_solved(SolveOptions *opts, DfsData *dd); -static void dfs_niss(Cube c, Step s, SolveOptions *opts, DfsData *dd); -static bool dfs_stop(Cube c, Step s, SolveOptions *opts, DfsData *dd); -static int digit_array_to_int(int *a, int n, int b); -static int edge_slice(Edge e); /* E=0, S=1, M=2 */ -static int epos_dependent(int pos1, int pos2); -static uint16_t epos_from_arrays(int *epos, int *ep); -static void epos_to_partial_ep(uint16_t epos, int *ep, int *ss); -static int factorial(int n); -static void free_alglistnode(AlgListNode *aln); -static void free_cubearray(CubeArray *arr, PieceFilter f); -static void genptable_dfs(Cube c, PruneData *pd, DfsData *dd); -static void genptable_dfs_branch(Cube c, PruneData *pd, DfsData *dd); -static void index_to_perm(int p, int n, int *r); -static void index_to_subset(int s, int n, int k, int *r); -static void int_to_digit_array(int a, int b, int n, int *r); -static void int_to_sum_zero_array(int x, int b, int n, int *a); -static int invert_digits(int a, int b, int n); -static bool is_perm(int *a, int n); -static bool is_subset(int *a, int n, int k); -static Cube move_via_arrays(CubeArray *arr, Cube c, PieceFilter pf); -static void movelist_to_position(Move *movelist, int *position); -static void moveset_to_list(Moveset ms, Checker f, Move *r); -static AlgList * new_alglist(); -static CubeArray * new_cubearray(Cube cube, PieceFilter f); -static int perm_sign(int *a, int n); -static int perm_to_index(int *a, int n); -static int powint(int a, int b); -static bool ptable_has_reached(PruneData *pd, uint64_t ind); -static void ptable_set_reached(PruneData *pd, uint64_t ind); -static void ptable_update(PruneData *pd, uint64_t ind, int m); -static void realloc_alg(Alg *alg, int n); -static bool read_algset_file(AlgSet *as); -static bool read_mtables_file(); -static bool read_ptable_file(PruneData *pd); -static bool read_ttables_file(); -static Cube rotate_via_compose(Trans r, Cube c, PieceFilter f); -static int subset_to_index(int *a, int n, int k); -static void sum_arrays_mod(int *src, int *dst, int n, int m); -static void swap(int *a, int *b); -static bool write_algset_file(AlgSet *as); -static bool write_mtables_file(); -static bool write_ptable_file(PruneData *pd); -static bool write_ttables_file(); - -static void init_auxtables(); -static void init_environment(); -static void init_moves(); -static void init_moves_aux(); -static void init_strings(); -static void init_trans(); -static void init_trans_aux(); - -/* All sorts of useful costants and tables **********************************/ - -static char * tabledir; - -static PieceFilter pf_all; -static PieceFilter pf_4val; -static PieceFilter pf_epcp; -static PieceFilter pf_cpos; -static PieceFilter pf_cp; -static PieceFilter pf_ep; -static PieceFilter pf_e; -static PieceFilter pf_s; -static PieceFilter pf_m; -static PieceFilter pf_eo; -static PieceFilter pf_co; - -static int epe_solved[4]; -static int eps_solved[4]; -static int epm_solved[4]; - -static char move_string[NMOVES][7]; -static char edge_string[12][7]; -static char corner_string[8][7]; -static char center_string[6][7]; - -static bool commute[NMOVES][NMOVES]; -static bool possible_next[NMOVES][NMOVES][NMOVES]; -static Move inverse_move_aux[NMOVES]; -static Trans inverse_trans_aux[NTRANS]; -static int epos_dependent_aux[BINOM12ON4][BINOM12ON4]; -static Center what_center_at_aux[FACTORIAL6][6]; -static Corner what_corner_at_aux[FACTORIAL8][8]; -static int what_orientation_last_corner_aux[POW3TO7]; -static int what_orientation_last_edge_aux[POW2TO11]; -static Center where_is_center_aux[FACTORIAL6][6]; -static Corner where_is_corner_aux[FACTORIAL8][8]; -static Edge where_is_edge_aux[3][FACTORIAL12/FACTORIAL8][12]; - -static uint16_t epose_ttable[NTRANS][FACTORIAL12/FACTORIAL8]; -static uint16_t eposs_ttable[NTRANS][FACTORIAL12/FACTORIAL8]; -static uint16_t eposm_ttable[NTRANS][FACTORIAL12/FACTORIAL8]; -static uint16_t eo_ttable[NTRANS][POW2TO11]; -static uint16_t cp_ttable[NTRANS][FACTORIAL8]; -static uint16_t co_ttable[NTRANS][POW3TO7]; -static uint16_t cpos_ttable[NTRANS][FACTORIAL6]; -static Move moves_ttable[NTRANS][NMOVES]; - -static uint16_t epose_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; -static uint16_t eposs_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; -static uint16_t eposm_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; -static uint16_t eofb_mtable[NMOVES][POW2TO11]; -static uint16_t eorl_mtable[NMOVES][POW2TO11]; -static uint16_t eoud_mtable[NMOVES][POW2TO11]; -static uint16_t cp_mtable[NMOVES][FACTORIAL8]; -static uint16_t coud_mtable[NMOVES][POW3TO7]; -static uint16_t cofb_mtable[NMOVES][POW3TO7]; -static uint16_t corl_mtable[NMOVES][POW3TO7]; -static uint16_t cpos_mtable[NMOVES][FACTORIAL6]; - -static uint64_t me[12]; - -static int edge_cycle[NMOVES][12]; -static int corner_cycle[NMOVES][8]; -static int center_cycle[NMOVES][6]; -static int eofb_flipped[NMOVES][12]; -static int eorl_flipped[NMOVES][12]; -static int eoud_flipped[NMOVES][12]; -static int coud_flipped[NMOVES][8]; -static int corl_flipped[NMOVES][8]; -static int cofb_flipped[NMOVES][8]; -static Alg * equiv_alg[NMOVES]; - -static int epose_source[NTRANS]; /* 0=epose, 1=eposs, 2=eposm */ -static int eposs_source[NTRANS]; -static int eposm_source[NTRANS]; -static int eofb_source[NTRANS]; /* 0=eoud, 1=eorl, 2=eofb */ -static int eorl_source[NTRANS]; -static int eoud_source[NTRANS]; -static int coud_source[NTRANS]; /* 0=coud, 1=corl, 2=cofb */ -static int cofb_source[NTRANS]; -static int corl_source[NTRANS]; -static int ep_mirror[12]; -static int cp_mirror[8]; -static int cpos_mirror[6]; -static Alg * trans_algs[NROTATIONS]; - - -/* Local functions implementation ********************************************/ - -static Cube -admissible_ep(Cube cube, PieceFilter f) -{ - CubeArray *arr = new_cubearray(cube, f); - Cube ret; - bool used[12] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; - int i, j; - - for (i = 0; i < 12; i++) - if (arr->ep[i] != -1) - used[arr->ep[i]] = true; - - for (i = 0, j = 0; i < 12; i++) { - for ( ; j < 11 && used[j]; j++); - if (arr->ep[i] == -1) - arr->ep[i] = j++; - } - - ret = arrays_to_cube(arr, pf_ep); - free_cubearray(arr, f); - - return ret; -} - -static bool -allowed_next(Move move, DfsData *dd) -{ - if (!possible_next[dd->last2][dd->last1][move]) - return false; - - if (commute[dd->last1][move]) - return dd->move_position[dd->last1] < dd->move_position[move]; - - return true; -} - -static void -append_alg(AlgList *l, Alg *alg) -{ - AlgListNode *node = malloc(sizeof(AlgListNode)); - int i; - - node->alg = new_alg(""); - for (i = 0; i < alg->len; i++) - append_move(node->alg, alg->move[i], alg->inv[i]); - node->next = NULL; - - if (++l->len == 1) - l->first = node; - else - l->last->next = node; - l->last = node; -} - -static void -append_move(Alg *alg, Move m, bool inverse) -{ - if (alg->len == alg->allocated) - realloc_alg(alg, 2*alg->len); - - alg->move[alg->len] = m; - alg->inv [alg->len] = inverse; - alg->len++; -} - -static Cube -apply_alg_generic(Alg *alg, Cube c, PieceFilter f, bool a) -{ - Cube ret = {0}; - int i; - - for (i = 0; i < alg->len; i++) - if (alg->inv[i]) - ret = a ? apply_move(alg->move[i], ret) : - apply_move_cubearray(alg->move[i], ret, f); - - ret = compose_filtered(c, inverse_cube(ret), f); - - for (i = 0; i < alg->len; i++) - if (!alg->inv[i]) - ret = a ? apply_move(alg->move[i], ret) : - apply_move_cubearray(alg->move[i], ret, f); - - return ret; -} - -static void -apply_permutation(int *perm, int *set, int n) -{ - int *aux = malloc(n * sizeof(int)); - int i; - - if (!is_perm(perm, n)) - return; - - for (i = 0; i < n; i++) - aux[i] = set[perm[i]]; - - memcpy(set, aux, n * sizeof(int)); - free(aux); -} - -static Cube -apply_move_cubearray(Move m, Cube cube, PieceFilter f) -{ - CubeArray m_arr = { - 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] - }; - - return move_via_arrays(&m_arr, cube, f); -} - -static uint16_t -array_ep_to_epos(int *ep, int *ss) -{ - int epos[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; - int eps[4]; - int i, j, is; - - for (i = 0, is = 0; i < 12; i++) { - for (j = 0; j < 4; j++) { - if (ep[i] == ss[j]) { - eps[is++] = j; - epos[i] = 1; - } - } - } - - for (i = 0; i < 4; i++) - swap(&epos[ss[i]], &epos[i+8]); - - return epos_from_arrays(epos, eps); -} - -static Cube -arrays_to_cube(CubeArray *arr, PieceFilter f) -{ - Cube ret = {0}; - - if (f.epose) - ret.epose = array_ep_to_epos(arr->ep, epe_solved); - if (f.eposs) - ret.eposs = array_ep_to_epos(arr->ep, eps_solved); - if (f.eposm) - ret.eposm = array_ep_to_epos(arr->ep, epm_solved); - 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; -} - -static int -binomial(int n, int k) -{ - if (n < 0 || k < 0 || k > n) - return 0; - - return factorial(n) / (factorial(k) * factorial(n-k)); -} - -static Cube -compose_filtered(Cube c2, Cube c1, PieceFilter f) -{ - CubeArray *arr = new_cubearray(c2, f); - Cube ret; - - ret = move_via_arrays(arr, c1, f); - free_cubearray(arr, f); - - return ret; -} - -static void -cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f) -{ - int i; - - if (f.epose || f.eposs || f.eposm) - for (i = 0; i < 12; i++) - arr->ep[i] = -1; - - if (f.epose) - epos_to_partial_ep(cube.epose, arr->ep, epe_solved); - if (f.eposs) - epos_to_partial_ep(cube.eposs, arr->ep, eps_solved); - if (f.eposm) - epos_to_partial_ep(cube.eposm, arr->ep, epm_solved); - 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); -} - -static void -dfs(Cube c, Step s, SolveOptions *opts, DfsData *dd) -{ - if (dfs_stop(c, s, opts, dd)) - return; - - if (dfs_check_solved(opts, dd)) - return; - - dfs_branch(c, s, opts, dd); - - if (opts->can_niss && !dd->niss) - dfs_niss(c, s, opts, dd); -} - -static void -dfs_branch(Cube c, Step s, SolveOptions *opts, DfsData *dd) -{ - Move m, l1 = dd->last1, l2 = dd->last2, *moves = dd->sorted_moves; - - int i, maxnsol = opts->max_solutions; - - for (i = 0; (m=moves[i]) != NULLMOVE && dd->sols->len < maxnsol; i++) { - if (allowed_next(m, dd)) { - dd->last2 = dd->last1; - dd->last1 = m; - append_move(dd->current_alg, m, dd->niss); - - dfs(apply_move(m, c), s, opts, dd); - - dd->current_alg->len--; - dd->last2 = l2; - dd->last1 = l1; - } - } -} - -static bool -dfs_check_solved(SolveOptions *opts, DfsData *dd) -{ - if (dd->lb != 0) - return false; - - if (dd->current_alg->len == dd->d) { - append_alg(dd->sols, dd->current_alg); - - if (opts->feedback) - print_alg(dd->current_alg, false); - } - - return true; -} - -static void -dfs_niss(Cube c, Step s, SolveOptions *opts, DfsData *dd) -{ - Move l1 = dd->last1, l2 = dd->last2; - - if (dd->current_alg->len == 0 || - (s.check(apply_move(inverse_move(l1), (Cube){0}), 1))) { - dd->niss = true; - dd->last1 = NULLMOVE; - dd->last2 = NULLMOVE; - - dfs(inverse_cube(c), s, opts, dd); - - dd->last1 = l1; - dd->last2 = l2; - dd->niss = false; - } -} - -static bool -dfs_stop(Cube c, Step s, SolveOptions *opts, DfsData *dd) -{ - if (dd->sols->len >= opts->max_solutions) - return true; - - dd->lb = s.check(c, dd->d - dd->current_alg->len); - if (opts->can_niss && !dd->niss) - dd->lb = MIN(1, dd->lb); - - if (dd->current_alg->len + dd->lb > dd->d) - return true; - - return false; -} - -static int -digit_array_to_int(int *a, int n, int b) -{ - int i, ret = 0, p = 1; - - for (i = 0; i < n; i++, p *= b) - ret += a[i] * p; - - return ret; -} - -static int -edge_slice(Edge e) { - if (e < 0 || e > 11) - return -1; - - if (e == FR || e == FL || e == BL || e == BR) - return 0; - if (e == UR || e == UL || e == DR || e == DL) - return 1; - - return 2; -} - -static int -epos_dependent(int poss, int pose) -{ - int ep[12] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}; - int ep8[8] = {0, 0, 0, 0, 0, 0, 0, 0}; - int i, j; - - epos_to_partial_ep(poss*FACTORIAL4, ep, eps_solved); - epos_to_partial_ep(pose*FACTORIAL4, ep, epe_solved); - - for (i = 0, j = 0; i < 12; i++) - if (edge_slice(ep[i]) != 0) - ep8[j++] = (edge_slice(ep[i]) == 1) ? 1 : 0; - - swap(&ep8[1], &ep8[4]); - swap(&ep8[3], &ep8[6]); - - return subset_to_index(ep8, 8, 4); -} - -static uint16_t -epos_from_arrays(int *epos, int *ep) -{ - return FACTORIAL4 * subset_to_index(epos,12,4) + perm_to_index(ep,4); -} - -static void -epos_to_partial_ep(uint16_t epos, int *ep, int *ss) -{ - int i, is, eposs[12], eps[4]; - - index_to_perm(epos % FACTORIAL4, 4, eps); - index_to_subset(epos / FACTORIAL4, 12, 4, eposs); - - for (i = 0; i < 4; i++) - swap(&eposs[ss[i]], &eposs[i+8]); - - for (i = 0, is = 0; i < 12; i++) - if (eposs[i]) - ep[i] = ss[eps[is++]]; -} - -static int -factorial(int n) -{ - int i, ret = 1; - - if (n < 0) - return 0; - - for (i = 1; i <= n; i++) - ret *= i; - - return ret; -} - -void -free_alg(Alg *alg) -{ - free(alg->move); - free(alg->inv); - free(alg); -} - -void -free_alglist(AlgList *l) -{ - AlgListNode *aux, *i = l->first; - - while (i != NULL) { - aux = i->next; - free_alglistnode(i); - i = aux; - } - free(l); -} - -void -free_alglistnode(AlgListNode *aln) -{ - free_alg(aln->alg); - free(aln); -} - -static void -free_cubearray(CubeArray *arr, PieceFilter f) -{ - if (f.epose || f.eposs || f.eposm) - free(arr->ep); - if (f.eofb) - free(arr->eofb); - if (f.eorl) - free(arr->eorl); - if (f.eoud) - free(arr->eoud); - if (f.cp) - free(arr->cp); - if (f.coud) - free(arr->coud); - if (f.corl) - free(arr->corl); - if (f.cofb) - free(arr->cofb); - if (f.cpos) - free(arr->cpos); - - free(arr); -} - -static void -genptable_dfs(Cube c, PruneData *pd, DfsData *dd) -{ - uint64_t ind = pd->index(c); - int oldval = ptableval(pd, ind); - - if (oldval < dd->m || ptable_has_reached(pd, ind) || pd->n == pd->size) - return; - - ptable_set_reached(pd, ind); - - if (dd->m == dd->d) { - if (dd->m < oldval) - ptable_update(pd, ind, dd->m); - return; - } - - genptable_dfs_branch(c, pd, dd); -} - -static void -genptable_dfs_branch(Cube c, PruneData *pd, DfsData *dd) -{ - Move i, move, l1 = dd->last1, l2 = dd->last2; - - dd->m++; - - for (i = 0; dd->sorted_moves[i] != NULLMOVE; i++) { - move = dd->sorted_moves[i]; - if (allowed_next(move, dd)) { - dd->last2 = dd->last1; - dd->last1 = move; - - genptable_dfs(apply_move(move, c), pd, dd); - - dd->last2 = l2; - dd->last1 = l1; - } - } - - dd->m--; -} - -static void -index_to_perm(int p, int n, int *r) -{ - int *a = malloc(n * sizeof(int)); - int i, j, c; - - for (i = 0; i < n; i++) - a[i] = 0; - - if (p < 0 || p >= factorial(n)) - for (i = 0; i < n; i++) - r[i] = -1; - - for (i = 0; i < n; i++) { - 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); - } - - free(a); -} - -static void -index_to_subset(int s, int n, int k, int *r) -{ - int i, j, v; - - if (s < 0 || s >= binomial(n, k)) { - for (i = 0; i < n; i++) - r[i] = -1; - return; - } - - for (i = 0; i < n; i++) { - if (k == n-i) { - for (j = i; j < n; j++) - r[j] = 1; - return; - } - - if (k == 0) { - for (j = i; j < n; j++) - r[j] = 0; - return; - } - - v = binomial(n-i-1, k); - if (s >= v) { - r[i] = 1; - k--; - s -= v; - } else { - r[i] = 0; - } - } -} - -static void -int_to_digit_array(int a, int b, int n, int *r) -{ - int i; - - if (b <= 1) - for (i = 0; i < n; i++) - r[i] = 0; - else - for (i = 0; i < n; i++, a /= b) - r[i] = a % b; -} - -static void -int_to_sum_zero_array(int x, int b, int n, int *a) -{ - int i, s = 0; - - if (b <= 1) { - for (i = 0; i < n; i++) - a[i] = 0; - } else { - int_to_digit_array(x, b, n-1, a); - for (i = 0; i < n - 1; i++) - s = (s + a[i]) % b; - a[n-1] = (b - s) % b; - } -} - -static int -invert_digits(int a, int b, int n) -{ - int i, ret, *r = malloc(n * sizeof(int)); - - int_to_digit_array(a, b, n, r); - for (i = 0; i < n; i++) - r[i] = (b-r[i]) % b; - - ret = digit_array_to_int(r, n, b); - free(r); - return ret; -} - -static bool -is_perm(int *a, int n) -{ - int *aux = malloc(n * sizeof(int)); - int i; - - for (i = 0; i < n; i++) - if (a[i] < 0 || a[i] >= n) - return false; - else - aux[a[i]] = 1; - - for (i = 0; i < n; i++) - if (!aux[i]) - return false; - - free(aux); - - return true; -} - -static bool -is_subset(int *a, int n, int k) -{ - int i, sum = 0; - - for (i = 0; i < n; i++) - sum += a[i] ? 1 : 0; - - return sum == k; -} - -static Cube -move_via_arrays(CubeArray *arr, Cube c, PieceFilter f) -{ - CubeArray *arrc = new_cubearray(c, f); - Cube ret; - - if (f.epose || f.eposs || f.eposm) - apply_permutation(arr->ep, arrc->ep, 12); - - if (f.eofb) { - apply_permutation(arr->ep, arrc->eofb, 12); - sum_arrays_mod(arr->eofb, arrc->eofb, 12, 2); - } - - if (f.eorl) { - apply_permutation(arr->ep, arrc->eorl, 12); - sum_arrays_mod(arr->eorl, arrc->eorl, 12, 2); - } - - if (f.eoud) { - apply_permutation(arr->ep, arrc->eoud, 12); - sum_arrays_mod(arr->eoud, arrc->eoud, 12, 2); - } - - if (f.cp) - apply_permutation(arr->cp, arrc->cp, 8); - - if (f.coud) { - apply_permutation(arr->cp, arrc->coud, 8); - sum_arrays_mod(arr->coud, arrc->coud, 8, 3); - } - - if (f.corl) { - apply_permutation(arr->cp, arrc->corl, 8); - sum_arrays_mod(arr->corl, arrc->corl, 8, 3); - } - - if (f.cofb) { - apply_permutation(arr->cp, arrc->cofb, 8); - sum_arrays_mod(arr->cofb, arrc->cofb, 8, 3); - } - - if (f.cpos) - apply_permutation(arr->cpos, arrc->cpos, 6); - - ret = arrays_to_cube(arrc, f); - free_cubearray(arrc, f); - - return ret; -} - -static void -movelist_to_position(Move *movelist, int *position) -{ - Move m; - - for (m = 0; m < NMOVES && movelist[m] != NULLMOVE; m++) - position[movelist[m]] = m; -} - -static void -moveset_to_list(Moveset ms, Checker f, Move *r) -{ - Cube c; - int b[NMOVES]; - int na = 0, nb = 0; - Move i; - - if (ms == NULL) { - fprintf(stderr, "Error: no moveset given\n"); - return; - } - - for (i = U; i < NMOVES; i++) { - if (ms(i)) { - c = apply_move(i, (Cube){0}); - if (f != NULL && f(c, 1)) - r[na++] = i; - else - b[nb++] = i; - } - } - - memcpy(r + na, b, nb * sizeof(Move)); - r[na+nb] = NULLMOVE; -} - -static AlgList * -new_alglist() -{ - AlgList *ret = malloc(sizeof(AlgList)); - - ret->len = 0; - ret->first = NULL; - ret->last = NULL; - - return ret; -} - -static CubeArray * -new_cubearray(Cube cube, PieceFilter f) -{ - CubeArray *arr = malloc(sizeof(CubeArray)); - - if (f.epose || f.eposs || f.eposm) - arr->ep = malloc(12 * sizeof(int)); - if (f.eofb) - arr->eofb = malloc(12 * sizeof(int)); - if (f.eorl) - arr->eorl = malloc(12 * sizeof(int)); - if (f.eoud) - arr->eoud = malloc(12 * sizeof(int)); - if (f.cp) - arr->cp = malloc(8 * sizeof(int)); - if (f.coud) - arr->coud = malloc(8 * sizeof(int)); - if (f.corl) - arr->corl = malloc(8 * sizeof(int)); - if (f.cofb) - arr->cofb = malloc(8 * sizeof(int)); - if (f.cpos) - arr->cpos = malloc(6 * sizeof(int)); - - cube_to_arrays(cube, arr, f); - - return arr; -} - -static int -perm_sign(int *a, int n) -{ - int i, j, ret = 0; - - if (!is_perm(a,n)) - return -1; - - for (i = 0; i < n; i++) - for (j = i+1; j < n; j++) - ret += (a[i] > a[j]) ? 1 : 0; - - return ret % 2; -} - -static int -perm_to_index(int *a, int n) -{ - int i, j, c, ret = 0; - - if (!is_perm(a, n)) - return -1; - - for (i = 0; i < n; i++) { - c = 0; - for (j = i+1; j < n; j++) - c += (a[i] > a[j]) ? 1 : 0; - ret += factorial(n-i-1) * c; - } - - return ret; -} - -static int -powint(int a, int b) -{ - if (b < 0) - return 0; - if (b == 0) - return 1; - - if (b % 2) - return a * powint(a, b-1); - else - return powint(a*a, b/2); -} - -static bool -ptable_has_reached(PruneData *pd, uint64_t ind) -{ - return ind % 2 ? pd->reached[ind/2] / 16 : pd->reached[ind/2] % 16; -} - -static void -ptable_set_reached(PruneData *pd, uint64_t ind) -{ - uint8_t oldval2 = pd->reached[ind/2]; - int other = ind % 2 ? oldval2 % 16 : oldval2 / 16; - - pd->reached[ind/2] = ind % 2 ? 16 + other : 16*other + 1; -} - -static void -ptable_update(PruneData *pd, uint64_t ind, int n) -{ - uint8_t oldval2 = pd->ptable[ind/2]; - int other = ind % 2 ? oldval2 % 16 : oldval2 / 16; - - pd->ptable[ind/2] = ind % 2 ? 16*n + other : 16*other + n; - pd->n++; -} - -static void -realloc_alg(Alg *alg, int n) -{ - if (alg == NULL) { - fprintf(stderr, "Error: trying to reallocate NULL alg.\n"); - return; - } - - if (n < alg->len) { - fprintf(stderr, "Error: alg too long for reallocation "); - fprintf(stderr, "(%d vs %d)\n", alg->len, n); - return; - } - - if (n > 1000000) { - fprintf(stderr, "Warning: very long alg,"); - fprintf(stderr, "something might go wrong.\n"); - } - - alg->move = realloc(alg->move, n * sizeof(int)); - alg->inv = realloc(alg->inv, n * sizeof(int)); - alg->allocated = n; -} - -static bool -read_algset_file(AlgSet *as) -{ - return false; -} - -static bool -read_mtables_file() -{ - FILE *f; - char fname[strlen(tabledir)+20]; - int m, b = sizeof(uint16_t); - bool r = true; - - strcpy(fname, tabledir); - strcat(fname, "/mtables"); - - if ((f = fopen(fname, "rb")) == NULL) - return false; - - for (m = 0; m < NMOVES; m++) { - r = r && fread(epose_mtable[m], b, me[0], f) == me[0]; - r = r && fread(eposs_mtable[m], b, me[1], f) == me[1]; - r = r && fread(eposm_mtable[m], b, me[2], f) == me[2]; - r = r && fread(eofb_mtable[m], b, me[3], f) == me[3]; - r = r && fread(eorl_mtable[m], b, me[4], f) == me[4]; - r = r && fread(eoud_mtable[m], b, me[5], f) == me[5]; - r = r && fread(cp_mtable[m], b, me[6], f) == me[6]; - r = r && fread(coud_mtable[m], b, me[7], f) == me[7]; - r = r && fread(corl_mtable[m], b, me[8], f) == me[8]; - r = r && fread(cofb_mtable[m], b, me[9], f) == me[9]; - r = r && fread(cpos_mtable[m], b, me[10], f) == me[10]; - } - - fclose(f); - return r; -} - -static bool -read_ptable_file(PruneData *pd) -{ - FILE *f; - char fname[strlen(tabledir)+100]; - uint64_t r; - - strcpy(fname, tabledir); - strcat(fname, "/"); - strcat(fname, pd->filename); - - if ((f = fopen(fname, "rb")) == NULL) - return false; - - r = fread(pd->ptable, sizeof(uint8_t), ptablesize(pd), f); - fclose(f); - - return r == ptablesize(pd); -} - -static bool -read_ttables_file() -{ - FILE *f; - char fname[strlen(tabledir)+20]; - int b = sizeof(uint16_t); - bool r = true; - Move m; - - strcpy(fname, tabledir); - strcat(fname, "/"); - strcat(fname, "ttables"); - - if ((f = fopen(fname, "rb")) == NULL) - return false; - - for (m = 0; m < NTRANS; m++) { - r = r && fread(epose_ttable[m], b, me[0], f) == me[0]; - r = r && fread(eposs_ttable[m], b, me[1], f) == me[1]; - r = r && fread(eposm_ttable[m], b, me[2], f) == me[2]; - r = r && fread(eo_ttable[m], b, me[3], f) == me[3]; - r = r && fread(cp_ttable[m], b, me[6], f) == me[6]; - r = r && fread(co_ttable[m], b, me[7], f) == me[7]; - r = r && fread(cpos_ttable[m], b, me[10], f) == me[10]; - r = r && fread(moves_ttable[m], b, me[11], f) == me[11]; - } - - fclose(f); - return r; -} - -static Cube -rotate_via_compose(Trans r, Cube c, PieceFilter f) -{ - Alg *inv; - static int zero12[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; - static int zero8[8] = { 0, 0, 0, 0, 0, 0, 0, 0 }; - static CubeArray ma = { - .ep = ep_mirror, - .eofb = zero12, - .eorl = zero12, - .eoud = zero12, - .cp = cp_mirror, - .coud = zero8, - .corl = zero8, - .cofb = zero8, - .cpos = cpos_mirror - }; - - Cube ret; - - if (r != mirror) { - ret = apply_alg_generic(trans_algs[r], c, f, true); - inv = on_inverse(trans_algs[r]); - ret = apply_alg_generic(inv, ret, f, true); - free_alg(inv); - } else { - ret = move_via_arrays(&ma, (Cube){0}, f); - ret = compose_filtered(c, ret, f); - ret = move_via_arrays(&ma, ret, f); - } - - return ret; -} - -static int -subset_to_index(int *a, int n, int k) -{ - int i, ret = 0; - - if (!is_subset(a, n, k)) - return binomial(n, k); - - for (i = 0; i < n; i++) { - if (k == n-i) - return ret; - if (a[i]) { - ret += binomial(n-i-1, k); - k--; - } - } - - return ret; -} - -static void -sum_arrays_mod(int *src, int *dst, int n, int m) -{ - int i; - - for (i = 0; i < n; i++) - dst[i] = (m <= 0) ? 0 : (src[i] + dst[i]) % m; -} - -static void -swap(int *a, int *b) -{ - int aux; - - aux = *a; - *a = *b; - *b = aux; -} - -static bool -write_algset_file(AlgSet *as) -{ - return false; -} - -static bool -write_mtables_file() -{ - FILE *f; - char fname[strlen(tabledir)+20]; - int m, b = sizeof(uint16_t); - bool r = true; - - strcpy(fname, tabledir); - strcat(fname, "/mtables"); - - if ((f = fopen(fname, "wb")) == NULL) - return false; - - for (m = 0; m < NMOVES; m++) { - r = r && fwrite(epose_mtable[m], b, me[0], f) == me[0]; - r = r && fwrite(eposs_mtable[m], b, me[1], f) == me[1]; - r = r && fwrite(eposm_mtable[m], b, me[2], f) == me[2]; - r = r && fwrite(eofb_mtable[m], b, me[3], f) == me[3]; - r = r && fwrite(eorl_mtable[m], b, me[4], f) == me[4]; - r = r && fwrite(eoud_mtable[m], b, me[5], f) == me[5]; - r = r && fwrite(cp_mtable[m], b, me[6], f) == me[6]; - r = r && fwrite(coud_mtable[m], b, me[7], f) == me[7]; - r = r && fwrite(corl_mtable[m], b, me[8], f) == me[8]; - r = r && fwrite(cofb_mtable[m], b, me[9], f) == me[9]; - r = r && fwrite(cpos_mtable[m], b, me[10], f) == me[10]; - } - - fclose(f); - return r; -} - -static bool -write_ptable_file(PruneData *pd) -{ - FILE *f; - char fname[strlen(tabledir)+100]; - uint64_t written; - - strcpy(fname, tabledir); - strcat(fname, "/"); - strcat(fname, pd->filename); - - if ((f = fopen(fname, "wb")) == NULL) - return false; - - written = fwrite(pd->ptable, sizeof(uint8_t), ptablesize(pd), f); - fclose(f); - - return written == ptablesize(pd); -} - -static bool -write_ttables_file() -{ - FILE *f; - char fname[strlen(tabledir)+20]; - bool r = true; - int b = sizeof(uint16_t); - Move m; - - strcpy(fname, tabledir); - strcat(fname, "/ttables"); - - if ((f = fopen(fname, "wb")) == NULL) - return false; - - for (m = 0; m < NTRANS; m++) { - r = r && fwrite(epose_ttable[m], b, me[0], f) == me[0]; - r = r && fwrite(eposs_ttable[m], b, me[1], f) == me[1]; - r = r && fwrite(eposm_ttable[m], b, me[2], f) == me[2]; - r = r && fwrite(eo_ttable[m], b, me[3], f) == me[3]; - r = r && fwrite(cp_ttable[m], b, me[6], f) == me[6]; - r = r && fwrite(co_ttable[m], b, me[7], f) == me[7]; - r = r && fwrite(cpos_ttable[m], b, me[10], f) == me[10]; - r = r && fwrite(moves_ttable[m], b, me[11], f) == me[11]; - } - - fclose(f); - return r; -} - -/* Init functions implementation *********************************************/ - -static void -init_auxtables() -{ - Cube c1, c2; - CubeArray *arr; - uint64_t ui, uj; - int i, j, k, auxarr[12]; - bool cij, p1, p2; - - for (ui = 0; ui < FACTORIAL6; ui++) { - arr = new_cubearray((Cube){.cpos = ui}, pf_cpos); - for (i = 0; i < 6; i++) { - what_center_at_aux[ui][i] = arr->cpos[i]; - where_is_center_aux[ui][arr->cpos[i]] = i; - } - free_cubearray(arr, pf_cpos); - } - - for (ui = 0; ui < FACTORIAL8; ui++) { - arr = new_cubearray((Cube){.cp = ui}, pf_cp); - for (i = 0; i < 8; i++) { - what_corner_at_aux[ui][i] = arr->cp[i]; - where_is_corner_aux[ui][arr->cp[i]] = i; - } - free_cubearray(arr, pf_cp); - } - - for (ui = 0; ui < FACTORIAL12/FACTORIAL8; ui++) { - arr = new_cubearray((Cube){.epose = ui}, pf_e); - for (i = 0; i < 12; i++) - if (edge_slice(arr->ep[i]) == 0) - where_is_edge_aux[0][ui][arr->ep[i]] = i; - free_cubearray(arr, pf_e); - - arr = new_cubearray((Cube){.eposs = ui}, pf_s); - for (i = 0; i < 12; i++) - if (edge_slice(arr->ep[i]) == 1) - where_is_edge_aux[1][ui][arr->ep[i]] = i; - free_cubearray(arr, pf_s); - - arr = new_cubearray((Cube){.eposm = ui}, pf_m); - for (i = 0; i < 12; i++) - if (edge_slice(arr->ep[i]) == 2) - where_is_edge_aux[2][ui][arr->ep[i]] = i; - free_cubearray(arr, pf_m); - } - - for (ui = 0; ui < POW3TO7; ui++) { - int_to_sum_zero_array(ui, 3, 8, auxarr); - what_orientation_last_corner_aux[ui] = auxarr[7]; - } - - for (ui = 0; ui < POW2TO11; ui++) { - int_to_sum_zero_array(ui, 2, 12, auxarr); - what_orientation_last_edge_aux[ui] = auxarr[11]; - } - - for (ui = 0; ui < BINOM12ON4; ui++) - for (uj = 0; uj < BINOM12ON4; uj++) - epos_dependent_aux[ui][uj] = epos_dependent(ui, uj); - - for (i = 0; i < NMOVES; i++) { - for (j = 0; j < NMOVES; j++) { - c1 = apply_move(i, apply_move(j, (Cube){0})); - c2 = apply_move(j, apply_move(i, (Cube){0})); - commute[i][j] = equal(c1, c2) && i && j; - } - } - - for (i = 0; i < NMOVES; i++) { - for (j = 0; j < NMOVES; j++) { - for (k = 0; k < NMOVES; k++) { - p1 = j && base_move(j) == base_move(k); - p2 = i && base_move(i) == base_move(k); - cij = commute[i][j]; - possible_next[i][j][k] = !(p1 || (cij && p2)); - } - } - } - - for (i = 0; i < NMOVES; i++) - inverse_move_aux[i] = i ? i + 2 - 2*((i-1)%3) : NULLMOVE; - - /* Is there a more elegant way? */ - inverse_trans_aux[uf] = uf; - inverse_trans_aux[ur] = ul; - inverse_trans_aux[ul] = ur; - inverse_trans_aux[ub] = ub; - - inverse_trans_aux[df] = df; - inverse_trans_aux[dr] = dr; - inverse_trans_aux[dl] = dl; - inverse_trans_aux[db] = db; - - inverse_trans_aux[rf] = lf; - inverse_trans_aux[rd] = bl; - inverse_trans_aux[rb] = rb; - inverse_trans_aux[ru] = fr; - - inverse_trans_aux[lf] = rf; - inverse_trans_aux[ld] = br; - inverse_trans_aux[lb] = lb; - inverse_trans_aux[lu] = fl; - - inverse_trans_aux[fu] = fu; - inverse_trans_aux[fr] = ru; - inverse_trans_aux[fd] = bu; - inverse_trans_aux[fl] = lu; - - inverse_trans_aux[bu] = fd; - inverse_trans_aux[br] = ld; - inverse_trans_aux[bd] = bd; - inverse_trans_aux[bl] = rd; - - inverse_trans_aux[mirror] = mirror; -} - -static void -init_environment() -{ - char *nissydata = getenv("NISSYDATA"); - char *localdata = getenv("XDG_DATA_HOME"); - char *home = getenv("HOME"); - bool read, write; - - if (nissydata != NULL) { - tabledir = malloc(strlen(nissydata) * sizeof(char) + 20); - strcpy(tabledir, nissydata); - } else if (localdata != NULL) { - tabledir = malloc(strlen(localdata) * sizeof(char) + 20); - strcpy(tabledir, localdata); - strcat(tabledir, "/nissy"); - } else if (home != NULL) { - tabledir = malloc(strlen(home) * sizeof(char) + 20); - strcpy(tabledir, home); - strcat(tabledir, "/.nissy"); - } - - mkdir(tabledir, 0777); - strcat(tabledir, "/tables"); - mkdir(tabledir, 0777); - - read = !access(tabledir, R_OK); - write = !access(tabledir, W_OK); - - if (!read) { - fprintf(stderr, "Table files cannot be read.\n"); - } else if (!write) { - fprintf(stderr, "Data directory not writable: "); - fprintf(stderr, "tables can be loaded, but not saved.\n"); - } -} - -static void -init_moves() { - Cube c; - CubeArray arrs; - int i; - uint16_t ui; - Move m; - - /* Generate all move cycles and flips; I do this regardless */ - for (i = 0; i < NMOVES; i++) { - if (i == U || i == x || i == y) - continue; - - c = apply_alg_generic(equiv_alg[i], (Cube){0}, pf_all, false); - - arrs = (CubeArray) { - 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_mtables_file()) - return; - - fprintf(stderr, "Cannot load %s, generating it\n", "mtables"); - - /* Initialize transition tables */ - for (m = 0; m < NMOVES; m++) { - for (ui = 0; ui < FACTORIAL12/FACTORIAL8; ui++) { - c = (Cube){ .epose = ui }; - c = apply_move_cubearray(m, c, pf_e); - epose_mtable[m][ui] = c.epose; - - c = (Cube){ .eposs = ui }; - c = apply_move_cubearray(m, c, pf_s); - eposs_mtable[m][ui] = c.eposs; - - c = (Cube){ .eposm = ui }; - c = apply_move_cubearray(m, c, pf_m); - eposm_mtable[m][ui] = c.eposm; - } - for (ui = 0; ui < POW2TO11; ui++ ) { - c = (Cube){ .eofb = ui }; - c = apply_move_cubearray(m, c, pf_eo); - eofb_mtable[m][ui] = c.eofb; - - c = (Cube){ .eorl = ui }; - c = apply_move_cubearray(m, c, pf_eo); - eorl_mtable[m][ui] = c.eorl; - - c = (Cube){ .eoud = ui }; - c = apply_move_cubearray(m, c, pf_eo); - eoud_mtable[m][ui] = c.eoud; - } - for (ui = 0; ui < POW3TO7; ui++) { - c = (Cube){ .coud = ui }; - c = apply_move_cubearray(m, c, pf_co); - coud_mtable[m][ui] = c.coud; - - c = (Cube){ .corl = ui }; - c = apply_move_cubearray(m, c, pf_co); - corl_mtable[m][ui] = c.corl; - - c = (Cube){ .cofb = ui }; - c = apply_move_cubearray(m, c, pf_co); - cofb_mtable[m][ui] = c.cofb; - } - for (ui = 0; ui < FACTORIAL8; ui++) { - c = (Cube){ .cp = ui }; - c = apply_move_cubearray(m, c, pf_cp); - cp_mtable[m][ui] = c.cp; - } - for (ui = 0; ui < FACTORIAL6; ui++) { - c = (Cube){ .cpos = ui }; - c = apply_move_cubearray(m, c, pf_cpos); - cpos_mtable[m][ui] = c.cpos; - } - } - - if (!write_mtables_file()) - fprintf(stderr, "Error writing mtables\n"); -} - -static void -init_moves_aux() -{ - /* Some standard PieceFilters */ - pf_all.epose = true; - pf_all.eposs = true; - pf_all.eposm = true; - pf_all.eofb = true; - pf_all.eorl = true; - pf_all.eoud = true; - pf_all.cp = true; - pf_all.cofb = true; - pf_all.corl = true; - pf_all.coud = true; - pf_all.cpos = true; - - pf_4val.epose = true; - pf_4val.eposs = true; - pf_4val.eposm = true; - pf_4val.eofb = true; - pf_4val.coud = true; - pf_4val.cp = true; - - pf_epcp.epose = true; - pf_epcp.eposs = true; - pf_epcp.eposm = true; - pf_epcp.cp = true; - - pf_cpos.cpos = true; - - pf_cp.cp = true; - - pf_ep.epose = true; - pf_ep.eposs = true; - pf_ep.eposm = true; - - pf_e.epose = true; - pf_s.eposs = true; - pf_m.eposm = true; - - pf_eo.eofb = true; - pf_eo.eorl = true; - pf_eo.eoud = true; - - pf_co.cofb = true; - pf_co.corl = true; - pf_co.coud = true; - - /* Used to convert to and from CubeArray */ - epe_solved[0] = FR; - epe_solved[1] = FL; - epe_solved[2] = BL; - epe_solved[3] = BR; - - eps_solved[0] = UL; - eps_solved[1] = UR; - eps_solved[2] = DL; - eps_solved[3] = DR; - - epm_solved[0] = UF; - epm_solved[1] = UB; - epm_solved[2] = DF; - epm_solved[3] = DB; - - /* Table sizes, used for reading and writing files */ - me[0] = FACTORIAL12/FACTORIAL8; - me[1] = FACTORIAL12/FACTORIAL8; - me[2] = FACTORIAL12/FACTORIAL8; - me[3] = POW2TO11; - me[4] = POW2TO11; - me[5] = POW2TO11; - me[6] = FACTORIAL8; - me[7] = POW3TO7; - me[8] = POW3TO7; - me[9] = POW3TO7; - me[10] = FACTORIAL6; - me[11] = NMOVES; - - /* Cycles *********************/ - edge_cycle[U][UF] = UR; - edge_cycle[U][UL] = UF; - edge_cycle[U][UB] = UL; - edge_cycle[U][UR] = UB; - edge_cycle[U][DF] = DF; - edge_cycle[U][DL] = DL; - edge_cycle[U][DB] = DB; - edge_cycle[U][DR] = DR; - edge_cycle[U][FR] = FR; - edge_cycle[U][FL] = FL; - edge_cycle[U][BL] = BL; - edge_cycle[U][BR] = BR; - - edge_cycle[x][UF] = DF; - edge_cycle[x][UL] = FL; - edge_cycle[x][UB] = UF; - edge_cycle[x][UR] = FR; - edge_cycle[x][DF] = DB; - edge_cycle[x][DL] = BL; - edge_cycle[x][DB] = UB; - edge_cycle[x][DR] = BR; - edge_cycle[x][FR] = DR; - edge_cycle[x][FL] = DL; - edge_cycle[x][BL] = UL; - edge_cycle[x][BR] = UR; - - edge_cycle[y][UF] = UR; - edge_cycle[y][UL] = UF; - edge_cycle[y][UB] = UL; - edge_cycle[y][UR] = UB; - edge_cycle[y][DF] = DR; - edge_cycle[y][DL] = DF; - edge_cycle[y][DB] = DL; - edge_cycle[y][DR] = DB; - edge_cycle[y][FR] = BR; - edge_cycle[y][FL] = FR; - edge_cycle[y][BL] = FL; - edge_cycle[y][BR] = BL; - - corner_cycle[U][UFR] = UBR; - corner_cycle[U][UFL] = UFR; - corner_cycle[U][UBL] = UFL; - corner_cycle[U][UBR] = UBL; - corner_cycle[U][DFR] = DFR; - corner_cycle[U][DFL] = DFL; - corner_cycle[U][DBL] = DBL; - corner_cycle[U][DBR] = DBR; - - corner_cycle[x][UFR] = DFR; - corner_cycle[x][UFL] = DFL; - corner_cycle[x][UBL] = UFL; - corner_cycle[x][UBR] = UFR; - corner_cycle[x][DFR] = DBR; - corner_cycle[x][DFL] = DBL; - corner_cycle[x][DBL] = UBL; - corner_cycle[x][DBR] = UBR; - - corner_cycle[y][UFR] = UBR; - corner_cycle[y][UFL] = UFR; - corner_cycle[y][UBL] = UFL; - corner_cycle[y][UBR] = UBL; - corner_cycle[y][DFR] = DBR; - corner_cycle[y][DFL] = DFR; - corner_cycle[y][DBL] = DFL; - corner_cycle[y][DBR] = DBL; - - center_cycle[U][U_center] = U_center; - center_cycle[U][D_center] = D_center; - center_cycle[U][R_center] = R_center; - center_cycle[U][L_center] = L_center; - center_cycle[U][F_center] = F_center; - center_cycle[U][B_center] = B_center; - - center_cycle[x][U_center] = F_center; - center_cycle[x][D_center] = B_center; - center_cycle[x][R_center] = R_center; - center_cycle[x][L_center] = L_center; - center_cycle[x][F_center] = D_center; - center_cycle[x][B_center] = U_center; - - center_cycle[y][U_center] = U_center; - center_cycle[y][D_center] = D_center; - center_cycle[y][R_center] = B_center; - center_cycle[y][L_center] = F_center; - center_cycle[y][F_center] = R_center; - center_cycle[y][B_center] = L_center; - - /* Flipped pieces *************/ - eofb_flipped[x][UF] = 1; - eofb_flipped[x][UB] = 1; - eofb_flipped[x][DF] = 1; - eofb_flipped[x][DB] = 1; - - eofb_flipped[y][FR] = 1; - eofb_flipped[y][FL] = 1; - eofb_flipped[y][BL] = 1; - eofb_flipped[y][BR] = 1; - - eorl_flipped[x][UF] = 1; - eorl_flipped[x][UL] = 1; - eorl_flipped[x][UB] = 1; - eorl_flipped[x][UR] = 1; - eorl_flipped[x][DF] = 1; - eorl_flipped[x][DL] = 1; - eorl_flipped[x][DB] = 1; - eorl_flipped[x][DR] = 1; - eorl_flipped[x][FR] = 1; - eorl_flipped[x][FL] = 1; - eorl_flipped[x][BL] = 1; - eorl_flipped[x][BR] = 1; - - eorl_flipped[y][FR] = 1; - eorl_flipped[y][FL] = 1; - eorl_flipped[y][BL] = 1; - eorl_flipped[y][BR] = 1; - - eoud_flipped[U][UF] = 1; - eoud_flipped[U][UL] = 1; - eoud_flipped[U][UB] = 1; - eoud_flipped[U][UR] = 1; - - eoud_flipped[x][UF] = 1; - eoud_flipped[x][UB] = 1; - eoud_flipped[x][DF] = 1; - eoud_flipped[x][DB] = 1; - - eoud_flipped[y][UF] = 1; - eoud_flipped[y][UL] = 1; - eoud_flipped[y][UB] = 1; - eoud_flipped[y][UR] = 1; - eoud_flipped[y][DF] = 1; - eoud_flipped[y][DL] = 1; - eoud_flipped[y][DB] = 1; - eoud_flipped[y][DR] = 1; - eoud_flipped[y][FR] = 1; - eoud_flipped[y][FL] = 1; - eoud_flipped[y][BL] = 1; - eoud_flipped[y][BR] = 1; - - coud_flipped[x][UFR] = 2; - coud_flipped[x][UFL] = 1; - coud_flipped[x][UBR] = 1; - coud_flipped[x][UBL] = 2; - coud_flipped[x][DFR] = 1; - coud_flipped[x][DFL] = 2; - coud_flipped[x][DBR] = 2; - coud_flipped[x][DBL] = 1; - - corl_flipped[U][UFR] = 1; - corl_flipped[U][UFL] = 2; - corl_flipped[U][UBL] = 1; - corl_flipped[U][UBR] = 2; - - corl_flipped[y][UFR] = 1; - corl_flipped[y][UFL] = 2; - corl_flipped[y][UBL] = 1; - corl_flipped[y][UBR] = 2; - corl_flipped[y][DFR] = 2; - corl_flipped[y][DFL] = 1; - corl_flipped[y][DBL] = 2; - corl_flipped[y][DBR] = 1; - - cofb_flipped[U][UFR] = 2; - cofb_flipped[U][UFL] = 1; - cofb_flipped[U][UBL] = 2; - cofb_flipped[U][UBR] = 1; - - cofb_flipped[x][UFR] = 1; - cofb_flipped[x][UFL] = 2; - cofb_flipped[x][UBL] = 1; - cofb_flipped[x][UBR] = 2; - cofb_flipped[x][DFR] = 2; - cofb_flipped[x][DFL] = 1; - cofb_flipped[x][DBL] = 2; - cofb_flipped[x][DBR] = 1; - - cofb_flipped[y][UFR] = 2; - cofb_flipped[y][UFL] = 1; - cofb_flipped[y][UBL] = 2; - cofb_flipped[y][UBR] = 1; - cofb_flipped[y][DFR] = 1; - cofb_flipped[y][DFL] = 2; - cofb_flipped[y][DBL] = 1; - cofb_flipped[y][DBR] = 2; - - /* Equivalent moves ***********/ - equiv_alg[NULLMOVE] = new_alg(""); - - equiv_alg[U] = new_alg(" U "); - equiv_alg[U2] = new_alg(" UU "); - equiv_alg[U3] = new_alg(" UUU "); - equiv_alg[D] = new_alg(" xx U xx "); - equiv_alg[D2] = new_alg(" xx UU xx "); - equiv_alg[D3] = new_alg(" xx UUU xx "); - equiv_alg[R] = new_alg(" yx U xxxyyy "); - equiv_alg[R2] = new_alg(" yx UU xxxyyy "); - equiv_alg[R3] = new_alg(" yx UUU xxxyyy "); - equiv_alg[L] = new_alg(" yyyx U xxxy "); - equiv_alg[L2] = new_alg(" yyyx UU xxxy "); - equiv_alg[L3] = new_alg(" yyyx UUU xxxy "); - equiv_alg[F] = new_alg(" x U xxx "); - equiv_alg[F2] = new_alg(" x UU xxx "); - equiv_alg[F3] = new_alg(" x UUU xxx "); - equiv_alg[B] = new_alg(" xxx U x "); - equiv_alg[B2] = new_alg(" xxx UU x "); - equiv_alg[B3] = new_alg(" xxx UUU x "); - - equiv_alg[Uw] = new_alg(" xx U xx y "); - equiv_alg[Uw2] = new_alg(" xx UU xx yy "); - equiv_alg[Uw3] = new_alg(" xx UUU xx yyy "); - equiv_alg[Dw] = new_alg(" U yyy "); - equiv_alg[Dw2] = new_alg(" UU yy "); - equiv_alg[Dw3] = new_alg(" UUU y "); - equiv_alg[Rw] = new_alg(" yyyx U xxxy x "); - equiv_alg[Rw2] = new_alg(" yyyx UU xxxy xx "); - equiv_alg[Rw3] = new_alg(" yyyx UUU xxxy xxx "); - equiv_alg[Lw] = new_alg(" yx U xxxyyy xxx "); - equiv_alg[Lw2] = new_alg(" yx UU xxxyyy xx "); - equiv_alg[Lw3] = new_alg(" yx UUU xxxyyy x "); - equiv_alg[Fw] = new_alg(" xxx U x yxxxyyy "); - equiv_alg[Fw2] = new_alg(" xxx UU x yxxyyy "); - equiv_alg[Fw3] = new_alg(" xxx UUU x yxyyy "); - equiv_alg[Bw] = new_alg(" x U xxx yxyyy "); - equiv_alg[Bw2] = new_alg(" x UU xxx yxxyyy "); - equiv_alg[Bw3] = new_alg(" x UUU xxx yxxxyyy "); - - equiv_alg[M] = new_alg(" yx U xx UUU yxyyy "); - equiv_alg[M2] = new_alg(" yx UU xx UU xxxy "); - equiv_alg[M3] = new_alg(" yx UUU xx U yxxxy "); - equiv_alg[S] = new_alg(" x UUU xx U yyyx "); - equiv_alg[S2] = new_alg(" x UU xx UU yyx "); - equiv_alg[S3] = new_alg(" x U xx UUU yx "); - equiv_alg[E] = new_alg(" U xx UUU xxyyy "); - equiv_alg[E2] = new_alg(" UU xx UU xxyy "); - equiv_alg[E3] = new_alg(" UUU xx U xxy "); - - equiv_alg[x] = new_alg(" x "); - equiv_alg[x2] = new_alg(" xx "); - equiv_alg[x3] = new_alg(" xxx "); - equiv_alg[y] = new_alg(" y "); - equiv_alg[y2] = new_alg(" yy "); - equiv_alg[y3] = new_alg(" yyy "); - equiv_alg[z] = new_alg(" yyy x y "); - equiv_alg[z2] = new_alg(" yy xx "); - equiv_alg[z3] = new_alg(" y x yyy "); -} - -static void -init_strings() -{ - strcpy(move_string [NULLMOVE], "-" ); - strcpy(move_string [U], "U" ); - strcpy(move_string [U2], "U2" ); - strcpy(move_string [U3], "U\'" ); - strcpy(move_string [D], "D" ); - strcpy(move_string [D2], "D2" ); - strcpy(move_string [D3], "D\'" ); - strcpy(move_string [R], "R" ); - strcpy(move_string [R2], "R2" ); - strcpy(move_string [R3], "R\'" ); - strcpy(move_string [L], "L" ); - strcpy(move_string [L2], "L2" ); - strcpy(move_string [L3], "L\'" ); - strcpy(move_string [F], "F" ); - strcpy(move_string [F2], "F2" ); - strcpy(move_string [F3], "F\'" ); - strcpy(move_string [B], "B" ); - strcpy(move_string [B2], "B2" ); - strcpy(move_string [B3], "B\'" ); - strcpy(move_string [Uw], "Uw" ); - strcpy(move_string [Uw2], "Uw2" ); - strcpy(move_string [Uw3], "Uw\'" ); - strcpy(move_string [Dw], "Dw" ); - strcpy(move_string [Dw2], "Dw2" ); - strcpy(move_string [Dw3], "Dw\'" ); - strcpy(move_string [Rw], "Rw" ); - strcpy(move_string [Rw2], "Rw2" ); - strcpy(move_string [Rw3], "Rw\'" ); - strcpy(move_string [Lw], "Lw" ); - strcpy(move_string [Lw2], "Lw2" ); - strcpy(move_string [Lw3], "Lw\'" ); - strcpy(move_string [Fw], "Fw" ); - strcpy(move_string [Fw2], "Fw2" ); - strcpy(move_string [Fw3], "Fw\'" ); - strcpy(move_string [Bw], "Bw" ); - strcpy(move_string [Bw2], "Bw2" ); - strcpy(move_string [Bw3], "Bw\'" ); - strcpy(move_string [M], "M" ); - strcpy(move_string [M2], "M2" ); - strcpy(move_string [M3], "M\'" ); - strcpy(move_string [S], "S" ); - strcpy(move_string [S2], "S2" ); - strcpy(move_string [S3], "S\'" ); - strcpy(move_string [E], "E" ); - strcpy(move_string [E2], "E2" ); - strcpy(move_string [E3], "E\'" ); - strcpy(move_string [x], "x" ); - strcpy(move_string [x2], "x2" ); - strcpy(move_string [x3], "x\'" ); - strcpy(move_string [y], "y" ); - strcpy(move_string [y2], "y2" ); - strcpy(move_string [y3], "y\'" ); - strcpy(move_string [z], "z" ); - strcpy(move_string [z2], "z2" ); - strcpy(move_string [z3], "z\'" ); - - strcpy(edge_string [UF], "UF" ); - strcpy(edge_string [UL], "UL" ); - strcpy(edge_string [UB], "UB" ); - strcpy(edge_string [UR], "UR" ); - strcpy(edge_string [DF], "DF" ); - strcpy(edge_string [DL], "DL" ); - strcpy(edge_string [DB], "DB" ); - strcpy(edge_string [DR], "DR" ); - strcpy(edge_string [FR], "FR" ); - strcpy(edge_string [FL], "FL" ); - strcpy(edge_string [BL], "BL" ); - strcpy(edge_string [BR], "BR" ); - - strcpy(corner_string [UFR], "UFR" ); - strcpy(corner_string [UFL], "UFL" ); - strcpy(corner_string [UBL], "UBL" ); - strcpy(corner_string [UBR], "UBR" ); - strcpy(corner_string [DFR], "DFR" ); - strcpy(corner_string [DFL], "DFL" ); - strcpy(corner_string [DBL], "DBL" ); - strcpy(corner_string [DBR], "DBR" ); - - strcpy(center_string [U_center], "U" ); - strcpy(center_string [D_center], "D" ); - strcpy(center_string [R_center], "R" ); - strcpy(center_string [L_center], "L" ); - strcpy(center_string [F_center], "F" ); - strcpy(center_string [B_center], "B" ); -} - -static void -init_trans() { - Cube aux, cube, c[3]; - CubeArray epcp; - int eparr[12], eoarr[12]; - int cparr[8], coarr[8]; - int i; - bool b1, b2, b3; - uint16_t ui; - Move mi, move; - Trans m; - - /* Compute sources */ - for (i = 0; i < NTRANS; i++) { - if (i == mirror) - cube = (Cube){0}; - else - cube = apply_alg(trans_algs[i], (Cube){0}); - - epose_source[i] = edge_slice(what_edge_at(cube, FR)); - eposs_source[i] = edge_slice(what_edge_at(cube, UR)); - eposm_source[i] = edge_slice(what_edge_at(cube, UF)); - eofb_source[i] = what_center_at(cube, F_center)/2; - eorl_source[i] = what_center_at(cube, R_center)/2; - eoud_source[i] = what_center_at(cube, U_center)/2; - coud_source[i] = what_center_at(cube, U_center)/2; - cofb_source[i] = what_center_at(cube, F_center)/2; - corl_source[i] = what_center_at(cube, R_center)/2; - } - - if (read_ttables_file()) - return; - - fprintf(stderr, "Cannot load %s, generating it\n", "ttables"); - - /* Initialize tables */ - for (m = 0; m < NTRANS; m++) { - if (m == mirror) { - memcpy(eparr, ep_mirror, 12 * sizeof(int)); - memcpy(cparr, cp_mirror, 8 * sizeof(int)); - } else { - epcp = (CubeArray){ .ep = eparr, .cp = cparr }; - cube = apply_alg(trans_algs[m], (Cube){0}); - cube_to_arrays(cube, &epcp, pf_epcp); - } - - for (ui = 0; ui < FACTORIAL12/FACTORIAL8; ui++) { - c[0] = admissible_ep((Cube){ .epose = ui }, pf_e); - c[1] = admissible_ep((Cube){ .eposs = ui }, pf_s); - c[2] = admissible_ep((Cube){ .eposm = ui }, pf_m); - - cube = rotate_via_compose(m,c[epose_source[m]],pf_ep); - epose_ttable[m][ui] = cube.epose; - - cube = rotate_via_compose(m,c[eposs_source[m]],pf_ep); - eposs_ttable[m][ui] = cube.eposs; - - cube = rotate_via_compose(m,c[eposm_source[m]],pf_ep); - eposm_ttable[m][ui] = cube.eposm; - } - for (ui = 0; ui < POW2TO11; ui++ ) { - int_to_sum_zero_array(ui, 2, 12, eoarr); - apply_permutation(eparr, eoarr, 12); - eo_ttable[m][ui] = digit_array_to_int(eoarr, 11, 2); - } - for (ui = 0; ui < POW3TO7; ui++) { - int_to_sum_zero_array(ui, 3, 8, coarr); - apply_permutation(cparr, coarr, 8); - co_ttable[m][ui] = digit_array_to_int(coarr, 7, 3); - if (m == mirror) - co_ttable[m][ui] = - invert_digits(co_ttable[m][ui], 3, 7); - } - for (ui = 0; ui < FACTORIAL8; ui++) { - cube = (Cube){ .cp = ui }; - cube = rotate_via_compose(m, cube, pf_cp); - cp_ttable[m][ui] = cube.cp; - } - for (ui = 0; ui < FACTORIAL6; ui++) { - cube = (Cube){ .cpos = ui }; - cube = rotate_via_compose(m, cube, pf_cpos); - cpos_ttable[m][ui] = cube.cpos; - } - for (mi = 0; mi < NMOVES; mi++) { - if (m == mirror) { - b1 = (mi >= U && mi <= Bw3); - b2 = (mi >= S && mi <= E3); - b3 = (mi >= x && mi <= z3); - if (b1 || b2 || b3) - moves_ttable[m][mi] = - inverse_move_aux[mi]; - else - moves_ttable[m][mi] = mi; - - if ((mi-1)/3==(R-1)/3 || (mi-1)/3==(Rw-1)/3) - moves_ttable[m][mi] += 3; - if ((mi-1)/3==(L-1)/3 || (mi-1)/3==(L2-1)/3) - moves_ttable[m][mi] -= 3; - } else { - aux = apply_trans(m, apply_move(mi,(Cube){0})); - for (move = 0; move < NMOVES; move++) { - cube = apply_move( - inverse_move_aux[move], aux); - if (is_solved(cube, false)) - moves_ttable[m][mi] = move; - } - } - } - } - - if (!write_ttables_file()) - fprintf(stderr, "Error writing ttables\n"); -} - -static void -init_trans_aux() -{ - ep_mirror[UF] = UF; - ep_mirror[UL] = UR; - ep_mirror[UB] = UB; - ep_mirror[UR] = UL; - ep_mirror[DF] = DF; - ep_mirror[DL] = DR; - ep_mirror[DB] = DB; - ep_mirror[DR] = DL; - ep_mirror[FR] = FL; - ep_mirror[FL] = FR; - ep_mirror[BR] = BL; - ep_mirror[BL] = BR; - - cp_mirror[UFR] = UFL; - cp_mirror[UFL] = UFR; - cp_mirror[UBL] = UBR; - cp_mirror[UBR] = UBL; - cp_mirror[DFR] = DFL; - cp_mirror[DFL] = DFR; - cp_mirror[DBL] = DBR; - cp_mirror[DBR] = DBL; - - cpos_mirror[U_center] = U_center; - cpos_mirror[D_center] = D_center; - cpos_mirror[R_center] = L_center; - cpos_mirror[L_center] = R_center; - cpos_mirror[F_center] = F_center; - cpos_mirror[B_center] = B_center; - - /* Is there a more elegant way? */ - trans_algs[uf] = new_alg(""); - trans_algs[ur] = new_alg("y"); - trans_algs[ub] = new_alg("y2"); - trans_algs[ul] = new_alg("y3"); - - trans_algs[df] = new_alg("z2"); - trans_algs[dr] = new_alg("y z2"); - trans_algs[db] = new_alg("x2"); - trans_algs[dl] = new_alg("y3 z2"); - - trans_algs[rf] = new_alg("z3"); - trans_algs[rd] = new_alg("z3 y"); - trans_algs[rb] = new_alg("z3 y2"); - trans_algs[ru] = new_alg("z3 y3"); - - trans_algs[lf] = new_alg("z"); - trans_algs[ld] = new_alg("z y3"); - trans_algs[lb] = new_alg("z y2"); - trans_algs[lu] = new_alg("z y"); - - trans_algs[fu] = new_alg("x y2"); - trans_algs[fr] = new_alg("x y"); - trans_algs[fd] = new_alg("x"); - trans_algs[fl] = new_alg("x y3"); - - trans_algs[bu] = new_alg("x3"); - trans_algs[br] = new_alg("x3 y"); - trans_algs[bd] = new_alg("x3 y2"); - trans_algs[bl] = new_alg("x3 y3"); -} - - -/* Public functions implementation *******************************************/ - -Cube -apply_alg(Alg *alg, Cube cube) -{ - return apply_alg_generic(alg, cube, pf_all, true); -} - -Cube -apply_move(Move m, Cube cube) -{ - return (Cube) { - .epose = epose_mtable[m][cube.epose], - .eposs = eposs_mtable[m][cube.eposs], - .eposm = eposm_mtable[m][cube.eposm], - .eofb = eofb_mtable[m][cube.eofb], - .eorl = eorl_mtable[m][cube.eorl], - .eoud = eoud_mtable[m][cube.eoud], - .coud = coud_mtable[m][cube.coud], - .cofb = cofb_mtable[m][cube.cofb], - .corl = corl_mtable[m][cube.corl], - .cp = cp_mtable[m][cube.cp], - .cpos = cpos_mtable[m][cube.cpos] - }; -} - -Cube -apply_trans(Trans t, Cube cube) -{ - uint16_t aux_epos[3] = { cube.epose, cube.eposs, cube.eposm }; - uint16_t aux_eo[3] = { cube.eoud, cube.eorl, cube.eofb }; - uint16_t aux_co[3] = { cube.coud, cube.corl, cube.cofb }; - - return (Cube) { - .epose = epose_ttable[t][aux_epos[epose_source[t]]], - .eposs = eposs_ttable[t][aux_epos[eposs_source[t]]], - .eposm = eposm_ttable[t][aux_epos[eposm_source[t]]], - .eofb = eo_ttable[t][aux_eo[eofb_source[t]]], - .eorl = eo_ttable[t][aux_eo[eorl_source[t]]], - .eoud = eo_ttable[t][aux_eo[eoud_source[t]]], - .coud = co_ttable[t][aux_co[coud_source[t]]], - .corl = co_ttable[t][aux_co[corl_source[t]]], - .cofb = co_ttable[t][aux_co[cofb_source[t]]], - .cp = cp_ttable[t][cube.cp], - .cpos = cpos_ttable[t][cube.cpos] - }; -} - -Move -base_move(Move m) -{ - if (m == NULLMOVE) - return NULLMOVE; - else - return m - (m-1)%3; -} - -Cube -compose(Cube c2, Cube c1) -{ - return compose_filtered(c2, c1, pf_all); -} - -uint64_t -epos_dependent_cube(Cube c) -{ - return epos_dependent_aux[c.eposs/FACTORIAL4][c.epose/FACTORIAL4]; -} - -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; -} - -void -genalgset(AlgSet *as) -{ - uint64_t i; - - if (as->generated) - return; - - /* TODO: check if memory is enough, otherwise maybe crash gracefully? */ - as->table = malloc(as->size * sizeof(AlgList *)); - - if (read_algset_file(as)) { - as->generated = true; - return; - } - - fprintf(stderr, "Cannot load %s, generating it\n", as->filename); - - for (i = 0; i < as->size; i++) { - as->table[i] = solve(as->antindex(i), as->step, &as->opts); - fprintf(stderr, "Generated %lu / %lu cases\n", i, as->size); - } - - if (!write_algset_file(as)) - fprintf(stderr, "Error writing algset file\n"); - - as->generated = true; -} - -void -genptable(PruneData *pd) -{ - uint64_t j; - DfsData dd = { - .m = 0, - .last1 = NULLMOVE, - .last2 = NULLMOVE - }; - - if (pd->generated) - return; - - /* TODO: check if memory is enough, otherwise maybe crash gracefully? */ - pd->ptable = malloc(ptablesize(pd) * sizeof(uint8_t)); - - if (read_ptable_file(pd)) { - pd->generated = true; - return; - } - - fprintf(stderr, "Cannot load %s, generating it\n", pd->filename); - - /* We use 4 bits per value, so any distance >= 15 is set to 15 */ - for (j = 0; j < pd->size; j++) - ptable_update(pd, j, 15); - - moveset_to_list(pd->moveset, NULL, dd.sorted_moves); - movelist_to_position(dd.sorted_moves, dd.move_position); - - pd->reached = malloc(ptablesize(pd) * sizeof(uint8_t)); - for (dd.d = 0, pd->n = 0; dd.d < 15 && pd->n < pd->size; dd.d++) { - memset(pd->reached, 0, ptablesize(pd)*sizeof(uint8_t)); - genptable_dfs((Cube){0}, pd, &dd); - fprintf(stderr, "Depth %d completed, generated %lu/%lu\n", - dd.d, pd->n, pd->size); - } - - if (!write_ptable_file(pd)) - fprintf(stderr, "Error writing ptable file\n"); - - pd->generated = true; - free(pd->reached); -} - -Cube -inverse_cube(Cube cube) -{ - CubeArray *arr = new_cubearray(cube, pf_all); - CubeArray *inv = new_cubearray((Cube){0}, pf_all); - Cube ret; - int i; - - for (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 (i = 0; i < 8; i++) { - inv->cp[arr->cp[i]] = i; - inv->coud[arr->cp[i]] = (3 - arr->coud[i]) % 3; - inv->corl[arr->cp[i]] = (3 - arr->corl[i]) % 3; - inv->cofb[arr->cp[i]] = (3 - arr->cofb[i]) % 3; - } - - for (int i = 0; i < 6; i++) - inv->cpos[arr->cpos[i]] = i; - - ret = arrays_to_cube(inv, pf_all); - free_cubearray(arr, pf_all); - free_cubearray(inv, pf_all); - - return ret; -} - -Move -inverse_move(Move m) -{ - return inverse_move_aux[m]; -} - -Trans -inverse_trans(Trans t) -{ - return inverse_trans_aux[t]; -} - -bool -is_admissible(Cube cube) -{ - /* TODO: this should check consistency of different orientations */ - /* TODO: check that centers are opposite and admissible */ - - CubeArray *a = new_cubearray(cube, pf_all); - int parity; - bool perm; - - perm = is_perm(a->ep, 12) && - is_perm(a->cp, 8) && - is_perm(a->cpos, 6); - parity = perm_sign(a->ep, 12) + - perm_sign(a->cp, 8) + - perm_sign(a->cpos, 6); - - return perm && parity % 2 == 0; -} - -bool -is_solved(Cube cube, bool reorient) -{ - Trans i; - - if (reorient) - for (i = 0; i < NROTATIONS; i++) - if (is_solved(apply_alg(trans_algs[i],cube), false)) - return true; - - return equal(cube, (Cube){0}); -} - -bool -is_solved_block(Cube cube, Block block) -{ - int i; - - for (i = 0; i < 12; i++) - if (block.edge[i] && !is_solved_edge(cube, i)) - return false; - for (i = 0; i < 8; i++) - if (block.corner[i] && !is_solved_corner(cube, i)) - return false; - for (i = 0; i < 6; i++) - if (block.center[i] && !is_solved_center(cube, i)) - return false; - - return true; -} - -bool -is_solved_center(Cube cube, Center c) -{ - return what_center_at(cube, c) == c; -} - -bool -is_solved_corner(Cube cube, Corner c) -{ - return what_corner_at(cube, c) == c && - what_orientation_corner(cube.coud, c); -} - -bool -is_solved_edge(Cube cube, Edge e) -{ - return what_edge_at(cube, e) == e && - what_orientation_edge(cube.eofb, e); -} - -int -piece_orientation(Cube cube, int piece, char *orientation) -{ - int arr[12], n, b; - uint16_t x; - - if (!strcmp(orientation, "eofb")) { - x = cube.eofb; - n = 12; - b = 2; - } else if (!strcmp(orientation, "eorl")) { - x = cube.eorl; - n = 12; - b = 2; - } else if (!strcmp(orientation, "eoud")) { - x = cube.eoud; - n = 12; - b = 2; - } else if (!strcmp(orientation, "coud")) { - x = cube.coud; - n = 8; - b = 3; - } else if (!strcmp(orientation, "corl")) { - x = cube.corl; - n = 8; - b = 3; - } else if (!strcmp(orientation, "cofb")) { - x = cube.cofb; - n = 8; - b = 3; - } else { - return -1; - } - - int_to_sum_zero_array(x, b, n, arr); - if (piece < n) - return arr[piece]; - - return -1; -} - -void -print_cube(Cube cube) -{ -/* - CubeArray *arr = new_cubearray(cube, pf_all); - - 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"); - - free_cubearray(arr, pf_all); -*/ - - for (int i = 0; i < 12; i++) - printf(" %s ", edge_string[what_edge_at(cube, i)]); - printf("\n"); - - for (int i = 0; i < 12; i++) - printf(" %d ", what_orientation_edge(cube.eofb, i)); - printf("\n"); - - for (int i = 0; i < 8; i++) - printf("%s ", corner_string[what_corner_at(cube, i)]); - printf("\n"); - - for (int i = 0; i < 8; i++) - printf(" %d ", what_orientation_corner(cube.coud, i)); - printf("\n"); - - for (int i = 0; i < 6; i++) - printf(" %s ", center_string[what_center_at(cube, i)]); - printf("\n"); - -} - -Cube -random_cube() -{ - CubeArray *arr = new_cubearray((Cube){0}, pf_4val); - Cube ret; - int ep, cp, eo, co; - - ep = rand() % FACTORIAL12; - cp = rand() % FACTORIAL8; - eo = rand() % POW2TO11; - co = rand() % POW3TO7; - - index_to_perm(ep, 12, arr->ep); - index_to_perm(cp, 8, arr->cp); - int_to_sum_zero_array(eo, 2, 12, arr->eofb); - int_to_sum_zero_array(co, 3, 8, arr->coud); - - if (perm_sign(arr->ep, 12) != perm_sign(arr->cp, 8)) - swap(&(arr->ep[0]), &(arr->ep[1])); - - ret = arrays_to_cube(arr, pf_4val); - free_cubearray(arr, pf_4val); - - return ret; -} - -AlgList * -solve(Cube cube, Step step, SolveOptions *opts) -{ - AlgListNode *node; - AlgList *sols = new_alglist(); - Cube c = apply_trans(opts->pre_trans, cube); - DfsData dd = { - .m = 0, - .niss = false, - .lb = -1, - .last1 = NULLMOVE, - .last2 = NULLMOVE, - .sols = sols, - .current_alg = new_alg("") - }; - - if (step.ready != NULL && step.ready(c, 1) != 0) { - fprintf(stderr, "Cube not ready for solving step\n"); - return sols; - } - - moveset_to_list(step.moveset, step.check, dd.sorted_moves); - movelist_to_position(dd.sorted_moves, dd.move_position); - - for (dd.d = opts->min_moves; - dd.d <= opts->max_moves && !(sols->len && opts->optimal_only); - dd.d++) { - if (opts->feedback) - fprintf(stderr, - "Found %d solutions, searching depth %d...\n", - sols->len, dd.d); - dfs(c, step, opts, &dd); - } - - for (node = sols->first; node != NULL; node = node->next) - transform_alg(inverse_trans_aux[opts->pre_trans], node->alg); - - free_alg(dd.current_alg); - return sols; -} - -Alg * -inverse_alg(Alg *alg) -{ - Alg *ret = new_alg(""); - int i; - - for (i = alg->len-1; i >= 0; i--) - append_move(ret, alg->move[i], alg->inv[i]); - - return ret; -} - -Alg * -new_alg(char *str) -{ - Alg *alg = malloc(sizeof(Alg)); - int i; - bool niss = false; - Move j, m; - - alg->move = malloc(30 * sizeof(Move)); - alg->inv = malloc(30 * sizeof(bool)); - alg->allocated = 30; - alg->len = 0; - - for (i = 0; str[i]; i++) { - if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n') - continue; - - if (str[i] == '(' && niss) { - fprintf(stderr, "Error reading moves: nested ( )\n"); - return alg; - } - - if (str[i] == ')' && !niss) { - fprintf(stderr, "Error reading moves: unmatched )\n"); - return alg; - } - - if (str[i] == '(' || str[i] == ')') { - niss = !niss; - continue; - } - - for (j = 0; j < NMOVES; j++) { - if (str[i] == move_string[j][0]) { - m = j; - if (m <= B && str[i+1]=='w') { - m += Uw - U; - i++; - } - if (str[i+1]=='2') { - m += 1; - i++; - } else if (str[i+1]=='\'' || str[i+1]=='3') { - m += 2; - i++; - } - append_move(alg, m, niss); - break; - } - } - } - - return alg; -} - -Alg * -on_inverse(Alg *alg) -{ - Alg *ret = new_alg(""); - int i; - - for (i = 0; i < alg->len; i++) - append_move(ret, alg->move[i], !alg->inv[i]); - - return ret; -} - -void -print_alg(Alg *alg, bool l) -{ - /* TODO: make it possible to print to stdout or to string */ - /* Maybe just return a string */ - char fill[4]; - int i; - bool niss = false; - - for (i = 0; i < alg->len; i++) { - if (!niss && alg->inv[i]) - strcpy(fill, i == 0 ? "(" : " ("); - if (niss && !alg->inv[i]) - strcpy(fill, ") "); - if (niss == alg->inv[i]) - strcpy(fill, i == 0 ? "" : " "); - - printf("%s%s", fill, move_string[alg->move[i]]); - niss = alg->inv[i]; - } - - if (niss) - printf(")"); - if (l) - printf(" (%d)", alg->len); - - printf("\n"); -} - -void -print_alglist(AlgList *al, bool l) -{ - AlgListNode *i; - - for (i = al->first; i != NULL; i = i->next) - print_alg(i->alg, l); -} - -void -print_ptable(PruneData *pd) -{ - uint64_t i, a[16]; - - for (i = 0; i < 16; i++) - a[i] = 0; - - if (!pd->generated) - genptable(pd); - - for (i = 0; i < pd->size; i++) - a[ptableval(pd, i)]++; - - fprintf(stderr, "Values for table %s\n", pd->filename); - for (i = 0; i < 16; i++) - printf("%2lu\t%10lu\n", i, a[i]); -} - -uint64_t -ptablesize(PruneData *pd) -{ - return (pd->size + 1) / 2; -} - -int -ptableval(PruneData *pd, uint64_t ind) -{ - return (ind % 2) ? pd->ptable[ind/2] / 16 : pd->ptable[ind/2] % 16; -} - - -Alg * -trans_alg(Trans i) -{ - return trans_algs[i]; -} - -void -transform_alg(Trans t, Alg *alg) -{ - int i; - - for (i = 0; i < alg->len; i++) - alg->move[i] = moves_ttable[t][alg->move[i]]; -} - -Center -what_center_at(Cube cube, Center c) -{ - return what_center_at_aux[cube.cpos][c]; -} - -Corner -what_corner_at(Cube cube, Corner c) -{ - return what_corner_at_aux[cube.cp][c]; -} - -Edge -what_edge_at(Cube cube, Edge e) -{ - Edge ret; - CubeArray *arr = new_cubearray(cube, pf_ep); - - ret = arr->ep[e]; - - free_cubearray(arr, pf_ep); - return ret; -} - -int -what_orientation_corner(int co, Corner c) -{ - if (c < 7) - return (co / powint(3, c)) % 3; - else - return what_orientation_last_corner_aux[co]; -} - -int -what_orientation_edge(int eo, Edge e) -{ - if (e < 11) - return (eo & (1 << e)) ? 1 : 0; - else - return what_orientation_last_edge_aux[eo]; -} - -Center -where_is_center(Cube cube, Center c) -{ - return where_is_center_aux[cube.cpos][c]; -} - -Corner -where_is_corner(Cube cube, Corner c) -{ - return where_is_corner_aux[cube.cp][c]; -} - - -void -init() -{ - /* Order is important! */ - init_environment(); - init_strings(); - init_moves_aux(); - init_moves(); - init_auxtables(); - init_trans_aux(); - init_trans(); -} - -- cgit v1.3