From 3568412f8f230774d0d11d7ed1c897424f95d3ef Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 11 Nov 2021 21:37:34 +0100 Subject: Rewritten from scratch. Welocme nissy 2.0! --- old/2021-06-02-cleanedup/cube.c | 2010 ++++++++++++++++++++++++++++++++++++++ old/2021-06-02-cleanedup/cube.h | 179 ++++ old/2021-06-02-cleanedup/main.c | 35 + old/2021-06-02-cleanedup/steps.h | 22 + 4 files changed, 2246 insertions(+) create mode 100644 old/2021-06-02-cleanedup/cube.c create mode 100644 old/2021-06-02-cleanedup/cube.h create mode 100644 old/2021-06-02-cleanedup/main.c create mode 100644 old/2021-06-02-cleanedup/steps.h (limited to 'old/2021-06-02-cleanedup') diff --git a/old/2021-06-02-cleanedup/cube.c b/old/2021-06-02-cleanedup/cube.c new file mode 100644 index 0000000..bb86143 --- /dev/null +++ b/old/2021-06-02-cleanedup/cube.c @@ -0,0 +1,2010 @@ +#include "cube.h" + +/* Constants and macros *****************************************************/ + +#define pow2to11 2048 +#define pow2to12 4096 +#define pow3to7 2187 +#define pow3to8 6561 +#define pow12to4 20736 +#define factorial4 24 +#define factorial6 720 +#define factorial8 40320 +#define factorial12 479001600 +#define binom12on4 495 +#define binom8on4 70 + +#define BASEALGLEN 50 +#define NMOVES (z3+1) +#define NTRANS (mirror+1) +#define NROTATIONS (NTRANS-1) + +#define min(a,b) (((a) < (b)) ? (a) : (b)) +#define max(a,b) (((a) > (b)) ? (a) : (b)) + +/* Local types ***************************************************************/ + +typedef struct cubearray CubeArray; +typedef struct dfsdata DfsData; +typedef struct piecefilter PieceFilter; + +struct +cubearray +{ + int *ep; + int *eofb; + int *eorl; + int *eoud; + int *cp; + int *coud; + int *corl; + int *cofb; + int *cpos; +}; + +struct +dfsdata +{ + int d; + int m; + bool niss; + Move last1; + Move last2; + AlgList *sols; + Alg current_alg; +}; + +struct +piecefilter +{ + bool epose; + bool eposs; + bool eposm; + bool eofb; + bool eorl; + bool eoud; + bool cp; + bool coud; + bool cofb; + bool corl; + bool cpos; +}; + +/* Local functions **********************************************************/ + +static Cube admissible_ep(Cube cube, PieceFilter f); +static CubeArray * alloc_cubearray(CubeArray *arr, PieceFilter f); +static void append_alg(AlgList *l, Alg alg); +static void append_move(Alg alg, NissMove m); +static Cube apply_alg_filtered(Alg alg, Cube cube, PieceFilter f); +static void apply_permutation(int *perm, int *set, int n); +static Cube apply_move_cubearray(Move m, Cube cube, PieceFilter f); +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 int digit_array_to_int(int *a, int n, int b); +static int edge_slice(Edge e); /* E=0, S=1, M=2 */ +static uint16_t epos_from_arrays(int *epos, int *ep); +static int factorial(int n); +static void free_alglist(AlgList *l); +static void free_cubearray(CubeArray *arr, PieceFilter f); +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_moves(); +static void init_trans(); +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 void intarrcopy(int *src, int *dst, int n); +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 Move * moveset_to_movelist(bool *moveset, Step step); +static AlgList * new_alglist(); +static int perm_sign(int a[], int n); +static int perm_to_index(int *a, int n); +static int powint(int a, int b); +static bool read_rtables_file(); +static bool read_ttables_file(); +static bool realloc_alg(Alg alg, int n); +static Cube rotate_via_compose(Trans r, Cube c, PieceFilter f); +static void solve_dfs(Cube c, Step s, SolveOptions opts, DfsData dd); +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_rtables_file(); +static bool write_ttables_file(); + +/* Aux tables ****************************************************************/ + +bool commute[NMOVES][NMOVES]; +bool possible_next[NMOVES][NMOVES][NMOVES]; +Move inverse_move_aux[NMOVES]; +Trans inverse_trans_aux[NTRANS]; + +/* Some utility constants ****************************************************/ + +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 int epe_solved[4] = { FR, FL, BL, BR }; +static int eps_solved[4] = { UL, UR, DL, DR }; +static int epm_solved[4] = { UF, UB, DF, DB }; + +static int ep_mirror[12] = { UF, UR, UB, UL, DF, DR, DB, DL, FL, FR, BR, BL }; +static int cp_mirror[8] = { UFL, UFR, UBR, UBL, DFL, DFR, DBR, DBL }; +static int cpos_mirror[6] = { + U_center, D_center, + L_center, R_center, + F_center, B_center +}; + +static long unsigned int me[12] = { + factorial12/factorial8, + factorial12/factorial8, + factorial12/factorial8, + pow2to11, + pow2to11, + pow2to11, + factorial8, + pow3to7, + pow3to7, + pow3to7, + factorial6, + NMOVES +}; + +static PieceFilter pf_all = { + true, true, true, true, true, true, true, true, true, true, true +}; +static PieceFilter pf_epcp = { + .epose = true, .eposs = true, .eposm = true, .cp = true +}; +static PieceFilter pf_cpos = { .cpos = true }; +static PieceFilter pf_cp = { .cp = true }; +static PieceFilter pf_ep = { .epose = true, .eposs = true, .eposm = true }; +static PieceFilter pf_e = { .epose = true }; +static PieceFilter pf_s = { .eposs = true }; +static PieceFilter pf_m = { .eposm = true }; +static PieceFilter pf_eo = { .eofb = true, .eorl = true, .eoud = true }; +static PieceFilter pf_co = { .coud = true, .cofb = true, .corl = true }; + +/* Strings for moves and pieces **********************************************/ + +char move_string[NMOVES][5] = { + "-", + "U", "U2", "U\'", "D", "D2", "D\'", + "R", "R2", "R\'", "L", "L2", "L\'", + "F", "F2", "F\'", "B", "B2", "B\'", + "Uw", "Uw2", "Uw\'", "Dw", "Dw2", "Dw\'", + "Rw", "Rw2", "Rw\'", "Lw", "Lw2", "Lw\'", + "Fw", "Fw2", "Fw\'", "Bw", "Bw2", "Bw\'", + "M", "M2", "M\'", + "S", "S2", "S\'", + "E", "E2", "E\'", + "x", "x2", "x\'", + "y", "y2", "y\'", + "z", "z2", "z\'" +}; +char edge_string[12][5] = { + "UF", "UL", "UB", "UR", + "DF", "DL", "DB", "DR", + "FR", "FL", "BL", "BR" +}; +char corner_string[8][5] = { + "UFR", "UFL", "UBL", "UBR", + "DFR", "DFL", "DBL", "DBR" +}; +char center_string[6][5] = { + "U", "D", + "R", "L", + "F", "B" +}; + +/* Transition tables for transformations and moves ***************************/ + +uint16_t epose_rtable[NTRANS][factorial12/factorial8]; +uint16_t eposs_rtable[NTRANS][factorial12/factorial8]; +uint16_t eposm_rtable[NTRANS][factorial12/factorial8]; +uint16_t eo_rtable[NTRANS][pow2to11]; +uint16_t cp_rtable[NTRANS][factorial8]; +uint16_t co_rtable[NTRANS][pow3to7]; +uint16_t cpos_rtable[NTRANS][factorial6]; +Move moves_rtable[NTRANS][NMOVES]; + +uint16_t epose_ttable[NMOVES][factorial12/factorial8]; +uint16_t eposs_ttable[NMOVES][factorial12/factorial8]; +uint16_t eposm_ttable[NMOVES][factorial12/factorial8]; +uint16_t eofb_ttable[NMOVES][pow2to11]; +uint16_t eorl_ttable[NMOVES][pow2to11]; +uint16_t eoud_ttable[NMOVES][pow2to11]; +uint16_t cp_ttable[NMOVES][factorial8]; +uint16_t coud_ttable[NMOVES][pow3to7]; +uint16_t cofb_ttable[NMOVES][pow3to7]; +uint16_t corl_ttable[NMOVES][pow3to7]; +uint16_t cpos_ttable[NMOVES][factorial6]; + +/* Used to compute the full transition tables for moves and transformations **/ + +int epose_source[NTRANS]; /* 0 = epose, 1 = eposs, 2 = eposm */ +int eposs_source[NTRANS]; +int eposm_source[NTRANS]; +int eofb_source[NTRANS]; /* 0 = eoud, 1 = eorl, 2 = eofb */ +int eorl_source[NTRANS]; +int eoud_source[NTRANS]; +int coud_source[NTRANS]; /* 0 = coud, 1 = corl, 2 = cofb */ +int cofb_source[NTRANS]; +int corl_source[NTRANS]; + +NissMove rotation_niss[NTRANS][6]; +NissMove rotation_algs[NROTATIONS][3] = { + { { .m = NULLMOVE }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = y }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = y2 }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = y3 }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = z2 }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = y }, { .m = z2 }, { .m = NULLMOVE } }, + { { .m = x2 }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = y3 }, { .m = z2 }, { .m = NULLMOVE } }, + { { .m = z3 }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = z3 }, { .m = y }, { .m = NULLMOVE } }, + { { .m = z3 }, { .m = y2 }, { .m = NULLMOVE } }, + { { .m = z3 }, { .m = y3 }, { .m = NULLMOVE } }, + { { .m = z }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = z }, { .m = y3 }, { .m = NULLMOVE } }, + { { .m = z }, { .m = y2 }, { .m = NULLMOVE } }, + { { .m = z }, { .m = y }, { .m = NULLMOVE } }, + { { .m = x }, { .m = y2 }, { .m = NULLMOVE } }, + { { .m = x }, { .m = y }, { .m = NULLMOVE } }, + { { .m = x }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = x }, { .m = y3 }, { .m = NULLMOVE } }, + { { .m = x3 }, { .m = NULLMOVE }, { .m = NULLMOVE } }, + { { .m = x3 }, { .m = y }, { .m = NULLMOVE } }, + { { .m = x3 }, { .m = y2 }, { .m = NULLMOVE } }, + { { .m = x3 }, { .m = y3 }, { .m = NULLMOVE } }, +}; + +/* For each type of pieces only the effects of U, x and y are described */ +int edge_cycle[NMOVES][12] = { + [U] = { UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR }, + [x] = { DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR }, + [y] = { UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL } +}; +int eofb_flipped[NMOVES][12] = { + [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 }, + [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 } +}; +int eorl_flipped[NMOVES][12] = { + [x] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, + [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 } +}; +int eoud_flipped[NMOVES][12] = { + [U] = { [UF] = 1, [UL] = 1, [UB] = 1, [UR] = 1 }, + [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 }, + [y] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } +}; +int corner_cycle[NMOVES][8] = { + [U] = {UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR}, + [x] = {DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR}, + [y] = {UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL} +}; +int coud_flipped[NMOVES][8] = { + [x] = { + [UFR] = 2, [UBR] = 1, [UFL] = 1, [UBL] = 2, + [DBR] = 2, [DFR] = 1, [DBL] = 1, [DFL] = 2 + } +}; +int corl_flipped[NMOVES][8] = { + [U] = { [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2 }, + [y] = { + [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2, + [DFR] = 2, [DBR] = 1, [DBL] = 2, [DFL] = 1 + } +}; +int cofb_flipped[NMOVES][8] = { + [U] = { [UFR] = 2, [UBR] = 1, [UBL] = 2, [UFL] = 1 }, + [x] = { + [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2, + [DFR] = 2, [DBR] = 1, [DBL] = 2, [DFL] = 1 + }, + [y] = { + [UFR] = 2, [UBR] = 1, [UBL] = 2, [UFL] = 1, + [DFR] = 1, [DBR] = 2, [DBL] = 1, [DFL] = 2 + } +}; +int center_cycle[NMOVES][6] = { + [x] = { F_center, B_center, R_center, L_center, D_center, U_center }, + [y] = { U_center, D_center, B_center, F_center, R_center, L_center } +}; + +/* Each move is reduced to a combination of U, x and y using this table */ +Move equiv_moves[NMOVES][14] = { + [U] = { U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [U2] = { U, U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [U3] = { U, U, U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [D] = { x, x, U, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [D2] = { x, x, U, U, x, x, 0, 0, 0, 0, 0, 0, 0, 0 }, + [D3] = { x, x, U, U, U, x, x, 0, 0, 0, 0, 0, 0, 0 }, + [R] = { y, x, U, x, x, x, y, y, y, 0, 0, 0, 0, 0 }, + [R2] = { y, x, U, U, x, x, x, y, y, y, 0, 0, 0, 0 }, + [R3] = { y, x, U, U, U, x, x, x, y, y, y, 0, 0, 0 }, + [L] = { y, y, y, x, U, x, x, x, y, 0, 0, 0, 0, 0 }, + [L2] = { y, y, y, x, U, U, x, x, x, y, 0, 0, 0, 0 }, + [L3] = { y, y, y, x, U, U, U, x, x, x, y, 0, 0, 0 }, + [F] = { x, U, x, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [F2] = { x, U, U, x, x, x, 0, 0, 0, 0, 0, 0, 0, 0 }, + [F3] = { x, U, U, U, x, x, x, 0, 0, 0, 0, 0, 0, 0 }, + [B] = { x, x, x, U, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [B2] = { x, x, x, U, U, x, 0, 0, 0, 0, 0, 0, 0, 0 }, + [B3] = { x, x, x, U, U, U, x, 0, 0, 0, 0, 0, 0, 0 }, + + [Uw] = { x, x, U, x, x, y, 0, 0, 0, 0, 0, 0, 0, 0 }, + [Uw2] = { x, x, U, U, x, x, y, y, 0, 0, 0, 0, 0, 0 }, + [Uw3] = { x, x, U, U, U, x, x, y, y, y, 0, 0, 0, 0 }, + [Dw] = { U, y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [Dw2] = { U, U, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [Dw3] = { U, U, U, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [Rw] = { y, y, y, x, U, x, x, x, y, x, 0, 0, 0, 0 }, + [Rw2] = { y, y, y, x, U, U, x, x, x, y, x, x, 0, 0 }, + [Rw3] = { y, y, y, x, U, U, U, y, x, x, x, y, 0, 0 }, + [Lw] = { y, x, U, x, x, x, y, y, y, x, x, x, 0, 0 }, + [Lw2] = { y, x, U, U, x, x, x, y, y, y, x, x, 0, 0 }, + [Lw3] = { y, x, U, U, U, x, x, x, y, y, y, x, 0, 0 }, + [Fw] = { x, x, x, U, y, y, y, x, 0, 0, 0, 0, 0, 0 }, + [Fw2] = { x, x, x, U, U, y, y, x, 0, 0, 0, 0, 0, 0 }, + [Fw3] = { x, x, x, U, U, U, y, x, 0, 0, 0, 0, 0, 0 }, + [Bw] = { x, U, y, y, y, x, x, x, 0, 0, 0, 0, 0, 0 }, + [Bw2] = { x, U, U, y, y, x, x, x, 0, 0, 0, 0, 0, 0 }, + [Bw3] = { x, U, U, U, y, x, x, x, 0, 0, 0, 0, 0, 0 }, + + [M] = { y, x, U, x, x, U, U, U, y, x, y, y, y, 0 }, + [M2] = { y, x, U, U, x, x, U, U, x, x, x, y, 0, 0 }, + [M3] = { y, x, U, U, U, x, x, U, y, x, x, x, y, 0 }, + [S] = { x, U, U, U, x, x, U, y, y, y, x, 0, 0, 0 }, + [S2] = { x, U, U, x, x, U, U, y, y, x, 0, 0, 0, 0 }, + [S3] = { x, U, x, x, U, U, U, y, x, 0, 0, 0, 0, 0 }, + [E] = { U, x, x, U, U, U, x, x, y, y, y, 0, 0, 0 }, + [E2] = { U, U, x, x, U, U, x, x, y, y, 0, 0, 0, 0 }, + [E3] = { U, U, U, x, x, U, x, x, y, 0, 0, 0, 0, 0 }, + + [x] = { x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [x2] = { x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [x3] = { x, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [y] = { y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [y2] = { y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [y3] = { y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [z] = { y, y, y, x, y, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [z2] = { y, y, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + [z3] = { y, x, y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, +}; + +/* Local functions implementation ********************************************/ + +static Cube +admissible_ep(Cube cube, PieceFilter f) +{ + CubeArray arr; + Cube ret; + bool used[12] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; + int i, j; + + alloc_cubearray(&arr, f); + cube_to_arrays(cube, &arr, f); + + 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 CubeArray * +alloc_cubearray(CubeArray *arr, PieceFilter f) +{ + 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)); + + return arr; +} + +static void +append_alg(AlgList *l, Alg alg) +{ + AlgListNode *node = malloc(sizeof(AlgListNode)); + + node->alg = new_alg(""); + copy_alg(alg, node->alg); + node->next = NULL; + + if (++l->len == 1) + l->first = node; + else + l->last->next = node; + l->last = node; +} + +static void +append_move(Alg alg, NissMove m) +{ + int n = len(alg); + + if (!realloc_alg(alg, n)) + return; + + alg[n] = m; + alg[n+1] = (NissMove) { .m = NULLMOVE }; +} + +static Cube +apply_alg_filtered(Alg alg, Cube cube, PieceFilter f) +{ + Cube ret = {0}; + int i; + + for (i = 0; alg[i].m != NULLMOVE; i++) + if (alg[i].inverse) + ret = apply_move(alg[i].m, ret); + + ret = compose_filtered(cube, inverse_cube(ret), f); + + for (i = 0; alg[i].m != NULLMOVE; i++) + if (!alg[i].inverse) + ret = apply_move(alg[i].m, ret); + + 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]]; + + intarrcopy(aux, set, n); + 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 Cube +arrays_to_cube(CubeArray arr, PieceFilter f) +{ + Cube ret = {0}; + int epose[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; + int eposs[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; + int eposm[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; + int epe[4], eps[4], epm[4]; + int i, ie, is, im, j; + + /* Again, ep is the hardest part */ + if (f.epose) { + for (i = 0, ie = 0; i < 12; i++) { + for (j = 0; j < 4; j++) { + if (arr.ep[i] == epe_solved[j]) { + epe[ie++] = j; + epose[i] = 1; + } + } + } + ret.epose = epos_from_arrays(epose, epe); + } + + if (f.eposs) { + for (i = 0, is = 0; i < 12; i++) { + for (j = 0; j < 4; j++) { + if (arr.ep[i] == eps_solved[j]) { + eps[is++] = j; + eposs[i] = 1; + } + } + } + for (i = 0; i < 4; i++) + swap(&eposs[eps_solved[i]], &eposs[i+8]); + ret.eposs = epos_from_arrays(eposs, eps); + } + + if (f.eposm) { + for (i = 0, im = 0; i < 12; i++) { + for (j = 0; j < 4; j++) { + if (arr.ep[i] == epm_solved[j]) { + epm[im++] = j; + eposm[i] = 1; + } + } + } + for (i = 0; i < 4; i++) + swap(&eposm[epm_solved[i]], &eposm[i+8]); + ret.eposm = epos_from_arrays(eposm, epm); + } + + 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; + Cube ret; + + alloc_cubearray(&arr, f); + cube_to_arrays(c2, &arr, f); + 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 epose[12], eposs[12], eposm[12]; + int epe[4], eps[4], epm[4]; + int i, ie, is, im; + + /* ep is the hardest */ + if (f.epose || f.eposs || f.eposm) + for (i = 0; i < 12; i++) + arr->ep[i] = -1; + + if (f.epose) { + index_to_perm(cube.epose % factorial(4), 4, epe); + index_to_subset(cube.epose / factorial(4), 12, 4, epose); + for (i = 0, ie = 0; i < 12; i++) + if (epose[i]) + arr->ep[i] = epe_solved[epe[ie++]]; + } + + if (f.eposs) { + index_to_perm(cube.eposs % factorial(4), 4, eps); + index_to_subset(cube.eposs / factorial(4), 12, 4, eposs); + for (i = 0; i < 4; i++) + swap(&eposs[eps_solved[i]], &eposs[i+8]); + for (i = 0, is = 0; i < 12; i++) + if (eposs[i]) + arr->ep[i] = eps_solved[eps[is++]]; + } + + if (f.eposm) { + index_to_perm(cube.eposm % factorial(4), 4, epm); + index_to_subset(cube.eposm / factorial(4), 12, 4, eposm); + for (i = 0; i < 4; i++) + swap(&eposm[epm_solved[i]], &eposm[i+8]); + for (i = 0, im = 0; i < 12; i++) + if (eposm[i]) + arr->ep[i] = epm_solved[epm[im++]]; + } + + /* All the others */ + if (f.eofb) + int_to_sum_zero_array(cube.eofb, 2, 12, arr->eofb); + if (f.eorl) + int_to_sum_zero_array(cube.eorl, 2, 12, arr->eorl); + if (f.eoud) + int_to_sum_zero_array(cube.eoud, 2, 12, arr->eoud); + if (f.cp) + index_to_perm(cube.cp, 8, arr->cp); + if (f.coud) + int_to_sum_zero_array(cube.coud, 3, 8, arr->coud); + if (f.corl) + int_to_sum_zero_array(cube.corl, 3, 8, arr->corl); + if (f.cofb) + int_to_sum_zero_array(cube.cofb, 3, 8, arr->cofb); + if (f.cpos) + index_to_perm(cube.cpos, 6, arr->cpos); +} + +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 == FR || e == FL || e == BL || e == BR) + return 0; + if (e == UR || e == UL || e == DR || e == DL) + return 1; + + return 2; +} + +static uint16_t +epos_from_arrays(int *epos, int *ep) +{ + return factorial4 * subset_to_index(epos,12,4) + perm_to_index(ep,4); +} + +static int +factorial(int n) +{ + int i, ret = 1; + + if (n < 0) + return 0; + + for (i = 1; i <= n; i++) + ret *= i; + + return ret; +} + +static void +free_alglist(AlgList *l) +{ + AlgListNode *aux, *i = l->first; + + while (i != NULL) { + aux = i->next; + free(i); + i = aux; + } + free(l); + + return; +} + +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); +} + +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 +init_auxtables() +{ + Cube c1, c2; + int i, j, k; + bool cij, p1, p2; + + 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); + } + } + + for (i = 0; i < NMOVES; i++) { + for (j = 0; j < NMOVES; j++) { + for (k = 0; k < NMOVES; k++) { + p1 = j && (j-(j-1)%3) == (k-(k-1)%3); + p2 = i && (i-(i-1)%3) == (k-(k-1)%3); + cij = commute[i][j]; + possible_next[i][j][k] = !(p1 || (cij && p2)); + } + } + } + + for (i = 0; i < NMOVES; i++) + inverse_move_aux[i] = + i == NULLMOVE ? NULLMOVE : i + 2 - 2*((i-1)%3); + + /* Is there a more elegant way? */ + inverse_trans_aux[uf] = uf; + inverse_trans_aux[ur] = ul; + inverse_trans_aux[ul] = ur; + inverse_trans_aux[ub] = ub; + + inverse_trans_aux[df] = df; + inverse_trans_aux[dr] = dr; + inverse_trans_aux[dl] = dl; + inverse_trans_aux[db] = db; + + inverse_trans_aux[rf] = lf; + inverse_trans_aux[rd] = bl; + inverse_trans_aux[rb] = rb; + inverse_trans_aux[ru] = fr; + + inverse_trans_aux[lf] = rf; + inverse_trans_aux[ld] = br; + inverse_trans_aux[lb] = lb; + inverse_trans_aux[lu] = fl; + + inverse_trans_aux[fu] = fu; + inverse_trans_aux[fr] = ru; + inverse_trans_aux[fd] = bu; + inverse_trans_aux[fl] = lu; + + inverse_trans_aux[bu] = fd; + inverse_trans_aux[br] = ld; + inverse_trans_aux[bd] = bd; + inverse_trans_aux[bl] = rd; + + inverse_trans_aux[mirror] = mirror; +} + +static void +init_moves() { + Cube c; + CubeArray arrs; + int i, j; + uint16_t ui; + Move m; + + /* Generate all move cycles and flips; I do this regardless */ + for (i = 0; i < NMOVES; i++) { + if (i == U || i == x || i == y) + continue; + + c = (Cube){0}; + for (j = 0; equiv_moves[i][j]; j++) + c = apply_move_cubearray(equiv_moves[i][j], c, pf_all); + + 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_ttables_file()) + return; + + fprintf(stderr, "ttables not found, generating them.\n"); + + /* 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_ttable[m][ui] = c.epose; + + c = (Cube){ .eposs = ui }; + c = apply_move_cubearray(m, c, pf_s); + eposs_ttable[m][ui] = c.eposs; + + c = (Cube){ .eposm = ui }; + c = apply_move_cubearray(m, c, pf_m); + eposm_ttable[m][ui] = c.eposm; + } + for (ui = 0; ui < pow2to11; ui++ ) { + c = (Cube){ .eofb = ui }; + c = apply_move_cubearray(m, c, pf_eo); + eofb_ttable[m][ui] = c.eofb; + + c = (Cube){ .eorl = ui }; + c = apply_move_cubearray(m, c, pf_eo); + eorl_ttable[m][ui] = c.eorl; + + c = (Cube){ .eoud = ui }; + c = apply_move_cubearray(m, c, pf_eo); + eoud_ttable[m][ui] = c.eoud; + } + for (ui = 0; ui < pow3to7; ui++) { + c = (Cube){ .coud = ui }; + c = apply_move_cubearray(m, c, pf_co); + coud_ttable[m][ui] = c.coud; + + c = (Cube){ .corl = ui }; + c = apply_move_cubearray(m, c, pf_co); + corl_ttable[m][ui] = c.corl; + + c = (Cube){ .cofb = ui }; + c = apply_move_cubearray(m, c, pf_co); + cofb_ttable[m][ui] = c.cofb; + } + for (ui = 0; ui < factorial8; ui++) { + c = (Cube){ .cp = ui }; + c = apply_move_cubearray(m, c, pf_cp); + cp_ttable[m][ui] = c.cp; + } + for (ui = 0; ui < factorial6; ui++) { + c = (Cube){ .cpos = ui }; + c = apply_move_cubearray(m, c, pf_cpos); + cpos_ttable[m][ui] = c.cpos; + } + } + + if (!write_ttables_file()) + fprintf(stderr, "Error writing ttables\n"); +} + +static void +init_trans() { + Cube aux, cube, c[3]; + CubeArray epcp; + int eparr[12], eoarr[12]; + int cparr[8], coarr[8]; + int i; + bool b1, b2, b3; + uint16_t ui; + Move mi, move; + Trans r, m; + + /* Compute sources */ + for (i = 0; i < NTRANS; i++) { + if (i == mirror) + cube = (Cube){0}; + else + cube = apply_alg(rotation_algs[i], (Cube){0}); + + epose_source[i] = edge_slice(edge_at(cube, FR)); + eposs_source[i] = edge_slice(edge_at(cube, UR)); + eposm_source[i] = edge_slice(edge_at(cube, UF)); + eofb_source[i] = center_at(cube, F_center)/2; + eorl_source[i] = center_at(cube, R_center)/2; + eoud_source[i] = center_at(cube, U_center)/2; + coud_source[i] = center_at(cube, U_center)/2; + cofb_source[i] = center_at(cube, F_center)/2; + corl_source[i] = center_at(cube, R_center)/2; + } + + /* Compute rotation_niss array, necessary for rotate_via_compose */ + for (r = 0; r != mirror; r++) { + concat(rotation_algs[r], rotation_algs[r], rotation_niss[r]); + for (i = len(rotation_algs[r]); rotation_niss[r][i].m; i++) + rotation_niss[r][i].inverse = true; + } + + if (read_rtables_file()) + return; + + fprintf(stderr, "rtables not found, generating them.\n"); + + /* Initialize tables */ + for (m = 0; m < NTRANS; m++) { + if (m == mirror) { + intarrcopy(ep_mirror, eparr, 12); + intarrcopy(cp_mirror, cparr, 8); + } else { + epcp = (CubeArray){ .ep = eparr, .cp = cparr }; + cube = apply_alg(rotation_algs[m], (Cube){0}); + cube_to_arrays(cube, &epcp, pf_epcp); + } + + for (ui = 0; ui < factorial12/factorial8; ui++) { + c[0] = admissible_ep((Cube){ .epose = ui }, pf_e); + c[1] = admissible_ep((Cube){ .eposs = ui }, pf_s); + c[2] = admissible_ep((Cube){ .eposm = ui }, pf_m); + + cube = rotate_via_compose(m,c[epose_source[m]],pf_ep); + epose_rtable[m][ui] = cube.epose; + + cube = rotate_via_compose(m,c[eposs_source[m]],pf_ep); + eposs_rtable[m][ui] = cube.eposs; + + cube = rotate_via_compose(m,c[eposm_source[m]],pf_ep); + eposm_rtable[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_rtable[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_rtable[m][ui] = digit_array_to_int(coarr, 7, 3); + if (m == mirror) + co_rtable[m][ui] = + invert_digits(co_rtable[m][ui], 3, 7); + } + for (ui = 0; ui < factorial8; ui++) { + cube = (Cube){ .cp = ui }; + cube = rotate_via_compose(m, cube, pf_cp); + cp_rtable[m][ui] = cube.cp; + } + for (ui = 0; ui < factorial6; ui++) { + cube = (Cube){ .cpos = ui }; + cube = rotate_via_compose(m, cube, pf_cpos); + cpos_rtable[m][ui] = cube.cpos; + } + for (mi = 0; mi < NMOVES; mi++) { + if (m == mirror) { + b1 = (mi >= U && mi <= Bw3); + b2 = (mi >= S && mi <= E3); + b3 = (mi >= x && mi <= z3); + if (b1 || b2 || b3) + moves_rtable[m][mi] = + inverse_move_aux[mi]; + else + moves_rtable[m][mi] = mi; + + if ((mi-1)/3==(R-1)/3 || (mi-1)/3==(Rw-1)/3) + moves_rtable[m][mi] += 3; + if ((mi-1)/3==(L-1)/3 || (mi-1)/3==(L2-1)/3) + moves_rtable[m][mi] -= 3; + } else { + aux = apply_trans(m, apply_move(mi,(Cube){0})); + for (move = 0; move < NMOVES; move++) { + cube = apply_move( + inverse_move_aux[move], aux); + if (is_solved(cube, false)) + moves_rtable[m][mi] = move; + } + } + } + } + + if (!write_rtables_file()) + fprintf(stderr, "Error writing rtables\n"); +} + +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 void +intarrcopy(int *src, int *dst, int n) +{ + int i; + + for (i = 0; i < n; i++) + dst[i] = src[i]; +} + +static int +invert_digits(int a, int b, int n) +{ + int i, *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; + + return digit_array_to_int(r, n, b); +} + +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; + Cube ret; + + alloc_cubearray(&arrc, f); + cube_to_arrays(c, &arrc, f); + + 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 Move * +moveset_to_movelist(bool *moveset, Step step) +{ + Cube c; + int *a = malloc(NMOVES * sizeof(int)), b[NMOVES]; + int na = 0, nb = 0; + Move i; + + if (moveset != NULL) { + for (i = NULLMOVE+1; i < NMOVES; i++) { + if (moveset[i]) { + c = apply_move(i, (Cube){0}); + if (step.f != NULL && step.f(c)) { + a[na++] = i; + } else { + b[nb++] = i; + } + } + } + } + + intarrcopy(b, a+na, nb); + a[na+nb] = NULLMOVE; + + return (Move *)a; +} + +static AlgList * +new_alglist() +{ + AlgList *ret = malloc(sizeof(AlgList)); + + ret->len = 0; + ret->first = NULL; + ret->last = NULL; + + return ret; +} + +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; /* Truncate */ + if (b == 0) + return 1; + + if (b % 2) + return a * powint(a, b-1); + else + return powint(a*a, b/2); +} + +static bool +read_rtables_file() +{ + FILE *ttf; + int b = sizeof(uint16_t); + bool r = true; + Move m; + + if ((ttf = fopen("rtables", "rb")) != NULL) { + for (m = 0; m < NTRANS; m++) { + r = r && fread(epose_rtable[m],b,me[0],ttf) == me[0]; + r = r && fread(eposs_rtable[m],b,me[1],ttf) == me[1]; + r = r && fread(eposm_rtable[m],b,me[2],ttf) == me[2]; + r = r && fread(eo_rtable[m],b,me[3],ttf) == me[3]; + r = r && fread(cp_rtable[m],b,me[6],ttf) == me[6]; + r = r && fread(co_rtable[m],b,me[7],ttf) == me[7]; + r = r && fread(cpos_rtable[m],b,me[10],ttf) == me[10]; + r = r && fread(moves_rtable[m],b,me[11],ttf) == me[11]; + } + fclose(ttf); + return r; + } else { + return false; + } +} + +static bool +read_ttables_file() +{ + FILE *ttf; + int m, b = sizeof(uint16_t); + bool r = true; + + if ((ttf = fopen("ttables", "rb")) != NULL) { + for (m = 0; m < NMOVES; m++) { + r = r && fread(epose_ttable[m],b,me[0],ttf) == me[0]; + r = r && fread(eposs_ttable[m],b,me[1],ttf) == me[1]; + r = r && fread(eposm_ttable[m],b,me[2],ttf) == me[2]; + r = r && fread(eofb_ttable[m],b,me[3],ttf) == me[3]; + r = r && fread(eorl_ttable[m],b,me[4],ttf) == me[4]; + r = r && fread(eoud_ttable[m],b,me[5],ttf) == me[5]; + r = r && fread(cp_ttable[m],b,me[6],ttf) == me[6]; + r = r && fread(coud_ttable[m],b,me[7],ttf) == me[7]; + r = r && fread(corl_ttable[m],b,me[8],ttf) == me[8]; + r = r && fread(cofb_ttable[m],b,me[9],ttf) == me[9]; + r = r && fread(cpos_ttable[m],b,me[10],ttf) == me[10]; + } + fclose(ttf); + return r; + } else { + return false; + } +} + +static bool +realloc_alg(Alg alg, int n) +{ + if (n+1 >= BASEALGLEN) { + if (reallocarray(alg, n+2, sizeof(NissMove)) == NULL) { + fprintf(stderr, "Error reallocating alg\n"); + return false; + } + } + + return true; +} + +static Cube +rotate_via_compose(Trans r, Cube c, PieceFilter f) +{ + Cube ret; + CubeArray ma = { + .ep = ep_mirror, + .eofb = zero12, + .eorl = zero12, + .eoud = zero12, + .cp = cp_mirror, + .coud = zero8, + .corl = zero8, + .cofb = zero8, + .cpos = cpos_mirror + }; + + if (r != mirror) { + ret = apply_alg_filtered(rotation_niss[r], c, f); + } else { + ret = move_via_arrays(ma, (Cube){0}, f); + ret = compose_filtered(c, ret, f); + ret = move_via_arrays(ma, ret, f); + } + + return ret; +} + +static void +solve_dfs(Cube c, Step s, SolveOptions opts, DfsData dd) +{ + DfsData newdd; + Move move; + NissMove nm; + int i; + bool found_many, prune, niss_makes_sense; + + found_many = dd.sols->len >= opts.max_solutions; + prune = (!opts.can_niss || dd.niss) && dd.m + s.f(c) > dd.d; + if (found_many || prune) + return; + + if (!s.f(c)) { + if (dd.m == dd.d) + append_alg(dd.sols, dd.current_alg); + return; + } + + for (i = 0; opts.sorted_moves[i] != NULLMOVE; i++) { + move = opts.sorted_moves[i]; + if (possible_next[dd.last2][dd.last1][move]) { + nm = (NissMove){ .m = move, .inverse = dd.niss }; + newdd = (DfsData) { + .d = dd.d, + .m = dd.m + 1, + .niss = dd.niss, + .last1 = move, + .last2 = dd.last1, + .sols = dd.sols, + .current_alg = dd.current_alg, + }; + + append_move(dd.current_alg, nm); + solve_dfs(apply_move(move, c), s, opts, newdd); + remove_last_moves(dd.current_alg, 1); + } + } + + niss_makes_sense = !dd.m || (s.f(apply_move(dd.last1, (Cube){0}))); + if (opts.can_niss && !dd.niss && niss_makes_sense) { + newdd = (DfsData) { + .d = dd.d, + .m = dd.m, + .niss = true, + .last1 = NULLMOVE, + .last2 = NULLMOVE, + .sols = dd.sols, + .current_alg = dd.current_alg, + }; + solve_dfs(inverse_cube(c), s, opts, newdd); + } +} + +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_rtables_file() +{ + FILE *ttf; + bool r = true; + int b = sizeof(uint16_t); + Move m; + + if ((ttf = fopen("rtables", "wb")) != NULL) { + for (m = 0; m < NTRANS; m++) { + r = r && fwrite(epose_rtable[m],b,me[0], ttf) == me[0]; + r = r && fwrite(eposs_rtable[m],b,me[1], ttf) == me[1]; + r = r && fwrite(eposm_rtable[m],b,me[2], ttf) == me[2]; + r = r && fwrite(eo_rtable[m],b,me[3], ttf) == me[3]; + r = r && fwrite(cp_rtable[m],b,me[6], ttf) == me[6]; + r = r && fwrite(co_rtable[m],b,me[7], ttf) == me[7]; + r = r && fwrite(cpos_rtable[m],b,me[10],ttf) == me[10]; + r = r && fwrite(moves_rtable[m],b,me[11],ttf)== me[11]; + } + fclose(ttf); + return r; + } else { + return false; + } +} + +static bool +write_ttables_file() +{ + FILE *ttf; + int m, b = sizeof(uint16_t);; + bool r = true; + + if ((ttf = fopen("ttables", "wb")) != NULL) { + for (m = 0; m < NMOVES; m++) { + r = r && fwrite(epose_ttable[m],b,me[0],ttf) == me[0]; + r = r && fwrite(eposs_ttable[m],b,me[1],ttf) == me[1]; + r = r && fwrite(eposm_ttable[m],b,me[2],ttf) == me[2]; + r = r && fwrite(eofb_ttable[m],b,me[3],ttf) == me[3]; + r = r && fwrite(eorl_ttable[m],b,me[4],ttf) == me[4]; + r = r && fwrite(eoud_ttable[m],b,me[5],ttf) == me[5]; + r = r && fwrite(cp_ttable[m],b,me[6],ttf) == me[6]; + r = r && fwrite(coud_ttable[m],b,me[7],ttf) == me[7]; + r = r && fwrite(corl_ttable[m],b,me[8],ttf) == me[8]; + r = r && fwrite(cofb_ttable[m],b,me[9],ttf) == me[9]; + r = r && fwrite(cpos_ttable[m],b,me[10],ttf) == me[10]; + } + fclose(ttf); + return r; + } else { + return false; + } +} + +/* Public functions implementation *******************************************/ + +Cube +apply_alg(Alg alg, Cube cube) +{ + return apply_alg_filtered(alg, cube, pf_all); +} + +Cube +apply_move(Move m, Cube cube) +{ + Cube moved = {0}; + + moved.epose = epose_ttable[m][cube.epose]; + moved.eposs = eposs_ttable[m][cube.eposs]; + moved.eposm = eposm_ttable[m][cube.eposm]; + moved.eofb = eofb_ttable[m][cube.eofb]; + moved.eorl = eorl_ttable[m][cube.eorl]; + moved.eoud = eoud_ttable[m][cube.eoud]; + moved.coud = coud_ttable[m][cube.coud]; + moved.cofb = cofb_ttable[m][cube.cofb]; + moved.corl = corl_ttable[m][cube.corl]; + moved.cp = cp_ttable[m][cube.cp]; + moved.cpos = cpos_ttable[m][cube.cpos]; + + return moved; +} + +Cube +apply_trans(Trans t, Cube cube) +{ + Cube transformed = {0}; + uint16_t aux_epos[3] = { cube.epose, cube.eposs, cube.eposm }; + uint16_t aux_eo[3] = { cube.eoud, cube.eorl, cube.eofb }; + uint16_t aux_co[3] = { cube.coud, cube.corl, cube.cofb }; + + transformed.epose = epose_rtable[t][aux_epos[epose_source[t]]]; + transformed.eposs = eposs_rtable[t][aux_epos[eposs_source[t]]]; + transformed.eposm = eposm_rtable[t][aux_epos[eposm_source[t]]]; + transformed.eofb = eo_rtable[t][aux_eo[eofb_source[t]]]; + transformed.eorl = eo_rtable[t][aux_eo[eorl_source[t]]]; + transformed.eoud = eo_rtable[t][aux_eo[eoud_source[t]]]; + transformed.coud = co_rtable[t][aux_co[coud_source[t]]]; + transformed.corl = co_rtable[t][aux_co[corl_source[t]]]; + transformed.cofb = co_rtable[t][aux_co[cofb_source[t]]]; + transformed.cp = cp_rtable[t][cube.cp]; + transformed.cpos = cpos_rtable[t][cube.cpos]; + + return transformed; +} + +/* TODO: this has to be changed using pre-computations */ +bool +block_solved(Cube cube, Block block) +{ + CubeArray arr; + int i; + bool ret = true; + + alloc_cubearray(&arr, pf_all); + cube_to_arrays(cube, &arr, pf_all); + + for (i = 0; i < 12; i++) + ret = ret && !(block.edge[i] && (arr.ep[i] != i || arr.eofb[i])); + for (i = 0; i < 8; i++) + ret = ret && !(block.corner[i] && (arr.cp[i] != i || arr.coud[i])); + for (i = 0; i < 6; i++) + ret = ret && !(block.center[i] && arr.cpos[i] != i); + + free_cubearray(&arr, pf_all); + + return ret; +} + +Center +center_at(Cube cube, Center c) +{ + int ret; + CubeArray arr; + + alloc_cubearray(&arr, pf_cpos); + cube_to_arrays(cube, &arr, pf_cpos); + ret = arr.cpos[c]; + free_cubearray(&arr, pf_cpos); + + return ret; +} + +Cube +compose(Cube c2, Cube c1) +{ + return compose_filtered(c2, c1, pf_all); +} + +Corner +corner_at(Cube cube, Corner c) +{ + int ret; + CubeArray arr; + + alloc_cubearray(&arr, pf_cp); + cube_to_arrays(cube, &arr, pf_cp); + ret = arr.cp[c]; + free_cubearray(&arr, pf_cp); + + return ret; +} + +Edge +edge_at(Cube cube, Edge e) +{ + int ret; + CubeArray arr; + + alloc_cubearray(&arr, pf_ep); + cube_to_arrays(cube, &arr, pf_ep); + ret = arr.ep[e]; + free_cubearray(&arr, pf_ep); + + return ret; +} + +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; +} + +Cube +inverse_cube(Cube cube) +{ + CubeArray arr, inv; + Cube ret; + int i; + + alloc_cubearray(&arr, pf_all); + alloc_cubearray(&inv, pf_all); + + cube_to_arrays(cube, &arr, pf_all); + + 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_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 equal(cube, (Cube){0}); +} + +int +piece_orientation(Cube cube, int piece, char *orientation) +{ + int arr[12], n, b; + uint16_t x; + + if (!strcmp(orientation, "eofb")) { + x = cube.eofb; + n = 12; + b = 2; + } else if (!strcmp(orientation, "eorl")) { + x = cube.eorl; + n = 12; + b = 2; + } else if (!strcmp(orientation, "eoud")) { + x = cube.eoud; + n = 12; + b = 2; + } else if (!strcmp(orientation, "coud")) { + x = cube.coud; + n = 8; + b = 3; + } else if (!strcmp(orientation, "corl")) { + x = cube.corl; + n = 8; + b = 3; + } else if (!strcmp(orientation, "cofb")) { + x = cube.cofb; + n = 8; + b = 3; + } else { + return -1; + } + + int_to_sum_zero_array(x, b, n, arr); + if (piece < n) + return arr[piece]; + + return -1; +} + +void +print_cube(Cube cube) +{ + CubeArray arr; + + alloc_cubearray(&arr, pf_all); + cube_to_arrays(cube, &arr, 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); +} + +void +concat(Alg src1, Alg src2, Alg dest) +{ + int n1 = len(src1), n2 = len(src2); + + if (!realloc_alg(dest, n1+n2)) + return; + + copy_alg(src1, dest); + copy_alg(src2, dest + n1); +} + +void +copy_alg(Alg src, Alg dest) +{ + int i, n = len(src); + + if (!realloc_alg(dest, n)) + return; + + for (i = 0; src[i].m != NULLMOVE; i++) + dest[i] = src[i]; + dest[i].m = NULLMOVE; +} + +void +invert_alg(Alg src, Alg dest) +{ + Move m; + int i, n = len(src); + + if (!realloc_alg(dest, n)) + return; + + for (i = 0; i < n; i++) { + m = inverse_move_aux[src[i].m]; + dest[n-i-1] = (NissMove) { .m = m, .inverse = src[i].inverse }; + } + dest[n].m = NULLMOVE; +} + +int +len(Alg alg) +{ + int i; + + for (i = 0; alg[i].m != NULLMOVE; i++); + + return i; +} + +Alg +new_alg(char *str) +{ + Alg alg = malloc(BASEALGLEN * sizeof(NissMove)); + int i; + bool niss = false; + Move j, m; + NissMove nm; + + alg[0] = (NissMove){ .m = NULLMOVE }; + 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++; + } + nm = (NissMove){ .m = m, .inverse = niss }; + append_move(alg, nm); + break; + } + } + } + append_move(alg, (NissMove){ .m = NULLMOVE }); + + return alg; +} + +void +print_alg(Alg alg) +{ + char fill[4]; + int i; + bool niss = false; + + for (i = 0; alg[i].m != NULLMOVE; i++) { + if (!niss && alg[i].inverse) + strcpy(fill, i == 0 ? "(" : " ("); + if (niss && !alg[i].inverse) + strcpy(fill, ") "); + if (niss == alg[i].inverse) + strcpy(fill, i == 0 ? "" : " "); + + printf("%s%s", fill, move_string[alg[i].m]); + niss = alg[i].inverse; + } + printf("%s\n", niss ? ")" : ""); +} + +void +remove_last_moves(Alg alg, int k) +{ + int n = len(alg); + int i = max(0, n-k); + + alg[i].m = NULLMOVE; +} + +AlgList * +solve(Cube cube, Step step, SolveOptions opts) +{ + AlgList *sols = new_alglist(); + AlgListNode *node; + Cube c; + DfsData dd; + int i; + + if (step.ready != NULL && !step.ready(cube)) + return sols; + + if (opts.sorted_moves == NULL) + opts.sorted_moves = moveset_to_movelist(opts.moveset, step); + + for (i = opts.min_moves; i <= opts.max_moves; i++) { + if (sols->len && opts.optimal_only) + break; + + c = apply_trans(opts.pre_trans, cube); + dd = (DfsData) { + .d = i, + .m = 0, + .niss = false, + .last1 = NULLMOVE, + .last2 = NULLMOVE, + .sols = sols, + .current_alg = new_alg("") + }; + + solve_dfs(c, step, opts, dd); + } + + for (node = sols->first; node != NULL; node = node->next) + transform_alg(inverse_trans_aux[opts.pre_trans], node->alg); + + return sols; +} + +void +transform_alg(Trans t, Alg alg) +{ + int i; + + for (i = 0; alg[i].m != NULLMOVE; i++) + alg[i].m = moves_rtable[t][alg[i].m]; +} + + +void +init() +{ + init_moves(); + init_auxtables(); + init_trans(); +} diff --git a/old/2021-06-02-cleanedup/cube.h b/old/2021-06-02-cleanedup/cube.h new file mode 100644 index 0000000..f1559a4 --- /dev/null +++ b/old/2021-06-02-cleanedup/cube.h @@ -0,0 +1,179 @@ +#include +#include +#include +#include +#include + +/* Constants ****************************************************************/ + +#define NMOVES (z3+1) +#define NTRANS (mirror+1) +#define NROTATIONS (NTRANS-1) + +/* Typedefs *****************************************************************/ + +typedef enum center Center; +typedef enum corner Corner; +typedef enum edge Edge; +typedef enum move Move; +typedef enum trans Trans; + +typedef struct nissmove * Alg; +typedef struct alglist AlgList; +typedef struct alglistnode AlgListNode; +typedef struct block Block; +typedef struct cube Cube; +typedef struct nissmove NissMove; +typedef struct solveoptions SolveOptions; +typedef struct step Step; + +/* Type specifications *******************************************************/ + +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, + mirror, /* R|L */ +}; + +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 +cube +{ + uint16_t epose; + uint16_t eposs; + uint16_t eposm; + uint16_t eofb; + uint16_t eorl; + uint16_t eoud; + uint16_t cp; + uint16_t coud; + uint16_t cofb; + uint16_t corl; + uint16_t cpos; +}; + +struct +nissmove +{ + Move m; + bool inverse; +}; + +struct +solveoptions +{ + int min_moves; + int max_moves; + int max_solutions; + bool optimal_only; + bool can_niss; + bool *moveset; + Move *sorted_moves; + Trans pre_trans; +}; + +struct +step +{ + int (*f)(Cube); + bool (*ready)(Cube); +}; + +/* Public functions **********************************************************/ + +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); +Center center_at(Cube cube, Center c); +Cube compose(Cube c2, Cube c1); /* Use c2 as an alg on c1 */ +Corner corner_at(Cube cube, Corner c); +Edge edge_at(Cube cube, Edge e); +bool equal(Cube c1, Cube c2); +Cube inverse_cube(Cube cube); +Move inverse_move(Move m); +Trans inverse_trans(Trans t); +bool is_solved(Cube cube, bool reorient); +int piece_orientation(Cube cube, int piece, char *orientation); +void print_cube(Cube cube); +AlgList * solve(Cube cube, Step step, SolveOptions opts); + +void concat(Alg src1, Alg src2, Alg dest); +void copy_alg(Alg src, Alg dest); +void invert_alg(Alg src, Alg dest); +int len(Alg alg); +Alg new_alg(char *str); +void print_alg(Alg alg); +void remove_last_moves(Alg alg, int k); +void transform_alg(Trans t, Alg alg); + +void init(); diff --git a/old/2021-06-02-cleanedup/main.c b/old/2021-06-02-cleanedup/main.c new file mode 100644 index 0000000..fca5e3c --- /dev/null +++ b/old/2021-06-02-cleanedup/main.c @@ -0,0 +1,35 @@ +#include +#include "cube.h" +#include "steps.h" + +int main() { + Alg algo; + AlgList *sols; + Cube cube; + SolveOptions opts; + + init(); + + algo = new_alg("R U R' F"); + cube = apply_alg(algo, (Cube){0}); + + print_cube(apply_trans(rd, cube)); + + opts = (SolveOptions) { + .min_moves = 0, + .max_moves = 5, + .optimal_only = true, + .max_solutions = 3, + .can_niss = false, + .moveset = standard_moveset, + .pre_trans = fu + }; + sols = solve(cube, step_eofb, opts); + if (sols->len == 0) + fprintf(stderr, "No solution found\n"); + else + print_alg(sols->first->alg); + + + return 0; +} diff --git a/old/2021-06-02-cleanedup/steps.h b/old/2021-06-02-cleanedup/steps.h new file mode 100644 index 0000000..452b71c --- /dev/null +++ b/old/2021-06-02-cleanedup/steps.h @@ -0,0 +1,22 @@ +/* Pre-conditions, i.e. "ready(cube)" functions ******************************/ + +bool always_ready(Cube cube) { return true; } + +/* Main functions, i.e. "f(cube)" ********************************************/ + +int f_eofb(Cube cube) { return (cube.eofb != 0) ? 1 : 0; } + +/* Steps *********************************************************************/ + +Step step_eofb = { .f = f_eofb, .ready = always_ready }; + +/* Movesets ******************************************************************/ + +bool standard_moveset[NMOVES] = { + [U] = true, [U2] = true, [U3] = true, + [D] = true, [D2] = true, [D3] = true, + [R] = true, [R2] = true, [R3] = true, + [L] = true, [L2] = true, [L3] = true, + [F] = true, [F2] = true, [F3] = true, + [B] = true, [B2] = true, [B3] = true, +}; -- cgit v1.3