#include "moves.h" Cube apply_move_cubearray(Move m, Cube cube, PieceFilter f); /* void sort_cancel_rotate(NissMove *alg, int n, bool inv, int top, int front); */ bool read_ttables_file(); bool write_ttables_file(); /* Transition tables */ 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]; bool commute[NMOVES][NMOVES]; bool possible_next[NMOVES][NMOVES][NMOVES]; Move inverse[NMOVES]; NissMove rotation_algs[24][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 } }, }; 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\'" }; /* 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,[DBR]=2,[DFR]=1,[UFL]=1,[UBL]=2,[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,[DFR]=2,[DBR]=1,[UBL]=1,[UFL]=2,[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 }, }; /* 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, }; bool is_solved_up_to_reorient(Cube cube) { for (int i = 0; i < 25; i++) if (is_solved(apply_alg(rotation_algs[i], cube))) return true; return false; } Cube apply_move_cubearray(Move m, Cube cube, PieceFilter f) { return move_via_arrays((CubeArray) { 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] }, cube, f); } int len(NissMove *alg) { int i; for (i = 0; alg[i].m != NULLMOVE; i++); return i; } int copy_alg(NissMove *src, NissMove *dest) { int i; for (i = 0; src[i].m != NULLMOVE; i++) dest[i] = src[i]; dest[i].m = NULLMOVE; return i; } int invert_alg(NissMove *src, NissMove *dest) { int n = len(src); for (int i = 0; i < n; i++) dest[n-i-1] = (NissMove){.m=inverse[src[i].m], .inverse=src[i].inverse}; dest[n].m = NULLMOVE; return n; } int concat(NissMove *src1, NissMove *src2, NissMove *dest) { int n1 = len(src1), n2 = len(src2); copy_alg(src1, dest); copy_alg(src2, dest+n1); return n1+n2; } /* TODO: all strings start with space?? */ void print_alg(NissMove *alg) { bool niss = false; for (int i = 0; alg[i].m != NULLMOVE; i++) { char *fill = !niss && alg[i].inverse ? " (" : (niss && !alg[i].inverse ? ") " : " "); printf("%s%s", fill, move_string[alg[i].m]); niss = alg[i].inverse; } printf("%s\n", niss ? ")" : ""); } int read_moves(char *str, NissMove *alg, int n) { bool niss = false; int c = 0; for (int i = 0; str[i] && c < n; i++) { if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n') continue; if (str[i] == '(' || str[i] == ')') { if ((niss && str[i] == '(') || (!niss && str[i] == ')')) return -1; niss = !niss; continue; } alg[c].inverse = niss; alg[c].m = NULLMOVE; for (Move j = 0; j < NMOVES; j++) { if (str[i] == move_string[j][0]) { alg[c].m = j; if (alg[c].m <= B && str[i+1]=='w') { alg[c].m += Uw - U; i++; } if (str[i+1]=='2') { alg[c].m += 1; i++; } else if (str[i+1]=='\'' || str[i+1]=='3') { alg[c].m += 2; i++; } c++; break; } } } alg[c].m = NULLMOVE; return c; } /* TODO: rewrite cleanup(). Idea: 1. split alg in normal + inverse part, rewriting each with equiv_moves 2. shift rotations to the end while transforming all moves in between ARGH! this uses transformation! One more reason to merge everything in one file. 3. cancellations */ bool read_ttables_file() { FILE *ttf; long unsigned int me[11] = { factorial12/factorial8, factorial12/factorial8, factorial12/factorial8, pow2to11, pow2to11, pow2to11, factorial8, pow3to7, pow3to7, pow3to7, factorial6 }; if ((ttf = fopen("ttables", "rb")) != NULL) { bool r = true; for (int m = 0; m < NMOVES; m++) { r = r && fread(epose_ttable[m], sizeof(uint16_t), me[0], ttf) == me[0]; r = r && fread(eposs_ttable[m], sizeof(uint16_t), me[1], ttf) == me[1]; r = r && fread(eposm_ttable[m], sizeof(uint16_t), me[2], ttf) == me[2]; r = r && fread(eofb_ttable[m], sizeof(uint16_t), me[3], ttf) == me[3]; r = r && fread(eorl_ttable[m], sizeof(uint16_t), me[4], ttf) == me[4]; r = r && fread(eoud_ttable[m], sizeof(uint16_t), me[5], ttf) == me[5]; r = r && fread(cp_ttable[m], sizeof(uint16_t), me[6], ttf) == me[6]; r = r && fread(coud_ttable[m], sizeof(uint16_t), me[7], ttf) == me[7]; r = r && fread(corl_ttable[m], sizeof(uint16_t), me[8], ttf) == me[8]; r = r && fread(cofb_ttable[m], sizeof(uint16_t), me[9], ttf) == me[9]; r = r && fread(cpos_ttable[m], sizeof(uint16_t), me[10], ttf) == me[10]; } fclose(ttf); return r; } else return false; } bool write_ttables_file() { FILE *ttf; long unsigned int me[11] = { factorial12/factorial8, factorial12/factorial8, factorial12/factorial8, pow2to11, pow2to11, pow2to11, factorial8, pow3to7, pow3to7, pow3to7, factorial6 }; if ((ttf = fopen("ttables", "wb")) != NULL) { bool r = true; for (int m = 0; m < NMOVES; m++) { r = r && fwrite(epose_ttable[m], sizeof(uint16_t), me[0], ttf) == me[0]; r = r && fwrite(eposs_ttable[m], sizeof(uint16_t), me[1], ttf) == me[1]; r = r && fwrite(eposm_ttable[m], sizeof(uint16_t), me[2], ttf) == me[2]; r = r && fwrite(eofb_ttable[m], sizeof(uint16_t), me[3], ttf) == me[3]; r = r && fwrite(eorl_ttable[m], sizeof(uint16_t), me[4], ttf) == me[4]; r = r && fwrite(eoud_ttable[m], sizeof(uint16_t), me[5], ttf) == me[5]; r = r && fwrite(cp_ttable[m], sizeof(uint16_t), me[6], ttf) == me[6]; r = r && fwrite(coud_ttable[m], sizeof(uint16_t), me[7], ttf) == me[7]; r = r && fwrite(corl_ttable[m], sizeof(uint16_t), me[8], ttf) == me[8]; r = r && fwrite(cofb_ttable[m], sizeof(uint16_t), me[9], ttf) == me[9]; r = r && fwrite(cpos_ttable[m], sizeof(uint16_t), me[10],ttf) == me[10]; } fclose(ttf); return r; } else return false; } void init_ttables(bool read, bool write) { /* Generate all move cycles and flips; I do this regardless */ for (int i = 0; i < NMOVES; i++) { if (i == U || i == x || i == y) continue; Cube c = {0}; for (int j = 0; equiv_moves[i][j]; j++) c = apply_move_cubearray(equiv_moves[i][j], c, pf_all); CubeArray arrs = { 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) if (read_ttables_file()) return; /* Initialize transition tables */ for (int m = 0; m < NMOVES; m++) { for (uint16_t i = 0; i < factorial12/factorial8; i++) { epose_ttable[m][i] = apply_move_cubearray(m,(Cube){.epose=i},pf_e).epose; eposs_ttable[m][i] = apply_move_cubearray(m,(Cube){.eposs=i},pf_s).eposs; eposm_ttable[m][i] = apply_move_cubearray(m,(Cube){.eposm=i},pf_m).eposm; } for (uint16_t i = 0; i < pow2to11; i++ ) { eofb_ttable[m][i] = apply_move_cubearray(m,(Cube){.eofb=i},pf_eo).eofb; eorl_ttable[m][i] = apply_move_cubearray(m,(Cube){.eorl=i},pf_eo).eorl; eoud_ttable[m][i] = apply_move_cubearray(m,(Cube){.eoud=i},pf_eo).eoud; } for (uint16_t i = 0; i < pow3to7; i++) { coud_ttable[m][i] = apply_move_cubearray(m,(Cube){.coud=i},pf_co).coud; corl_ttable[m][i] = apply_move_cubearray(m,(Cube){.corl=i},pf_co).corl; cofb_ttable[m][i] = apply_move_cubearray(m,(Cube){.cofb=i},pf_co).cofb; } for (uint16_t i = 0; i < factorial8; i++) cp_ttable[m][i] = apply_move_cubearray(m,(Cube){.cp=i},pf_cp).cp; for (uint16_t i = 0; i < factorial6; i++) cpos_ttable[m][i] = apply_move_cubearray(m,(Cube){.cpos=i},pf_cpos).cpos; } if (write) if (!write_ttables_file()) printf("Error in writing ttables: file not writable\n"); } Cube move_cube(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_alg_filtered(NissMove *alg, Cube cube, PieceFilter f) { Cube ret = {0}; for (int i = 0; alg[i].m != NULLMOVE; i++) if (alg[i].inverse) ret = move_cube(alg[i].m, ret); ret = compose_filtered(cube, inverse_cube(ret), f); for (int i = 0; alg[i].m != NULLMOVE; i++) if (!alg[i].inverse) ret = move_cube(alg[i].m, ret); return ret; } Cube apply_alg(NissMove *alg, Cube cube) { return apply_alg_filtered(alg, cube, pf_all); } void init_aux_tables() { /* Commute */ for (int i = 0; i < NMOVES; i++) for (int j = 0; j < NMOVES; j++) commute[i][j] = equal(move_cube(i, move_cube(j, (Cube){0})), move_cube(j, move_cube(i, (Cube){0}))); /* Possible next (if the sequence i j k is valid) */ for (int i = 0; i < NMOVES; i++) for (int j = 0; j < NMOVES; j++) for (int k = 0; k < NMOVES; k++) possible_next[i][j][k] = (j == 0) || (j != 0 && (j-(j-1)%3) != (k-(k-1)%3) && !(i != 0 && commute[i][j] && (i-(i-1)%3) == (k-(k-1)%3))); /* Inverse */ for (int i = 0; i < NMOVES; i++) inverse[i] = i == NULLMOVE ? NULLMOVE : i + 2 - 2*((i-1)%3); }