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! --- src/moves.c | 956 +++++++++++++++++++++++++++++------------------------------- 1 file changed, 455 insertions(+), 501 deletions(-) (limited to 'src/moves.c') diff --git a/src/moves.c b/src/moves.c index ce47e8f..25ce779 100644 --- a/src/moves.c +++ b/src/moves.c @@ -1,521 +1,475 @@ -/* This file contains the definitions of the basic moves of the cube. - * There is no object or type representing the cube. - * Data about the cube can be represented by arrays (describing the position - * of pieces of certain types), integers (representing for example a bitmask - * for the orientation of pieces of certain type, or the permutation index of - * an array representing the permutation of pieces). - * Each of the moves functions operates on one such piece of data. - * - * For example, a way of representing the cube can be: - * - An integer eo, which is a bitmask for the orientation of the edges. - * - An integer co, same for corners. - * - An array ep[12], where a[i]=j means that the edge j is in place i. - * - An integer cp representing the permutation index of a permutation array - * which is the analogue of that described for edges. - * - * Different representations will be used for different use-cases. */ - -#include "coordinates.h" #include "moves.h" -/* possible_next[i][j] is a bitmask representing the possible - * next moves we can apply. For example, if the last moves a 0 R then it does - * not make sense to apply R, R2 or R'. If they are U D2 it does not make - * sense to apply any U* or D*. */ -int possible_next[19][19]; +/* Local functions ***********************************************************/ -int parallel(int m1, int m2) { - if (m1 == 0 || m2 == 0) return 0; - return ((m1-1)/6 == (m2-1)/6); -} - -int compute_possible_next(int last1, int last2) { - if (last1 == 0) return move_mask_all; - - /* Removes the 2 or ' (e.g. turns U2 to U, R' to R). */ - last2 = (last2 == 0) ? last2 : 3*((last2-1)/3) + 1; - last1 = 3*((last1-1)/3) + 1; +static Cube apply_move_cubearray(Move m, Cube cube, PieceFilter f); +static bool read_mtables_file(); +static bool write_mtables_file(); - int mask = move_mask_all ^ (7 << last1); +/* Tables and other data *****************************************************/ - if (parallel(last1, last2)) - mask ^= 7 << last2; - else if (last1 % 6 == 4) /*Always U before D, R before L, F before B*/ - mask ^= 7 << (last1-3); +/* Every move is translated to a an alg before filling the + transition tables, see init_moves() */ - return mask; -} - -void init_possible_next() { - for (int i = 0; i < 19; i++) - for (int j = 0; j < 19; j++) - possible_next[i][j] = compute_possible_next(i, j); -} - -/* Piece cycles depending on the move. For example edge_cycle[U2][UF] - * gives the piece in position UF after applying U2 to a solved cube */ - -int edge_cycle[19][12] = { - {UF, UL, UB, UR, DF, DL, DB, DR, FR, FL, BL, BR}, /* - */ - {UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR}, /* U */ - {UB, UR, UF, UL, DF, DL, DB, DR, FR, FL, BL, BR}, /* U2 */ - {UL, UB, UR, UF, DF, DL, DB, DR, FR, FL, BL, BR}, /* U' */ - {UF, UL, UB, UR, DL, DB, DR, DF, FR, FL, BL, BR}, /* D */ - {UF, UL, UB, UR, DB, DR, DF, DL, FR, FL, BL, BR}, /* D2 */ - {UF, UL, UB, UR, DR, DF, DL, DB, FR, FL, BL, BR}, /* D' */ - {UF, UL, UB, FR, DF, DL, DB, BR, DR, FL, BL, UR}, /* R */ - {UF, UL, UB, DR, DF, DL, DB, UR, BR, FL, BL, FR}, /* R2 */ - {UF, UL, UB, BR, DF, DL, DB, FR, UR, FL, BL, DR}, /* R' */ - {UF, BL, UB, UR, DF, FL, DB, DR, FR, UL, DL, BR}, /* L */ - {UF, DL, UB, UR, DF, UL, DB, DR, FR, BL, FL, BR}, /* L2 */ - {UF, FL, UB, UR, DF, BL, DB, DR, FR, DL, UL, BR}, /* L' */ - {FL, UL, UB, UR, FR, DL, DB, DR, UF, DF, BL, BR}, /* F */ - {DF, UL, UB, UR, UF, DL, DB, DR, FL, FR, BL, BR}, /* F2 */ - {FR, UL, UB, UR, FL, DL, DB, DR, DF, UF, BL, BR}, /* F' */ - {UF, UL, BR, UR, DF, DL, BL, DR, FR, FL, UB, DB}, /* B */ - {UF, UL, DB, UR, DF, DL, UB, DR, FR, FL, BR, BL}, /* B2 */ - {UF, UL, BL, UR, DF, DL, BR, DR, FR, FL, DB, UB} /* B' */ +static 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 corner_cycle[19][8] = { - {UFR, UFL, UBL, UBR, DFR, DFL, DBL, DBR}, /* - */ - {UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR}, /* U */ - {UBL, UBR, UFR, UFL, DFR, DFL, DBL, DBR}, /* U2 */ - {UFL, UBL, UBR, UFR, DFR, DFL, DBL, DBR}, /* U' */ - {UFR, UFL, UBL, UBR, DFL, DBL, DBR, DFR}, /* D */ - {UFR, UFL, UBL, UBR, DBL, DBR, DFR, DFL}, /* D2 */ - {UFR, UFL, UBL, UBR, DBR, DFR, DFL, DBL}, /* D' */ - {DFR, UFL, UBL, UFR, DBR, DFL, DBL, UBR}, /* R */ - {DBR, UFL, UBL, DFR, UBR, DFL, DBL, UFR}, /* R2 */ - {UBR, UFL, UBL, DBR, UFR, DFL, DBL, DFR}, /* R' */ - {UFR, UBL, DBL, UBR, DFR, UFL, DFL, DBR}, /* L */ - {UFR, DBL, DFL, UBR, DFR, UBL, UFL, DBR}, /* L2 */ - {UFR, DFL, UFL, UBR, DFR, DBL, UBL, DBR}, /* L' */ - {UFL, DFL, UBL, UBR, UFR, DFR, DBL, DBR}, /* F */ - {DFL, DFR, UBL, UBR, UFL, UFR, DBL, DBR}, /* F2 */ - {DFR, UFR, UBL, UBR, DFL, UFL, DBL, DBR}, /* F' */ - {UFR, UFL, UBR, DBR, DFR, DFL, UBL, DBL}, /* B */ - {UFR, UFL, DBR, DBL, DFR, DFL, UBR, UBL}, /* B2 */ - {UFR, UFL, DBL, UBL, DFR, DFL, DBR, UBR}, /* U' */ +static 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 } }; -/* Transition tables */ - -int eofb_transition_table[pow2to11][19]; -int eorl_transition_table[pow2to11][19]; -int eoud_transition_table[pow2to11][19]; -int coud_transition_table[pow3to7][19]; -int cofb_transition_table[pow3to7][19]; -int corl_transition_table[pow3to7][19]; -int epud_transition_table[factorial8][19]; -int eprl_transition_table[factorial8][19]; -int epfb_transition_table[factorial8][19]; -int epose_transition_table[binom12on4][19]; -int eposs_transition_table[binom12on4][19]; -int eposm_transition_table[binom12on4][19]; -int epe_transition_table[factorial4][19]; -int eps_transition_table[factorial4][19]; -int epm_transition_table[factorial4][19]; -int emslices_transition_table[binom12on4*binom8on4][19]; -int cp_transition_table[factorial8][19]; - -/***/ -/* Functions for permuting pieces (given in array format) */ -/***/ - -void apply_move_ep_array(int move, int ep[12]) { - int aux[12]; - for (int i = 0; i < 12; i++) - aux[i] = ep[i]; - for (int i = 0; i < 12; i++) - ep[i] = aux[edge_cycle[move][i]]; -} - -void apply_move_cp_array(int move, int cp[8]) { - int aux[8]; - for (int i = 0; i < 8; i++) - aux[i] = cp[i]; - for (int i = 0; i < 8; i++) - cp[i] = aux[corner_cycle[move][i]]; -} - -/***/ -/* Functions for permuting pieces (given in integer format) */ -/***/ - -int apply_move_ep_int(int move, int ep) { - int a[12]; - ep_int_to_array(ep, a); - apply_move_ep_array(move, a); - return ep_array_to_int(a); -} - -int apply_move_epud_int(int move, int ep) { - int a[12]; - epud_int_to_array(ep, a); - apply_move_ep_array(move, a); - return epud_array_to_int(a); -} - -int apply_move_eprl_int(int move, int ep) { - int a[12]; - eprl_int_to_array(ep, a); - apply_move_ep_array(move, a); - return eprl_array_to_int(a); -} - -int apply_move_epfb_int(int move, int ep) { - int a[12]; - epfb_int_to_array(ep, a); - apply_move_ep_array(move, a); - return epfb_array_to_int(a); -} - -int apply_move_epose_int(int move, int ep) { - int a[12]; - epose_int_to_array(ep, a); - apply_move_ep_array(move, a); - return epose_array_to_int(a); -} - -int apply_move_eposs_int(int move, int ep) { - int a[12]; - eposs_int_to_array(ep, a); - apply_move_ep_array(move, a); - return eposs_array_to_int(a); -} - -int apply_move_eposm_int(int move, int ep) { - int a[12]; - eposm_int_to_array(ep, a); - apply_move_ep_array(move, a); - return eposm_array_to_int(a); -} - -int apply_move_epe_int(int move, int ep) { - int a[12]; - epe_int_to_array(ep, a); - apply_move_ep_array(move, a); - return epe_array_to_int(a); -} - -int apply_move_eps_int(int move, int ep) { - int a[12]; - eps_int_to_array(ep, a); - apply_move_ep_array(move, a); - return eps_array_to_int(a); -} - -int apply_move_epm_int(int move, int ep) { - int a[12]; - epm_int_to_array(ep, a); - apply_move_ep_array(move, a); - return epm_array_to_int(a); -} - -int apply_move_emslices_int(int move, int e) { - int a[12]; - emslices_int_to_array(e, a); - apply_move_ep_array(move, a); - return emslices_array_to_int(a); -} - -int apply_move_cp_int(int move, int cp) { - int a[8]; - cp_int_to_array(cp, a); - apply_move_cp_array(move, a); - return cp_array_to_int(a); -} - -int apply_move_eofb_int(int move, int eo) { - int a[12]; - eo_11bits_to_array(eo, a); - apply_move_ep_array(move, a); - /* Change edge orientation */ - if (move == F || move == F3) { - a[UF] = 1 - a[UF]; - a[DF] = 1 - a[DF]; - a[FR] = 1 - a[FR]; - a[FL] = 1 - a[FL]; - } - if (move == B || move == B3) { - a[UB] = 1 - a[UB]; - a[DB] = 1 - a[DB]; - a[BL] = 1 - a[BL]; - a[BR] = 1 - a[BR]; - } - return eo_array_to_11bits(a); -} - -int apply_move_eorl_int(int move, int eo) { - int a[12]; - eo_11bits_to_array(eo, a); - apply_move_ep_array(move, a); - /* Change edge orientation */ - if (move == R || move == R3) { - a[UR] = 1 - a[UR]; - a[DR] = 1 - a[DR]; - a[FR] = 1 - a[FR]; - a[BR] = 1 - a[BR]; - } - if (move == L || move == L3) { - a[UL] = 1 - a[UL]; - a[DL] = 1 - a[DL]; - a[FL] = 1 - a[FL]; - a[BL] = 1 - a[BL]; - } - return eo_array_to_11bits(a); -} - -int apply_move_eoud_int(int move, int eo) { - int a[12]; - eo_11bits_to_array(eo, a); - apply_move_ep_array(move, a); - /* Change edge orientation */ - if (move == U || move == U3) { - a[UF] = 1 - a[UF]; - a[UL] = 1 - a[UL]; - a[UB] = 1 - a[UB]; - a[UR] = 1 - a[UR]; - } - if (move == D || move == D3) { - a[DF] = 1 - a[DF]; - a[DL] = 1 - a[DL]; - a[DB] = 1 - a[DB]; - a[DR] = 1 - a[DR]; - } - return eo_array_to_11bits(a); -} - -int apply_move_coud_int(int move, int co) { - int a[8]; - co_7trits_to_array(co, a); - apply_move_cp_array(move, a); - /* Change corner orientation */ - if (move == R || move == R3) { - a[UFR] = (a[UFR] + 2) % 3; - a[UBR] = (a[UBR] + 1) % 3; - a[DBR] = (a[DBR] + 2) % 3; - a[DFR] = (a[DFR] + 1) % 3; - } - if (move == L || move == L3) { - a[UBL] = (a[UBL] + 2) % 3; - a[UFL] = (a[UFL] + 1) % 3; - a[DFL] = (a[DFL] + 2) % 3; - a[DBL] = (a[DBL] + 1) % 3; - } - if (move == F || move == F3) { - a[UFL] = (a[UFL] + 2) % 3; - a[UFR] = (a[UFR] + 1) % 3; - a[DFR] = (a[DFR] + 2) % 3; - a[DFL] = (a[DFL] + 1) % 3; - } - if (move == B || move == B3) { - a[UBR] = (a[UBR] + 2) % 3; - a[UBL] = (a[UBL] + 1) % 3; - a[DBL] = (a[DBL] + 2) % 3; - a[DBR] = (a[DBR] + 1) % 3; - } - return co_array_to_7trits(a); -} - -int apply_move_cofb_int(int move, int co) { - int a[8]; - co_7trits_to_array(co, a); - apply_move_cp_array(move, a); - /* Change corner orientation */ - if (move == R || move == R3) { - a[UFR] = (a[UFR] + 1) % 3; - a[UBR] = (a[UBR] + 2) % 3; - a[DBR] = (a[DBR] + 1) % 3; - a[DFR] = (a[DFR] + 2) % 3; - } - if (move == L || move == L3) { - a[UBL] = (a[UBL] + 1) % 3; - a[UFL] = (a[UFL] + 2) % 3; - a[DFL] = (a[DFL] + 1) % 3; - a[DBL] = (a[DBL] + 2) % 3; - } - if (move == U || move == U3) { - a[UFL] = (a[UFL] + 1) % 3; - a[UFR] = (a[UFR] + 2) % 3; - a[UBL] = (a[UBL] + 2) % 3; - a[UBR] = (a[UBR] + 1) % 3; - } - if (move == D || move == D3) { - a[DFL] = (a[DFL] + 2) % 3; - a[DFR] = (a[DFR] + 1) % 3; - a[DBL] = (a[DBL] + 1) % 3; - a[DBR] = (a[DBR] + 2) % 3; - } - return co_array_to_7trits(a); -} - -int apply_move_corl_int(int move, int co) { - int a[8]; - co_7trits_to_array(co, a); - apply_move_cp_array(move, a); - /* Change corner orientation */ - if (move == F || move == F3) { - a[UFR] = (a[UFR] + 2) % 3; - a[UFL] = (a[UFL] + 1) % 3; - a[DFL] = (a[DFL] + 2) % 3; - a[DFR] = (a[DFR] + 1) % 3; - } - if (move == B || move == B3) { - a[UBL] = (a[UBL] + 2) % 3; - a[UBR] = (a[UBR] + 1) % 3; - a[DBR] = (a[DBR] + 2) % 3; - a[DBL] = (a[DBL] + 1) % 3; - } - if (move == U || move == U3) { - a[UFL] = (a[UFL] + 2) % 3; - a[UFR] = (a[UFR] + 1) % 3; - a[UBL] = (a[UBL] + 1) % 3; - a[UBR] = (a[UBR] + 2) % 3; - } - if (move == D || move == D3) { - a[DFL] = (a[DFL] + 1) % 3; - a[DFR] = (a[DFR] + 2) % 3; - a[DBL] = (a[DBL] + 2) % 3; - a[DBR] = (a[DBR] + 1) % 3; - } - return co_array_to_7trits(a); -} - - - -/* Initialize transition tables */ - -void init_epud_transition_table() { - for (int i = 0; i < factorial8; i++) - for (int j = 0; j < 19; j++) - if (move_mask_drud & (1 << j)) - epud_transition_table[i][j] = apply_move_epud_int(j, i); -} - -void init_eprl_transition_table() { - for (int i = 0; i < factorial8; i++) - for (int j = 0; j < 19; j++) - if (move_mask_drrl & (1 << j)) - eprl_transition_table[i][j] = apply_move_eprl_int(j, i); -} - -void init_epfb_transition_table() { - for (int i = 0; i < factorial8; i++) - for (int j = 0; j < 19; j++) - if (move_mask_drfb & (1 << j)) - epfb_transition_table[i][j] = apply_move_epfb_int(j, i); -} - -void init_epose_transition_table() { - for (int i = 0; i < binom12on4; i++) - for (int j = 0; j < 19; j++) - epose_transition_table[i][j] = apply_move_epose_int(j, i); -} - -void init_eposs_transition_table() { - for (int i = 0; i < binom12on4; i++) - for (int j = 0; j < 19; j++) - eposs_transition_table[i][j] = apply_move_eposs_int(j, i); -} - -void init_eposm_transition_table() { - for (int i = 0; i < binom12on4; i++) - for (int j = 0; j < 19; j++) - eposm_transition_table[i][j] = apply_move_eposm_int(j, i); -} - -void init_epe_transition_table() { - for (int i = 0; i < factorial4; i++) { - for (int j = 0; j < 19; j++) - if (move_mask_drud & (1 << j)) - epe_transition_table[i][j] = apply_move_epe_int(j, i); - } -} - -void init_eps_transition_table() { - for (int i = 0; i < factorial4; i++) { - for (int j = 0; j < 19; j++) - if (move_mask_drfb & (1 << j)) - eps_transition_table[i][j] = apply_move_eps_int(j, i); - } -} - -void init_epm_transition_table() { - for (int i = 0; i < factorial4; i++) { - for (int j = 0; j < 19; j++) - if (move_mask_drrl & (1 << j)) - epm_transition_table[i][j] = apply_move_epm_int(j, i); - } -} - -void init_emslices_transition_table() { - for (int i = 0; i < binom12on4*binom8on4; i++) { - for (int j = 0; j < 19; j++) - emslices_transition_table[i][j] = apply_move_emslices_int(j, i); - } -} +static 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 } +}; -void init_cp_transition_table() { - for (int i = 0; i < factorial8; i++) - for (int j = 0; j < 19; j++) - cp_transition_table[i][j] = apply_move_cp_int(j, i); -} +static int eofb_flipped[NMOVES][12] = { + [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 }, + [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 } +}; -void init_eofb_transition_table() { - for (int i = 0; i < pow2to11; i++) - for (int j = 0; j < 19; j++) - eofb_transition_table[i][j] = apply_move_eofb_int(j, i); -} +static 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 } +}; -void init_eorl_transition_table() { - for (int i = 0; i < pow2to11; i++) - for (int j = 0; j < 19; j++) - eorl_transition_table[i][j] = apply_move_eorl_int(j, i); -} +static 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 } +}; -void init_eoud_transition_table() { - for (int i = 0; i < pow2to11; i++) - for (int j = 0; j < 19; j++) - eoud_transition_table[i][j] = apply_move_eoud_int(j, i); -} +static int coud_flipped[NMOVES][8] = { + [x] = { + [UFR] = 2, [UBR] = 1, [UFL] = 1, [UBL] = 2, + [DBR] = 2, [DFR] = 1, [DBL] = 1, [DFL] = 2 + } +}; -void init_coud_transition_table() { - for (int i = 0; i < pow3to7; i++) - for (int j = 0; j < 19; j++ ) - coud_transition_table[i][j] = apply_move_coud_int(j, i); -} +static 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 + } +}; -void init_cofb_transition_table() { - for (int i = 0; i < pow3to7; i++) - for (int j = 0; j < 19; j++ ) - cofb_transition_table[i][j] = apply_move_cofb_int(j, i); -} +static 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 + } +}; -void init_corl_transition_table() { - for (int i = 0; i < pow3to7; i++) - for (int j = 0; j < 19; j++ ) - corl_transition_table[i][j] = apply_move_corl_int(j, i); -} +static char equiv_alg_string[100][NMOVES] = { + [NULLMOVE] = "", + + [U] = " U ", + [U2] = " UU ", + [U3] = " UUU ", + [D] = " xx U xx ", + [D2] = " xx UU xx ", + [D3] = " xx UUU xx ", + [R] = " yx U xxxyyy ", + [R2] = " yx UU xxxyyy ", + [R3] = " yx UUU xxxyyy ", + [L] = " yyyx U xxxy ", + [L2] = " yyyx UU xxxy ", + [L3] = " yyyx UUU xxxy ", + [F] = " x U xxx ", + [F2] = " x UU xxx ", + [F3] = " x UUU xxx ", + [B] = " xxx U x ", + [B2] = " xxx UU x ", + [B3] = " xxx UUU x ", + + [Uw] = " xx U xx y ", + [Uw2] = " xx UU xx yy ", + [Uw3] = " xx UUU xx yyy ", + [Dw] = " U yyy ", + [Dw2] = " UU yy ", + [Dw3] = " UUU y ", + [Rw] = " yyyx U xxxy x ", + [Rw2] = " yyyx UU xxxy xx ", + [Rw3] = " yyyx UUU xxxy xxx ", + [Lw] = " yx U xxxyyy xxx ", + [Lw2] = " yx UU xxxyyy xx ", + [Lw3] = " yx UUU xxxyyy x ", + [Fw] = " xxx U x yxxxyyy ", + [Fw2] = " xxx UU x yxxyyy ", + [Fw3] = " xxx UUU x yxyyy ", + [Bw] = " x U xxx yxyyy ", + [Bw2] = " x UU xxx yxxyyy ", + [Bw3] = " x UUU xxx yxxxyyy ", + + [M] = " yx U xx UUU yxyyy ", + [M2] = " yx UU xx UU xxxy ", + [M3] = " yx UUU xx U yxxxy ", + [S] = " x UUU xx U yyyx ", + [S2] = " x UU xx UU yyx ", + [S3] = " x U xx UUU yx ", + [E] = " U xx UUU xxyyy ", + [E2] = " UU xx UU xxyy ", + [E3] = " UUU xx U xxy ", + + [x] = " x ", + [x2] = " xx ", + [x3] = " xxx ", + [y] = " y ", + [y2] = " yy ", + [y3] = " yyy ", + [z] = " yyy x y ", + [z2] = " yy xx ", + [z3] = " y x yyy " +}; -void init_transition_table() { - init_epud_transition_table(); - init_eprl_transition_table(); - init_epfb_transition_table(); - init_epose_transition_table(); - init_eposs_transition_table(); - init_eposm_transition_table(); - init_epe_transition_table(); - init_eps_transition_table(); - init_epm_transition_table(); - init_emslices_transition_table(); - init_cp_transition_table(); - init_eofb_transition_table(); - init_eorl_transition_table(); - init_eoud_transition_table(); - init_coud_transition_table(); - init_cofb_transition_table(); - init_corl_transition_table(); +/* Transition tables, to be loaded up at the beginning */ +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]; + + +/* Local functions implementation ********************************************/ + +static Cube +apply_move_cubearray(Move m, Cube cube, PieceFilter f) +{ + /*init_moves();*/ + + 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); +} + +/* Public functions **********************************************************/ + +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; +} + +Cube +apply_alg(Alg *alg, Cube cube) +{ + return apply_alg_generic(alg, cube, pf_all, true); +} + +Cube +apply_move(Move m, Cube cube) +{ + /*init_moves();*/ + + 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] + }; +} + +static bool +read_mtables_file() +{ + init_env(); + + FILE *f; + char fname[strlen(tabledir)+20]; + int m, b = sizeof(int); + bool r = true; + + /* Table sizes, used for reading and writing files */ + uint64_t me[11] = { + [0] = FACTORIAL12/FACTORIAL8, + [1] = FACTORIAL12/FACTORIAL8, + [2] = FACTORIAL12/FACTORIAL8, + [3] = POW2TO11, + [4] = POW2TO11, + [5] = POW2TO11, + [6] = FACTORIAL8, + [7] = POW3TO7, + [8] = POW3TO7, + [9] = POW3TO7, + [10] = FACTORIAL6 + }; + + 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 +write_mtables_file() +{ + init_env(); + + FILE *f; + char fname[strlen(tabledir)+20]; + int m, b = sizeof(int); + bool r = true; + + /* Table sizes, used for reading and writing files */ + uint64_t me[11] = { + [0] = FACTORIAL12/FACTORIAL8, + [1] = FACTORIAL12/FACTORIAL8, + [2] = FACTORIAL12/FACTORIAL8, + [3] = POW2TO11, + [4] = POW2TO11, + [5] = POW2TO11, + [6] = FACTORIAL8, + [7] = POW3TO7, + [8] = POW3TO7, + [9] = POW3TO7, + [10] = FACTORIAL6 + }; + + 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; +} + +bool +commute(Move m1, Move m2) +{ + static bool initialized = false; + static bool commute_aux[NMOVES][NMOVES]; + + if (!initialized) { + Cube c1, c2; + int i, j; + + 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_aux[i][j] = equal(c1, c2) && i && j; + } + } + + initialized = true; + } + + return commute_aux[m1][m2]; +} + +bool +possible_next(Move m1, Move m2, Move m3) +{ + static bool initialized = false; + static bool paux[NMOVES][NMOVES][NMOVES]; + + if (!initialized) { + int i, j, k; + bool p, q, c; + + for (i = 0; i < NMOVES; i++) { + for (j = 0; j < NMOVES; j++) { + for (k = 0; k < NMOVES; k++) { + p = j && base_move(j) == base_move(k); + q = i && base_move(i) == base_move(k); + c = commute(i, j); + paux[i][j][k] = !(p || (c && q)); + } + } + } + + initialized = true; + } + + return paux[m1][m2][m3]; +} + +void +init_moves() { + static bool initialized = false; + if (initialized) + return; + initialized = true; + + Cube c; + CubeArray arrs; + int i; + unsigned int ui; + Move m; + Alg *equiv_alg[NMOVES]; + + for (i = 0; i < NMOVES; i++) + equiv_alg[i] = new_alg(equiv_alg_string[i]); + + /* 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"); + + for (i = 0; i < NMOVES; i++) + free_alg(equiv_alg[i]); } -- cgit v1.3