From 3568412f8f230774d0d11d7ed1c897424f95d3ef Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 11 Nov 2021 21:37:34 +0100 Subject: Rewritten from scratch. Welocme nissy 2.0! --- old/2021-06-23-uint16t/cube.c | 2762 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 2762 insertions(+) create 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 new file mode 100644 index 0000000..0381ba0 --- /dev/null +++ b/old/2021-06-23-uint16t/cube.c @@ -0,0 +1,2762 @@ +#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