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-07-02-genptable-dfs/cube.c | 3394 ++++++++++++++++++++++++++++++ old/2021-07-02-genptable-dfs/cube.h | 90 + old/2021-07-02-genptable-dfs/cubetypes.h | 250 +++ old/2021-07-02-genptable-dfs/macros.h | 23 + old/2021-07-02-genptable-dfs/main.c | 80 + old/2021-07-02-genptable-dfs/steps.c | 307 +++ old/2021-07-02-genptable-dfs/steps.h | 24 + 7 files changed, 4168 insertions(+) create mode 100644 old/2021-07-02-genptable-dfs/cube.c create mode 100644 old/2021-07-02-genptable-dfs/cube.h create mode 100644 old/2021-07-02-genptable-dfs/cubetypes.h create mode 100644 old/2021-07-02-genptable-dfs/macros.h create mode 100644 old/2021-07-02-genptable-dfs/main.c create mode 100644 old/2021-07-02-genptable-dfs/steps.c create mode 100644 old/2021-07-02-genptable-dfs/steps.h (limited to 'old/2021-07-02-genptable-dfs') diff --git a/old/2021-07-02-genptable-dfs/cube.c b/old/2021-07-02-genptable-dfs/cube.c new file mode 100644 index 0000000..a7d137c --- /dev/null +++ b/old/2021-07-02-genptable-dfs/cube.c @@ -0,0 +1,3394 @@ +#include "cube.h" + +/* Local functions **********************************************************/ + +static Cube admissible_ep(Cube cube, PieceFilter f); +static Cube admissible_eos_from_eofbepos(Cube cube); +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 int 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_pos(int pos1, int pos2); +static int epos_from_arrays(int *epos, int *ep); +static void epos_to_partial_ep(int 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 gensym(SymData *sd); +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 init_auxtables(); +static void init_cphtr_cosets(); +static void init_cphtr_left_cosets_bfs(int i, int c); +static void init_cphtr_right_cosets_color(int i, int c); +static void init_environment(); +static void init_moves(); +static void init_moves_aux(); +static void init_strings(); +static void init_symdata(); +static void init_trans(); +static void init_trans_aux(); +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, Estimator 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 void ptable_update(PruneData *pd, Cube cube, int m); +static void realloc_alg(Alg *alg, int n); +static bool read_mtables_file(); +static bool read_ptable_file(PruneData *pd); +static bool read_symdata_file(SymData *sd); +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_mtables_file(); +static bool write_ptable_file(PruneData *pd); +static bool write_symdata_file(SymData *sd); +static bool write_ttables_file(); + + +/* 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 Cube admissible_ee_aux[POW2TO11*BINOM12ON4]; +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 int cphtr_left_cosets[FACTORIAL8]; +static int cphtr_right_cosets[FACTORIAL8]; +static int cphtr_right_rep[BINOM8ON4*6]; +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 int epose_ttable[NTRANS][FACTORIAL12/FACTORIAL8]; +static int eposs_ttable[NTRANS][FACTORIAL12/FACTORIAL8]; +static int eposm_ttable[NTRANS][FACTORIAL12/FACTORIAL8]; +static int eo_ttable[NTRANS][POW2TO11]; +static int cp_ttable[NTRANS][FACTORIAL8]; +static int co_ttable[NTRANS][POW3TO7]; +static int cpos_ttable[NTRANS][FACTORIAL6]; +static Move moves_ttable[NTRANS][NMOVES]; + +static int epose_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; +static int eposs_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; +static int eposm_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; +static int eofb_mtable[NMOVES][POW2TO11]; +static int eorl_mtable[NMOVES][POW2TO11]; +static int eoud_mtable[NMOVES][POW2TO11]; +static int cp_mtable[NMOVES][FACTORIAL8]; +static int coud_mtable[NMOVES][POW3TO7]; +static int cofb_mtable[NMOVES][POW3TO7]; +static int corl_mtable[NMOVES][POW3TO7]; +static int 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 * rotation_algs[NROTATIONS]; + + +/* Symmetry data for some coordinates ****************************************/ + +static Trans +trans_group_udfix[16] = { + uf, ur, ub, ul, + df, dr, db, dl, + uf_mirror, ur_mirror, ub_mirror, ul_mirror, + df_mirror, dr_mirror, db_mirror, dl_mirror, +}; + +SymData +sd_coud_16 = { + .filename = "sd_coud_16", + .coord = &coord_coud, + .sym_coord = &coord_coud_sym16, + .ntrans = 16, + .trans = trans_group_udfix +}; + +SymData +sd_eofbepos_16 = { + .filename = "sd_eofbepos_16", + .coord = &coord_eofbepos, + .sym_coord = &coord_eofbepos_sym16, + .ntrans = 16, + .trans = trans_group_udfix +}; + +static int n_all_symdata = 2; +static SymData * all_sd[2] = { &sd_coud_16, &sd_eofbepos_16 }; + +/* Coordinates and their implementation **************************************/ + +static uint64_t index_eofb(Cube cube); +static uint64_t index_eofbepos(Cube cube); +static uint64_t index_coud(Cube cube); +static uint64_t index_corners(Cube cube); +static uint64_t index_cornershtr(Cube cube); +static uint64_t index_drud(Cube cube); +static uint64_t index_coud_sym16(Cube cube); +static uint64_t index_eofbepos_sym16(Cube cube); +static uint64_t index_drud_sym16(Cube cube); +static uint64_t index_khuge(Cube cube); + +static Cube antindex_eofb(uint64_t ind); +static Cube antindex_eofbepos(uint64_t ind); +static Cube antindex_coud(uint64_t ind); +static Cube antindex_corners(uint64_t ind); +static Cube antindex_cornershtr(uint64_t ind); +static Cube antindex_drud(uint64_t ind); +static Cube antindex_coud_sym16(uint64_t ind); +static Cube antindex_eofbepos_sym16(uint64_t ind); +static Cube antindex_drud_sym16(uint64_t ind); +static Cube antindex_khuge(uint64_t ind); + +Coordinate +coord_eofb = { + .index = index_eofb, + .cube = antindex_eofb, + .check = check_eofb, + .max = POW2TO11 +}; + +Coordinate +coord_eofbepos = { + .index = index_eofbepos, + .cube = antindex_eofbepos, + .check = check_eofbepos, + .max = POW2TO11 * BINOM12ON4 +}; + +Coordinate +coord_coud = { + .index = index_coud, + .cube = antindex_coud, + .check = check_coud, + .max = POW3TO7 +}; + +Coordinate +coord_corners = { + .index = index_corners, + .cube = antindex_corners, + .check = check_corners, + .max = POW3TO7 * FACTORIAL8 +}; + +Coordinate +coord_cornershtr = { + .index = index_cornershtr, + .cube = antindex_cornershtr, + .check = check_cornershtr, + .max = POW3TO7 * BINOM8ON4 * 6 +}; + +Coordinate +coord_drud = { + .index = index_drud, + .cube = antindex_drud, + .check = check_drud, + .max = POW2TO11 * POW3TO7 * BINOM12ON4 +}; + +Coordinate +coord_eofbepos_sym16 = { + .index = index_eofbepos_sym16, + .cube = antindex_eofbepos_sym16, + .check = check_eofbepos, +}; + +Coordinate +coord_coud_sym16 = { + .index = index_coud_sym16, + .cube = antindex_coud_sym16, + .check = check_coud, +}; + +Coordinate +coord_drud_sym16 = { + .index = index_drud_sym16, + .cube = antindex_drud_sym16, + .check = check_drud, + .max = POW3TO7 * 64430 +}; + +Coordinate +coord_khuge = { + .index = index_khuge, + .cube = antindex_khuge, + .check = check_khuge, + .max = POW3TO7 * FACTORIAL4 * 64430 +}; + + +static uint64_t +index_eofb(Cube cube) +{ + return cube.eofb; +} + +static uint64_t +index_eofbepos(Cube cube) +{ + return (cube.epose / FACTORIAL4) * POW2TO11 + cube.eofb; +} + +static uint64_t +index_coud(Cube cube) +{ + return cube.coud; +} + +static uint64_t +index_corners(Cube cube) +{ + return cube.coud * FACTORIAL8 + cube.cp; +} + +static uint64_t +index_cornershtr(Cube cube) +{ + return cube.coud * BINOM8ON4 * 6 + cphtr(cube); +} + +static uint64_t +index_drud(Cube cube) +{ + uint64_t a, b, c; + + a = cube.eofb; + b = cube.coud; + c = cube.epose / FACTORIAL4; + + b *= POW2TO11; + c *= POW2TO11 * POW3TO7; + + return a + b + c; +} + +static uint64_t +index_coud_sym16(Cube cube) +{ + return sd_coud_16.class[index_coud(cube)]; +} + +static uint64_t +index_drud_sym16(Cube cube) +{ + Trans t; + Cube c; + + t = sd_eofbepos_16.transtorep[index_eofbepos(cube)]; + c = apply_trans(t, cube); + + return index_eofbepos_sym16(c) * POW3TO7 + c.coud; +} + +static uint64_t +index_eofbepos_sym16(Cube cube) +{ + return sd_eofbepos_16.class[index_eofbepos(cube)]; +} + +static uint64_t +index_khuge(Cube cube) +{ + Trans t; + Cube c; + uint64_t a; + + t = sd_eofbepos_16.transtorep[index_eofbepos(cube)]; + c = apply_trans(t, cube); + a = (index_eofbepos_sym16(c) * 24) + (c.epose % 24); + + return a * POW3TO7 + c.coud; +} + + +/* TODO: rename */ +static Cube +antindex_eofb(uint64_t ind) +{ + return (Cube){ .eofb = ind, .eorl = ind, .eoud = ind }; +} + +static Cube +antindex_eofbepos(uint64_t ind) +{ + return admissible_ee_aux[ind]; +} + +/* TODO: rename */ +static Cube +antindex_coud(uint64_t ind) +{ + return (Cube){ .coud = ind, .corl = ind, .cofb = ind }; +} + +/* TODO: admissible co for other orientations */ +static Cube +antindex_corners(uint64_t ind) +{ + Cube c = {0}; + + c.coud = ind / FACTORIAL8; + c.cp = ind % FACTORIAL8; + + return c; +} + +/* TODO: admissible co for other orientations */ +static Cube +antindex_cornershtr(uint64_t ind) +{ + Cube c = anti_cphtr(ind % (BINOM8ON4 * 6)); + + c.coud = ind / (BINOM8ON4 * 6); + + return c; +} + +/* TODO: admissible eos and cos */ +static Cube +antindex_drud(uint64_t ind) +{ + Cube c = {0}; + + c.eofb = ind % POW2TO11; + c.coud = (ind / POW2TO11) % POW3TO7; + c.epose = (ind % (POW2TO11 * POW3TO7)) * FACTORIAL4; + + return c; +} + +static Cube +antindex_coud_sym16(uint64_t ind) +{ + return sd_coud_16.rep[ind]; +} + +static Cube +antindex_eofbepos_sym16(uint64_t ind) +{ + return sd_eofbepos_16.rep[ind]; +} + +static Cube +antindex_drud_sym16(uint64_t ind) +{ + Cube c; + + c = sd_eofbepos_16.rep[ind/POW3TO7]; + c.coud = ind % POW3TO7; + c.cofb = c.coud; + c.corl = c.coud; + + return c; +} + +static Cube +antindex_khuge(uint64_t ind) +{ + Cube c; + + c = sd_eofbepos_16.rep[ind/(FACTORIAL4*POW3TO7)]; + c.epose = ((c.epose / 24) * 24) + ((ind/POW3TO7) % 24); + c.coud = ind % POW3TO7; + + return c; +} + + +/* Checkers ******************************************************************/ + +bool +check_centers(Cube cube) +{ + return cube.cpos == 0; +} + +bool +check_corners(Cube cube) +{ + return cube.cp == 0 && cube.coud == 0; +} + +bool +check_cornershtr(Cube cube) +{ + return cube.coud == 0 && cphtr(cube) == 0; /* TODO: use array cphtrcosets*/ +} + +bool +check_coud(Cube cube) +{ + return cube.coud == 0; +} + +bool +check_drud(Cube cube) +{ + return cube.eofb == 0 && cube.eorl == 0 && cube.coud == 0; +} + +bool +check_eofb(Cube cube) +{ + return cube.eofb == 0; +} + +bool +check_eofbepos(Cube cube) +{ + return cube.eofb == 0 && cube.epose / 24 == 0; +} + +bool +check_epose(Cube cube) +{ + return cube.epose == 0; +} + +bool +check_ep(Cube cube) +{ + return cube.epose == 0 && cube.eposs == 0 && cube.eposm == 0; +} + +bool +check_khuge(Cube cube) +{ + return check_drud(cube) && cube.epose % 24 == 0; +} + +bool +check_nothing(Cube cube) +{ + return is_admissible(cube); /*TODO: maybe change?*/ +} + +/* Movesets ******************************************************************/ + +bool +moveset_HTM(Move m) +{ + return m >= U && m <= B3; +} + +bool +moveset_URF(Move m) +{ + Move b = base_move(m); + + return b == U || b == R || b == F; +} + + +/* Local functions implementation ********************************************/ + +/* TODO: this should be an anti index (maybe?) */ +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 Cube +admissible_eos_from_eofbepos(Cube cube) +{ + Edge e; + Cube ret; + CubeArray *arr = new_cubearray(cube, pf_all); + + memcpy(arr->eorl, arr->eofb, 12 * sizeof(int)); + memcpy(arr->eoud, arr->eofb, 12 * sizeof(int)); + + for (e = 0; e < 12; e++) { + if ((edge_slice(e) != 0 && edge_slice(arr->ep[e]) == 0) || + (edge_slice(e) == 0 && edge_slice(arr->ep[e]) != 0)) + arr->eorl[e] = 1 - arr->eorl[e]; + if ((edge_slice(e) != 2 && edge_slice(arr->ep[e]) == 2) || + (edge_slice(e) == 2 && edge_slice(arr->ep[e]) != 2)) + arr->eoud[e] = 1 - arr->eoud[e]; + } + + ret = arrays_to_cube(arr, pf_all); + free_cubearray(arr, pf_all); + + 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 int +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 int +cphtr_cp(int cp) +{ + int i, a[8]; + + index_to_perm(cp, 8, a); + + for (i = 0; i < 8; i++) + if (a[i] == UFR || a[i] == UBL || a[i] == DFL || a[i] == DBR) + a[i] = 0; + else + a[i] = 1; + + swap(&a[1], &a[5]); + swap(&a[3], &a[7]); + + return subset_to_index(a, 8, 4); +} +*/ + +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; moves[i] != NULLMOVE && dd->sols->len < maxnsol; i++) { + m = moves[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; + CubeTarget ct; + + ct.cube = apply_move(inverse_move(l1), (Cube){0}); + ct.target = 1; + + if (dd->current_alg->len == 0 || s.estimate(ct)) { + 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) +{ + CubeTarget ct = { + .cube = c, + .target = dd->d - dd->current_alg->len + }; + + if (dd->sols->len >= opts->max_solutions) + return true; + + dd->lb = s.estimate(ct); + 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_pos(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 int +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(int 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) +{ + int oldval = ptableval(pd, c); + + if (oldval < dd->m || pd->n == pd->coord->max || + (dd->m != 0 && pd->coord->check(c)) ) + return; + + if (dd->m == dd->d) { + if (dd->m < oldval) + ptable_update(pd, c, 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 +gensym(SymData *sd) +{ + uint64_t i, in, nreps = 0; + int j; + Cube c, d; + + if (sd->generated) + return; + + sd->class = malloc(sd->coord->max * sizeof(uint64_t)); + sd->rep = malloc(sd->coord->max * sizeof(Cube)); + sd->transtorep = malloc(sd->coord->max * sizeof(Trans)); + + if (read_symdata_file(sd)) { + sd->generated = true; + return; + } + + fprintf(stderr, "Cannot load %s, generating it\n", sd->filename); + + for (i = 0; i < sd->coord->max; i++) + sd->class[i] = sd->coord->max + 1; + + for (i = 0; i < sd->coord->max; i++) { + if (sd->class[i] == sd->coord->max + 1) { + c = sd->coord->cube(i); + sd->rep[nreps] = c; + for (j = 0; j < sd->ntrans; j++) { + d = apply_trans(sd->trans[j], c); + in = sd->coord->index(d); + + if (sd->class[in] == sd->coord->max + 1) { + sd->class[in] = nreps; + sd->transtorep[in] = + inverse_trans(sd->trans[j]); + } + } + nreps++; + } + } + + sd->sym_coord->max = nreps; + sd->rep = realloc(sd->rep, nreps * sizeof(Cube)); + sd->generated = true; + + fprintf(stderr, "Found %lu classes\n", nreps); + + if (!write_symdata_file(sd)) + fprintf(stderr, "Error writing SymData file\n"); + + return; +} + +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, Estimator f, Move *r) +{ + CubeTarget ct = { .target = 1 }; + 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)) { + ct.cube = apply_move(i, (Cube){0}); + if (f != NULL && f(ct)) + 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 void +ptable_update(PruneData *pd, Cube cube, int n) +{ + uint64_t ind = pd->coord->index(cube); + 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_mtables_file() +{ + FILE *f; + char fname[strlen(tabledir)+20]; + int m, b = sizeof(int); + 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_symdata_file(SymData *sd) +{ + FILE *f; + char fname[strlen(tabledir)+100]; + uint64_t n = sd->coord->max, *sn = &sd->sym_coord->max; + bool r = true; + + strcpy(fname, tabledir); + strcat(fname, "/"); + strcat(fname, sd->filename); + + if ((f = fopen(fname, "rb")) == NULL) + return false; + + r = r && fread(&sd->sym_coord->max, sizeof(uint64_t), 1, f) == 1; + r = r && fread(sd->rep, sizeof(Cube), *sn, f) == *sn; + r = r && fread(sd->class, sizeof(uint64_t), n, f) == n; + r = r && fread(sd->transtorep, sizeof(Trans), n, f) == n; + + fclose(f); + return r; +} + +static bool +read_ttables_file() +{ + FILE *f; + char fname[strlen(tabledir)+20]; + int b = sizeof(int); + 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) +{ + 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 + }; + + Alg *inv = inverse_alg(rotation_algs[r % NROTATIONS]); + Cube ret = {0}; + + if (r >= NROTATIONS) + ret = move_via_arrays(&ma, ret, f); + ret = apply_alg_generic(inv, ret, f, true); + + ret = compose_filtered(c, ret, f); + + ret = apply_alg_generic(rotation_algs[r % NROTATIONS], ret, f, true); + if (r >= NROTATIONS) + ret = move_via_arrays(&ma, ret, f); + + free_alg(inv); + 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_mtables_file() +{ + FILE *f; + char fname[strlen(tabledir)+20]; + int m, b = sizeof(int); + 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_symdata_file(SymData *sd) +{ + FILE *f; + char fname[strlen(tabledir)+100]; + uint64_t n = sd->coord->max, *sn = &sd->sym_coord->max; + bool r = true; + + strcpy(fname, tabledir); + strcat(fname, "/"); + strcat(fname, sd->filename); + + if ((f = fopen(fname, "wb")) == NULL) + return false; + + r = r && fwrite(&sd->sym_coord->max, sizeof(uint64_t), 1, f) == 1; + r = r && fwrite(sd->rep, sizeof(Cube), *sn, f) == *sn; + r = r && fwrite(sd->class, sizeof(uint64_t), n, f) == n; + r = r && fwrite(sd->transtorep, sizeof(Trans), n, f) == n; + + fclose(f); + return r; +} + +static bool +write_ttables_file() +{ + FILE *f; + char fname[strlen(tabledir)+20]; + bool r = true; + int b = sizeof(int); + 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 < POW2TO11*BINOM12ON4; ui++) { + k = (ui / POW2TO11) * 24; + c1 = admissible_ep((Cube){ .epose = k }, pf_e); + c1.eofb = ui % POW2TO11; + c1 = admissible_eos_from_eofbepos(c1); + admissible_ee_aux[ui] = c1; + } + + 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_pos(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[uf_mirror] = uf_mirror; + inverse_trans_aux[ur_mirror] = ur_mirror; + inverse_trans_aux[ul_mirror] = ul_mirror; + inverse_trans_aux[ub_mirror] = ub_mirror; + + inverse_trans_aux[df_mirror] = df_mirror; + inverse_trans_aux[dr_mirror] = dl_mirror; + inverse_trans_aux[dl_mirror] = dr_mirror; + inverse_trans_aux[db_mirror] = db_mirror; + + inverse_trans_aux[rf_mirror] = rf_mirror; + inverse_trans_aux[rd_mirror] = br_mirror; + inverse_trans_aux[rb_mirror] = lb_mirror; + inverse_trans_aux[ru_mirror] = fl_mirror; + + inverse_trans_aux[lf_mirror] = lf_mirror; + inverse_trans_aux[ld_mirror] = bl_mirror; + inverse_trans_aux[lb_mirror] = rb_mirror; + inverse_trans_aux[lu_mirror] = fr_mirror; + + inverse_trans_aux[fu_mirror] = fu_mirror; + inverse_trans_aux[fr_mirror] = lu_mirror; + inverse_trans_aux[fd_mirror] = bu_mirror; + inverse_trans_aux[fl_mirror] = ru_mirror; + + inverse_trans_aux[bu_mirror] = fd_mirror; + inverse_trans_aux[br_mirror] = rd_mirror; + inverse_trans_aux[bd_mirror] = bd_mirror; + inverse_trans_aux[bl_mirror] = ld_mirror; +} + +/* + * There is certainly a bette way to do this, but for now I just use + * a "graph coloring" algorithm to compute the left cosets, and I compose + * with every possible cp to get the right cosets (it is possible that I am + * mixing up left and right). + * + * For doing it better "Mathematically", we need 3 things: + * - Checking that cp separates the orbits (UFR,UBL,DFL,DBR) and the other + * This is easy and it is done in the commented function cphtr_cp(). + * - Check that there is no ep/cp parity + * - Check that we are not in the "3c" case; this is the part I don't + * know how to do. + */ +static void +init_cphtr_cosets() +{ + unsigned int i; + int c = 0, d = 0; + + for (i = 0; i < FACTORIAL8; i++) { + cphtr_left_cosets[i] = -1; + cphtr_right_cosets[i] = -1; + } + + /* First we compute left cosets with a bfs */ + for (i = 0; i < FACTORIAL8; i++) + if (cphtr_left_cosets[i] == -1) + init_cphtr_left_cosets_bfs(i, c++); + + /* Then we compute right cosets using compose() */ + for (i = 0; i < FACTORIAL8; i++) + if (cphtr_right_cosets[i] == -1) + init_cphtr_right_cosets_color(i, d++); +} + +static void +init_cphtr_left_cosets_bfs(int i, int c) +{ + int j, jj, k, next[FACTORIAL8], next2[FACTORIAL8], n, n2; + Move moves[6] = {U2, D2, R2, L2, F2, B2}; + + n = 1; + next[0] = i; + cphtr_left_cosets[i] = c; + + while (n != 0) { + for (j = 0, n2 = 0; j < n; j++) { + for (k = 0; k < 6; k++) { + jj = cp_mtable[moves[k]][next[j]]; + if (cphtr_left_cosets[jj] == -1) { + cphtr_left_cosets[jj] = c; + next2[n2++] = jj; + } + } + } + + for (j = 0; j < n2; j++) + next[j] = next2[j]; + n = n2; + } +} + +static void +init_cphtr_right_cosets_color(int i, int d) +{ + int cp; + unsigned int j; + + cphtr_right_rep[d] = i; + for (j = 0; j < FACTORIAL8; j++) { + if (cphtr_left_cosets[j] == 0) { + /* TODO: use antindexer, it's nicer */ + cp = compose((Cube){.cp = i}, (Cube){.cp = j}).cp; + cphtr_right_cosets[cp] = d; + } + } +} + +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; + unsigned int 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_symdata() +{ + int i; + + for (i = 0; i < n_all_symdata; i++) + gensym(all_sd[i]); +} + +static void +init_trans() { + Cube aux, cube, mirr, c[3]; + CubeArray epcp; + int i, eparr[12], eoarr[12], cparr[8], coarr[8]; + unsigned int ui; + Move mi, move; + Trans m; + + /* Compute sources */ + for (i = 0; i < NTRANS; i++) { + cube = apply_alg(rotation_algs[i % NROTATIONS], (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++) { + epcp = (CubeArray){ .ep = eparr, .cp = cparr }; + cube = apply_alg(rotation_algs[m % NROTATIONS], (Cube){0}); + cube_to_arrays(cube, &epcp, pf_epcp); + if (m >= NROTATIONS) { + apply_permutation(ep_mirror, eparr, 12); + apply_permutation(cp_mirror, cparr, 8); + } + + 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 >= NROTATIONS) + 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++) { + aux = apply_trans(m, apply_move(mi, (Cube){0})); + for (move = 0; move < NMOVES; move++) { + cube = apply_move(inverse_move_aux[move], aux); + mirr = apply_trans(uf_mirror, cube); + if (is_solved(cube, false) || + is_solved(mirr, 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? */ + rotation_algs[uf] = new_alg(""); + rotation_algs[ur] = new_alg("y"); + rotation_algs[ub] = new_alg("y2"); + rotation_algs[ul] = new_alg("y3"); + + rotation_algs[df] = new_alg("z2"); + rotation_algs[dr] = new_alg("y z2"); + rotation_algs[db] = new_alg("x2"); + rotation_algs[dl] = new_alg("y3 z2"); + + rotation_algs[rf] = new_alg("z3"); + rotation_algs[rd] = new_alg("z3 y"); + rotation_algs[rb] = new_alg("z3 y2"); + rotation_algs[ru] = new_alg("z3 y3"); + + rotation_algs[lf] = new_alg("z"); + rotation_algs[ld] = new_alg("z y3"); + rotation_algs[lb] = new_alg("z y2"); + rotation_algs[lu] = new_alg("z y"); + + rotation_algs[fu] = new_alg("x y2"); + rotation_algs[fr] = new_alg("x y"); + rotation_algs[fd] = new_alg("x"); + rotation_algs[fl] = new_alg("x y3"); + + rotation_algs[bu] = new_alg("x3"); + rotation_algs[br] = new_alg("x3 y"); + rotation_algs[bd] = new_alg("x3 y2"); + rotation_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) +{ + int aux_epos[3] = { cube.epose, cube.eposs, cube.eposm }; + int aux_eo[3] = { cube.eoud, cube.eorl, cube.eofb }; + int 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); +} + +/*TODO maybe move the next two */ +uint64_t +cphtr(Cube cube) +{ + return cphtr_right_cosets[cube.cp]; +} + +Cube +anti_cphtr(uint64_t ind) +{ + return (Cube) { .cp = cphtr_right_rep[ind] }; +} + +uint64_t +epos_dependent(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 +genptable(PruneData *pd) +{ + Cube cube; + uint64_t j, oldn = 0; + 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->coord->max; j++) + ptable_update(pd, pd->coord->cube(j), 15); + + moveset_to_list(pd->moveset, NULL, dd.sorted_moves); + movelist_to_position(dd.sorted_moves, dd.move_position); + + for (dd.d = 0, pd->n = 0; dd.d < 15 && pd->n < pd->coord->max; dd.d++) { + for (j = 0; j < pd->coord->max; j++) { + cube = pd->coord->cube(j); + if (pd->coord->check(cube)) + genptable_dfs(cube, pd, &dd); + } + fprintf(stderr, "Depth %d done, generated %lu\t(%lu/%lu)\n", + dd.d, pd->n-oldn, pd->n, pd->coord->max); + oldn = pd->n; + } + + if (!write_ptable_file(pd)) + fprintf(stderr, "Error writing ptable file\n"); + + pd->generated = true; +} + +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) +{ + int i; + + if (reorient) { + for (i = 0; i < NROTATIONS; i++) + if (is_solved(apply_alg(rotation_algs[i], cube),false)) + return true; + return false; + } else { + 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, 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; +} + +/* TODO: clean pre_trans or put it back */ +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(cube)) { + fprintf(stderr, "Cube not ready for solving step\n"); + return sols; + } + + moveset_to_list(step.moveset, step.estimate, 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(cube, step, opts, &dd); + } + +/* + for (node = sols->first; node != NULL; node = node->next) + transform_alg(inverse_trans(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, inverse_move(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->coord->max; i++) + a[ptableval(pd, pd->coord->cube(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->coord->max + 1) / 2; +} + +int +ptableval(PruneData *pd, Cube cube) +{ + uint64_t ind = pd->coord->index(cube); + + return (ind % 2) ? pd->ptable[ind/2] / 16 : pd->ptable[ind/2] % 16; +} + + +Alg * +rotation_alg(Trans i) +{ + return rotation_algs[i % NROTATIONS]; +} + +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_cphtr_cosets(); + init_trans_aux(); + init_trans(); + init_symdata(); +} + diff --git a/old/2021-07-02-genptable-dfs/cube.h b/old/2021-07-02-genptable-dfs/cube.h new file mode 100644 index 0000000..ffbcd86 --- /dev/null +++ b/old/2021-07-02-genptable-dfs/cube.h @@ -0,0 +1,90 @@ +#ifndef CUBE_H +#define CUBE_H + +#include +#include +#include +#include +#include +#include +#include +#include + +#include "macros.h" +#include "cubetypes.h" + +extern Coordinate coord_eofb; +extern Coordinate coord_eofbepos; +extern Coordinate coord_coud; +extern Coordinate coord_corners; +extern Coordinate coord_cornershtr; +extern Coordinate coord_drud; +extern Coordinate coord_coud_sym16; +extern Coordinate coord_eofbepos_sym16; +extern Coordinate coord_drud_sym16; +extern Coordinate coord_khuge; + +Cube apply_alg(Alg *alg, Cube cube); +Cube apply_move(Move m, Cube cube); +Cube apply_trans(Trans t, Cube cube); +bool block_solved(Cube cube, Block); +Cube compose(Cube c2, Cube c1); /* Use c2 as an alg on c1 */ +uint64_t cphtr(Cube cube); /* TODO: rename (something with cosets) */ +Cube anti_cphtr(uint64_t ind); /*TODO also this */ +uint64_t epos_dependent(Cube cube); /* TODO: rename and turn into an indexer */ +bool equal(Cube c1, Cube c2); +Cube inverse_cube(Cube cube); +Move inverse_move(Move m); +Trans inverse_trans(Trans t); +bool is_admissible(Cube cube); +bool is_solved(Cube cube, bool reorient); +bool is_solved_center(Cube cube, Center c); +bool is_solved_corner(Cube cube, Corner c); +bool is_solved_edge(Cube cube, Edge e); +void print_cube(Cube cube); +Cube random_cube(); +AlgList * solve(Cube cube, Step step, SolveOptions *opts); +Center what_center_at(Cube cube, Center c); +Corner what_corner_at(Cube cube, Corner c); +Edge what_edge_at(Cube cube, Edge e); +int what_orientation_corner(int co, Corner c); +int what_orientation_edge(int eo, Edge e); +Center where_is_center(Cube cube, Center c); +Corner where_is_corner(Cube cube, Corner c); +Edge where_is_edge(Cube cube, Edge e); + +bool check_centers(Cube cube); +bool check_corners(Cube cube); +bool check_cornershtr(Cube cube); +bool check_coud(Cube cube); +bool check_drud(Cube cube); +bool check_eofb(Cube cube); +bool check_eofbepos(Cube cube); +bool check_epose(Cube cube); +bool check_ep(Cube cube); +bool check_khuge(Cube cube); +bool check_nothing(Cube cube); + +bool moveset_HTM(Move m); +bool moveset_URF(Move m); + +Move base_move(Move m); +void free_alg(Alg *alg); +void free_alglist(AlgList *l); +Alg * inverse_alg(Alg *alg); +Alg * new_alg(char *str); +Alg * on_inverse(Alg *alg); +void print_alg(Alg *alg, bool l); +void print_alglist(AlgList *al, bool l); +Alg * rotation_alg(Trans i); +void transform_alg(Trans t, Alg *alg); + +void genptable(PruneData *pd); +void print_ptable(PruneData *pd); +uint64_t ptablesize(PruneData *pd); +int ptableval(PruneData *pd, Cube cube); + +void init(); + +#endif + diff --git a/old/2021-07-02-genptable-dfs/cubetypes.h b/old/2021-07-02-genptable-dfs/cubetypes.h new file mode 100644 index 0000000..a324985 --- /dev/null +++ b/old/2021-07-02-genptable-dfs/cubetypes.h @@ -0,0 +1,250 @@ +#ifndef CUBETYPES_H +#define CUBETYPES_H + +/* Typedefs ******************************************************************/ + +typedef enum center Center; +typedef enum corner Corner; +typedef enum edge Edge; +typedef enum move Move; +typedef enum trans Trans; + +typedef struct alg Alg; +typedef struct alglist AlgList; +typedef struct alglistnode AlgListNode; +typedef struct block Block; +typedef struct coordinate Coordinate; +typedef struct cube Cube; +typedef struct cubearray CubeArray; +typedef struct cubetarget CubeTarget; +typedef struct dfsdata DfsData; +typedef struct piecefilter PieceFilter; +typedef struct prunedata PruneData; +typedef struct solveoptions SolveOptions; +typedef struct step Step; +typedef struct symdata SymData; + +typedef Cube (*AntiIndexer) (uint64_t); +typedef bool (*Checker) (Cube); +typedef int (*Estimator) (CubeTarget); +typedef uint64_t (*Indexer) (Cube); +typedef bool (*Moveset) (Move); + + +/* Enums *********************************************************************/ + +enum +center +{ + U_center, D_center, + R_center, L_center, + F_center, B_center +}; + +enum +corner +{ + UFR, UFL, UBL, UBR, + DFR, DFL, DBL, DBR +}; + +enum +edge +{ + UF, UL, UB, UR, + DF, DL, DB, DR, + FR, FL, BL, BR +}; + +enum +move +{ + NULLMOVE, + U, U2, U3, D, D2, D3, + R, R2, R3, L, L2, L3, + F, F2, F3, B, B2, B3, + Uw, Uw2, Uw3, Dw, Dw2, Dw3, + Rw, Rw2, Rw3, Lw, Lw2, Lw3, + Fw, Fw2, Fw3, Bw, Bw2, Bw3, + M, M2, M3, + S, S2, S3, + E, E2, E3, + x, x2, x3, + y, y2, y3, + z, z2, z3, +}; + +enum +trans +{ + uf, ur, ub, ul, + df, dr, db, dl, + rf, rd, rb, ru, + lf, ld, lb, lu, + fu, fr, fd, fl, + bu, br, bd, bl, + uf_mirror, ur_mirror, ub_mirror, ul_mirror, + df_mirror, dr_mirror, db_mirror, dl_mirror, + rf_mirror, rd_mirror, rb_mirror, ru_mirror, + lf_mirror, ld_mirror, lb_mirror, lu_mirror, + fu_mirror, fr_mirror, fd_mirror, fl_mirror, + bu_mirror, br_mirror, bd_mirror, bl_mirror, +}; + + +/* Structs *******************************************************************/ + +struct +alg +{ + Move * move; + bool * inv; + int len; + int allocated; +}; + +struct +alglist +{ + AlgListNode * first; + AlgListNode * last; + int len; +}; + +struct +alglistnode +{ + Alg * alg; + AlgListNode * next; +}; + +struct +block +{ + bool edge[12]; + bool corner[8]; + bool center[6]; +}; + +struct +coordinate +{ + Indexer index; + AntiIndexer cube; + Checker check; + uint64_t max; +}; + +struct +cube +{ + int epose; + int eposs; + int eposm; + int eofb; + int eorl; + int eoud; + int cp; + int coud; + int cofb; + int corl; + int cpos; +}; + +struct +cubearray +{ + int * ep; + int * eofb; + int * eorl; + int * eoud; + int * cp; + int * coud; + int * corl; + int * cofb; + int * cpos; +}; + +struct +cubetarget +{ + Cube cube; + int target; +}; + +struct +dfsdata +{ + int d; + int m; + int lb; + bool niss; + Move last1; + Move last2; + AlgList * sols; + Alg * current_alg; + Move sorted_moves[NMOVES]; + int move_position[NMOVES]; +}; + +struct +piecefilter +{ + bool epose; + bool eposs; + bool eposm; + bool eofb; + bool eorl; + bool eoud; + bool cp; + bool coud; + bool cofb; + bool corl; + bool cpos; +}; + +struct +prunedata +{ + char * filename; + uint8_t * ptable; + bool generated; + uint64_t n; + Coordinate * coord; + Moveset moveset; +}; + +struct +solveoptions +{ + int min_moves; + int max_moves; + int max_solutions; + bool optimal_only; + bool can_niss; + bool feedback; +}; + +struct +step +{ + Estimator estimate; + Checker ready; + Moveset moveset; +}; + +struct +symdata +{ + char * filename; + bool generated; + Coordinate * coord; + Coordinate * sym_coord; + int ntrans; + Trans * trans; + uint64_t * class; + Cube * rep; + Trans * transtorep; +}; + +#endif diff --git a/old/2021-07-02-genptable-dfs/macros.h b/old/2021-07-02-genptable-dfs/macros.h new file mode 100644 index 0000000..af3bca1 --- /dev/null +++ b/old/2021-07-02-genptable-dfs/macros.h @@ -0,0 +1,23 @@ +#ifndef MACROS_H +#define MACROS_H + +#define POW2TO6 64ULL +#define POW2TO11 2048ULL +#define POW2TO12 4096ULL +#define POW3TO7 2187ULL +#define POW3TO8 6561ULL +#define FACTORIAL4 24ULL +#define FACTORIAL6 720ULL +#define FACTORIAL7 5040ULL +#define FACTORIAL8 40320ULL +#define FACTORIAL12 479001600ULL +#define BINOM12ON4 495ULL +#define BINOM8ON4 70ULL +#define MIN(a,b) (((a) < (b)) ? (a) : (b)) +#define MAX(a,b) (((a) > (b)) ? (a) : (b)) + +#define NMOVES (z3+1) +#define NTRANS 48 +#define NROTATIONS 24 + +#endif diff --git a/old/2021-07-02-genptable-dfs/main.c b/old/2021-07-02-genptable-dfs/main.c new file mode 100644 index 0000000..1ebd917 --- /dev/null +++ b/old/2021-07-02-genptable-dfs/main.c @@ -0,0 +1,80 @@ +#include +#include "cube.h" +#include "steps.h" + +int main() { + Alg *algo; + AlgList *sols; + Cube cube; + SolveOptions opts; + char line[1000]; + int i, ns = 2; +/* Move m;*/ +/* int nrand = 10000, sum1, sum2, sum3;*/ + + Step *stps[20] = {&drud_HTM, &optimal_HTM}; + char sss[30][30] = {"DR on UD", "Optimal solve"}; + + opts = (SolveOptions) { + .min_moves = 0, + .max_moves = 20, + .optimal_only = true, + .max_solutions = 1, + .can_niss = false, + .feedback = true, + }; + + init(); + +/* + srand(time(NULL)); + sum1 = 0; + sum2 = 0; + sum3 = 0; + for (i = 0; i < nrand; i++) { + cube = random_cube(); + sum1 += drud_HTM.check(cube, 20); + sum2 += optimal_HTM.check(cube, 20); + sum3 += cornershtreofb_HTM.check(cube, 20); + } + printf("Average drud pruning: %lf\n", ((double)sum1) / ((double) nrand)); + printf("Average corners htr pruning: %lf\n", ((double)sum2) / ((double) nrand)); + printf("Average corners htr + eofb pruning: %lf\n", ((double)sum3) / ((double) nrand)); +*/ + +/* + for (m = U; m <= B3; m++) { + printf("Class eofbepos after %d: ", m); + printf("%lu\n", coord_khuge.index(apply_move(m,(Cube){0}))); + } +*/ + + printf("Welcome to nissy 2.0! Insert a scramble:\n"); + + if (fgets(line, 1000, stdin) != NULL) { + algo = new_alg(line); + cube = apply_alg(algo, (Cube){0}); + + print_alg(inverse_alg(algo), false); +/* + printf("After rb_mirror:\n"); + cube = apply_trans(rb_mirror, cube); + print_cube(cube); + printf("Going back:\n"); + cube = apply_trans(inverse_trans(rb_mirror), cube); +*/ + + print_cube(cube); + + for (i = 0; i < ns; i++) { + sols = solve(cube, *stps[i], &opts); + printf("%s: %d solutions found:\n", sss[i], sols->len); + print_alglist(sols, true); + free_alglist(sols); + } + free_alg(algo); + } + + return 0; +} + diff --git a/old/2021-07-02-genptable-dfs/steps.c b/old/2021-07-02-genptable-dfs/steps.c new file mode 100644 index 0000000..91e7f00 --- /dev/null +++ b/old/2021-07-02-genptable-dfs/steps.c @@ -0,0 +1,307 @@ +#include "steps.h" + +/* Standard checkers (return lower bound) ************************************/ + +static int estimate_eofb_HTM(CubeTarget ct); +static int estimate_coud_HTM(CubeTarget ct); +static int estimate_coud_URF(CubeTarget ct); +static int estimate_corners_HTM(CubeTarget ct); +static int estimate_cornershtr_HTM(CubeTarget ct); +static int estimate_corners_URF(CubeTarget ct); +static int estimate_cornershtr_URF(CubeTarget ct); +static int estimate_drud_HTM(CubeTarget ct); +static int estimate_optimal_HTM(CubeTarget ct); + +/* Steps *********************************************************************/ + +Step +eofb_HTM = { + .estimate = estimate_eofb_HTM, + .ready = check_centers, + .moveset = moveset_HTM +}; + +Step +coud_HTM = { + .estimate = estimate_coud_HTM, + .ready = check_centers, + .moveset = moveset_HTM +}; + +Step +coud_URF = { + .estimate = estimate_coud_URF, + .ready = check_nothing, + .moveset = moveset_URF +}; + +Step +corners_HTM = { + .estimate = estimate_corners_HTM, + .ready = check_centers, + .moveset = moveset_HTM +}; + +Step +cornershtr_HTM = { + .estimate = estimate_cornershtr_HTM, + .ready = check_centers, + .moveset = moveset_HTM +}; + +Step +cornershtr_URF = { + .estimate = estimate_cornershtr_URF, + .ready = check_nothing, + .moveset = moveset_URF +}; + +Step +corners_URF = { + .estimate = estimate_corners_URF, + .ready = check_nothing, + .moveset = moveset_URF +}; + +Step +drud_HTM = { + .estimate = estimate_drud_HTM, + .ready = check_centers, + .moveset = moveset_HTM +}; + +Step +optimal_HTM = { + .estimate = estimate_optimal_HTM, + .ready = check_centers, + .moveset = moveset_HTM +}; + + +/* Pruning tables ************************************************************/ + +PruneData +pd_eofb_HTM = { + .filename = "ptable_eofb_HTM", + .coord = &coord_eofb, + .moveset = moveset_HTM +}; + +PruneData +pd_coud_HTM = { + .filename = "ptable_coud_HTM", + .coord = &coord_coud, + .moveset = moveset_HTM +}; + +PruneData +pd_cornershtr_HTM = { + .filename = "ptable_cornershtr_withcosets_HTM", + .coord = &coord_cornershtr, + .moveset = moveset_HTM +}; + +PruneData +pd_corners_HTM = { + .filename = "ptable_corners_HTM", + .coord = &coord_corners, + .moveset = moveset_HTM +}; + +PruneData +pd_drud_HTM = { + .filename = "ptable_drud_HTM", + .coord = &coord_drud, + .moveset = moveset_HTM +}; + +PruneData +pd_drud_sym16_HTM = { + .filename = "ptable_drud_sym16_HTM", + .coord = &coord_drud_sym16, + .moveset = moveset_HTM, +}; + +PruneData +pd_khuge_HTM = { + .filename = "ptable_khuge_HTM", + .coord = &coord_khuge, + .moveset = moveset_HTM +}; + + +/* Standard checkers (return lower bound) ************************************/ + +static int +estimate_eofb_HTM(CubeTarget ct) +{ + if (!pd_eofb_HTM.generated) + genptable(&pd_eofb_HTM); + + return ptableval(&pd_eofb_HTM, ct.cube); +} + +static int +estimate_coud_HTM(CubeTarget ct) +{ + if (!pd_coud_HTM.generated) + genptable(&pd_coud_HTM); + + return ptableval(&pd_coud_HTM, ct.cube); +} + +static int +estimate_coud_URF(CubeTarget ct) +{ + /* TODO: I can improve this by checking first the orientation of + * the corner in DBL and use that as a reference */ + + CubeTarget ct2 = {.cube = apply_move(z, ct.cube), .target = ct.target}; + CubeTarget ct3 = {.cube = apply_move(x, ct.cube), .target = ct.target}; + + int ud = estimate_coud_HTM(ct); + int rl = estimate_coud_HTM(ct2); + int fb = estimate_coud_HTM(ct3); + + return MIN(ud, MIN(rl, fb)); +} + +static int +estimate_corners_HTM(CubeTarget ct) +{ + if (!pd_corners_HTM.generated) + genptable(&pd_corners_HTM); + + return ptableval(&pd_corners_HTM, ct.cube); +} + +static int +estimate_cornershtr_HTM(CubeTarget ct) +{ + if (!pd_cornershtr_HTM.generated) + genptable(&pd_cornershtr_HTM); + + return ptableval(&pd_cornershtr_HTM, ct.cube); +} + +static int +estimate_cornershtr_URF(CubeTarget ct) +{ + /* TODO: I can improve this by checking first the corner in DBL + * and use that as a reference */ + + int c, ret = 15; + Trans i; + + for (i = 0; i < NROTATIONS; i++) { + ct.cube = apply_alg(rotation_alg(i), ct.cube); + c = estimate_cornershtr_HTM(ct); + ret = MIN(ret, c); + } + + return ret; +} + +static int +estimate_corners_URF(CubeTarget ct) +{ + /* TODO: I can improve this by checking first the corner in DBL + * and use that as a reference */ + + int c, ret = 15; + Trans i; + + for (i = 0; i < NROTATIONS; i++) { + ct.cube = apply_alg(rotation_alg(i), ct.cube); + c = estimate_corners_HTM(ct); + ret = MIN(ret, c); + } + + return ret; +} + +static int +estimate_drud_HTM(CubeTarget ct) +{ +/* + if (!pd_drud_HTM.generated) + genptable(&pd_drud_HTM); + + return ptableval(&pd_drud_HTM, ct.cube); +*/ + + if (!pd_drud_sym16_HTM.generated) + genptable(&pd_drud_sym16_HTM); + + return ptableval(&pd_drud_sym16_HTM, ct.cube); +} + +/* TODO: if lucky, remove this */ +/* +static int +estimate_optimal_HTM(CubeTarget ct) +{ + static Trans t1 = { .rot = rf, .mirror = false }; + static Trans t2 = { .rot = bd, .mirror = false }; + int dr1, dr2, dr3, cor, ret; + Cube cube = ct.cube; + + dr1 = estimate_drud_HTM(ct); + cor = estimate_corners_HTM(ct); + ret = MAX(dr1, cor); + + if (ret > ct.target) + return ret; + + ct.cube = apply_trans(t1, cube); + dr2 = estimate_drud_HTM(ct); + ret = MAX(ret, dr2); + + if (ret > ct.target) + return ret; + + ct.cube = apply_trans(t2, cube); + dr3 = estimate_drud_HTM(ct); + + if (dr1 == dr2 && dr2 == dr3 && dr1 != 0) + dr3++; + + ret = MAX(ret, dr3); + + if (ret == 0) + return check_ep(cube) ? 0 : 6; + + return ret; +} +*/ + +static int +estimate_optimal_HTM(CubeTarget ct) +{ + static Trans t2 = rf, t3 = bd; + + int dr1, dr2, dr3, cor, ret; + Cube cube = ct.cube; + + if (!pd_khuge_HTM.generated) + genptable(&pd_khuge_HTM); + + dr1 = ptableval(&pd_khuge_HTM, cube); + cor = estimate_corners_HTM(ct); + ret = MAX(dr1, cor); + + if (ret > ct.target) + return ret; + + cube = apply_trans(t2, ct.cube); + dr2 = ptableval(&pd_khuge_HTM, cube); + ret = MAX(ret, dr2); + + if (ret > ct.target) + return ret; + + cube = apply_trans(t3, ct.cube); + dr3 = ptableval(&pd_khuge_HTM, cube); + + return MAX(ret, dr3); +} diff --git a/old/2021-07-02-genptable-dfs/steps.h b/old/2021-07-02-genptable-dfs/steps.h new file mode 100644 index 0000000..81ae11c --- /dev/null +++ b/old/2021-07-02-genptable-dfs/steps.h @@ -0,0 +1,24 @@ +#ifndef STEPS_H +#define STEPS_H + +#include "cube.h" + +extern Step eofb_HTM; +extern Step coud_HTM; +extern Step coud_URF; +extern Step corners_HTM; +extern Step cornershtr_HTM; +extern Step corners_URF; +extern Step cornershtr_URF; +extern Step drud_HTM; +extern Step optimal_HTM; + +extern PruneData pd_eofb_HTM; +extern PruneData pd_coud_HTM; +extern PruneData pd_corners_HTM; +extern PruneData pd_cornershtr_HTM; +extern PruneData pd_cornershtreofb_HTM; +extern PruneData pd_drud_HTM; +extern PruneData pd_khuge_HTM; + +#endif -- cgit v1.3