path: root/old/2021-02-06/cube.c

#include "cube.h"

typedef struct {
  int ep[12], eofb[12], eorl[12], eoud[12],
      cp[8],  coud[8],  corl[8],  cofb[8],  cpos[6];
} CubeArray;

typedef struct {
  bool epose, eposs, eposm, eofb, eorl, eoud, cp, coud, cofb, corl, cpos;
} PieceFilter;

PieceFilter fAll = {true,true,true,true,true,true,true,true,true,true,true};
PieceFilter cpos_only = { .cpos = true };

void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f);
Cube arrays_to_cube(CubeArray arr, PieceFilter f);
void move_cubearray(Move m, CubeArray *arr, PieceFilter f);
Cube move_via_array(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];

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" };
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]=2,[UFL]=1,[DBL]=1,[DFL]=2},
    [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,
};

int epe_solved[] = {FR, FL, BL, BR};
int eps_solved[] = {UL, UR, DL, DR};
int epm_solved[] = {UF, UB, DF, DB};

Cube blank_cube() {
  Cube c = {0};
  return c;
}

void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f) {
  /* ep is the hardest */
  if (f.epose || f.eposs || f.eposm)
    for (int i = 0; i < 12; i++) arr->ep[i] = -1;
  if (f.epose) {
    int epe[4], epose[12];
    index_to_perm(cube.epose % factorial(4), 4, epe);
    index_to_subset(cube.epose / factorial(4), 12, 4, epose);
    for (int i = 0, ie = 0; i < 12; i++)
      if (epose[i]) arr->ep[i] = epe_solved[epe[ie++]];
  }
  if (f.eposs) {
    int eps[4], eposs[12];
    index_to_perm(cube.eposs % factorial(4), 4, eps);
    index_to_subset(cube.eposs / factorial(4), 12, 4, eposs);
    for (int i = 0; i < 4; i++) swap(&eposs[eps_solved[i]], &eposs[i+8]);
    for (int i = 0, is = 0; i < 12; i++)
      if (eposs[i]) arr->ep[i] = eps_solved[eps[is++]]; 
  }
  if (f.eposm) {
    int epm[4], eposm[12];
    index_to_perm(cube.eposm % factorial(4), 4, epm);
    index_to_subset(cube.eposm / factorial(4), 12, 4, eposm);
    for (int i = 0; i < 4; i++) swap(&eposm[epm_solved[i]], &eposm[i+8]);
    for (int 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);
}

Cube arrays_to_cube(CubeArray arr, PieceFilter f) {
  Cube ret = {0};

  /* Again, ep is the hardest part */
  if (f.epose) {
    int epe[4], epose[12] = {0,0,0,0,0,0,0,0,0,0,0,0};
    for (int i = 0, ie = 0; i < 12; i++)
      for (int j = 0; j < 4; j++)
        if (arr.ep[i] == epe_solved[j])
          { epe[ie++] = j; epose[i] = 1; }
    ret.epose = factorial(4)*subset_to_index(epose,12,4)+perm_to_index(epe,4);
  }
  if (f.eposs) {
    int eps[4], eposs[12] = {0,0,0,0,0,0,0,0,0,0,0,0};
    for (int i = 0, is = 0; i < 12; i++)
      for (int j = 0; j < 4; j++)
        if (arr.ep[i] == eps_solved[j])
          { eps[is++] = j; eposs[i] = 1; }
    for (int i = 0; i < 4; i++) swap(&eposs[eps_solved[i]], &eposs[i+8]);
    ret.eposs = factorial(4)*subset_to_index(eposs,12,4)+perm_to_index(eps,4);
  }
  if (f.eposm) {
    int epm[4], eposm[12] = {0,0,0,0,0,0,0,0,0,0,0,0};
    for (int i = 0, im = 0; i < 12; i++)
      for (int j = 0; j < 4; j++)
        if (arr.ep[i] == epm_solved[j])
          { epm[im++] = j; eposm[i] = 1; }
    for (int i = 0; i < 4; i++) swap(&eposm[epm_solved[i]], &eposm[i+8]);
    ret.eposm = factorial(4)*subset_to_index(eposm,12,4)+perm_to_index(epm,4);
  }
  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;
}

void move_cubearray(Move m, CubeArray *arr, PieceFilter f) {
  if (f.epose || f.eposs || f.eposm)
    apply_permutation(edge_cycle[m], arr->ep, 12);
  if (f.eofb) {
    apply_permutation(edge_cycle[m], arr->eofb, 12);
    sum_arrays_mod(eofb_flipped[m],  arr->eofb, 12, 2);
  }
  if (f.eofb) {
    apply_permutation(edge_cycle[m], arr->eorl, 12);
    sum_arrays_mod(eorl_flipped[m],  arr->eorl, 12, 2);
  }
  if (f.eofb) {
    apply_permutation(edge_cycle[m], arr->eoud, 12);
    sum_arrays_mod(eoud_flipped[m],  arr->eoud, 12, 2);
  }
  if (f.cp)
    apply_permutation(corner_cycle[m], arr->cp,   8);
  if (f.coud) {
    apply_permutation(corner_cycle[m], arr->coud, 8);
    sum_arrays_mod(coud_flipped[m],    arr->coud, 8, 3);
  }
  if (f.corl) {
    apply_permutation(corner_cycle[m], arr->corl, 8);
    sum_arrays_mod(corl_flipped[m],    arr->corl, 8, 3);
  }
  if (f.cofb) {
    apply_permutation(corner_cycle[m], arr->cofb, 8);
    sum_arrays_mod(cofb_flipped[m],    arr->cofb, 8, 3);
  }
  if (f.cpos)
    apply_permutation(center_cycle[m], arr->cpos, 6);
}

Cube move_via_array(Move m, Cube cube, PieceFilter f) {
  CubeArray arr = {0};
  cube_to_arrays(cube, &arr, f);
  move_cubearray(m, &arr, f);
  return arrays_to_cube(arr, f);
}

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;
}

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;
}

bool solvable(Cube cube) {
  /* Since we memorize orientation truncating the last digit, we only need to
   * check that the permutations have the correct sign. */
  CubeArray arr = {0};
  cube_to_arrays(cube, &arr, fAll);
  return (perm_sign(arr.ep,12) ^ perm_sign(arr.cpos,6)) == perm_sign(arr.cp,8);
}

bool is_solved(Cube cube, bool reorient) {
  if (!reorient || !cube.cpos)
    return !cube.eofb  && !cube.coud  && !cube.cp &&
           !cube.epose && !cube.eposs && !cube.eposm;

  bool ret = false;
  for (int i = x; i <= z3; i++) {
    ret = ret || is_solved(move_cube(i, cube), false);
    for (int j = x; j <= z3; j++)
      ret = ret || is_solved(move_cube(i, move_cube(j, cube)), false);
  }
  return ret;
}

void print_cube(Cube cube) {
  CubeArray arr = {0};
  cube_to_arrays(cube, &arr, fAll);

  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");
}

/* TODO: all strings start with space?? */
void print_moves(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;
}

/* Helper function for cleanup. alg must contain only basic moves, no 2 or '.
   top and front describe an admissible orientation of the cube. */
void sort_cancel_rotate(NissMove *alg, int n, bool inv, int top, int front) {
  int c = 0, i = 0;
  NissMove aux[n+3];
  aux[0].m = NULLMOVE;

  while (i < n && alg[i].m != NULLMOVE) {
    int j = i;
    while (j < n && commute[alg[i].m][alg[j].m]) j++;
    Move base = 6*((alg[i].m-1)/6);
    int t1 = 0, t2 = 0;
    for (int k = i; k < j; k++)
      if (alg[k].m == base+1) t1 = (t1+1)%4;
      else                       t2 = (t2+1)%4;
    if (t1) { aux[c].inverse = inv; aux[c].m = base+t1;   c++; }
    if (t2) { aux[c].inverse = inv; aux[c].m = base+t2+3; c++; }
    i = j;
  }
  aux[c].m = NULLMOVE;

  CubeArray q;
  cube_to_arrays(blank_cube(), &q, cpos_only);
  /* First we try to rotate in one move, then we try an x or y rotation
     followed by a z rotation */
  for (int r = x; r <= z3; r++) {
    move_cubearray(r, &q, cpos_only);
    if (q.cpos[F_center] == front && q.cpos[U_center] == top) {
      aux[c].inverse = inv; aux[c].m = r;

      aux[++c].m = NULLMOVE;
      copy_alg(aux, alg);
      return;
    }
    move_cubearray(inverse[r], &q, cpos_only);
  }
  for (int r = x; r <= y3; r++) {
    move_cubearray(r, &q, cpos_only);
    if (q.cpos[F_center] == front) {
      aux[c].inverse = inv; aux[c++].m = r;
      break;
    }
    move_cubearray(inverse[r], &q, cpos_only);
  }
  for (int r = z; r <= z3; r++) {
    move_cubearray(r, &q, cpos_only);
    if (q.cpos[U_center] == top) {
      aux[c].inverse = inv; aux[c++].m = r;
      break;
    }
    move_cubearray(inverse[r], &q, cpos_only);
  }

  aux[c].m = NULLMOVE;
  copy_alg(aux, alg);
}

void cleanup(NissMove *alg, int n) {
  int count_n = 0, count_i = 0, *count;
  NissMove aux_n[n+1], aux_i[n+1], *aux;
  CubeArray cube_n, cube_i, *cube;
  cube_to_arrays(blank_cube(), &cube_n, cpos_only);
  cube_to_arrays(blank_cube(), &cube_i, cpos_only);
  
  for (int i = 0; count_n + count_i < n && alg[i].m != NULLMOVE; i++) {
    if (alg[i].inverse) { count = &count_i; aux = aux_i; cube = &cube_i; }
    else                { count = &count_n; aux = aux_n; cube = &cube_n; }
    
    for (int j = 0; equiv_moves[alg[i].m][j]; j++) {
      Move m = equiv_moves[alg[i].m][j];
      aux[*count].inverse = alg[i].inverse;
      move_cubearray(m, cube, cpos_only);
      if (m == U) aux[(*count)++].m = 3 * cube->cpos[0] + 1;
    }
  }

  aux_n[count_n].m = NULLMOVE;
  aux_i[count_i].m = NULLMOVE;
  sort_cancel_rotate(aux_n, count_n, false, cube_n.cpos[0], cube_n.cpos[4]); 
  sort_cancel_rotate(aux_i, count_i, true,  cube_i.cpos[0], cube_n.cpos[4]); 
  copy_alg(aux_n, alg);
  copy_alg(aux_i, alg+count_n);
}

Cube inverse_cube(Cube cube) {
  CubeArray arr = {0}, inv = {0};
  cube_to_arrays(cube, &arr, fAll);

  for (int 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 (int i = 0; i < 8; i++) {
    inv.cp[arr.cp[i]] = i;
    inv.coud[arr.cp[i]] = arr.coud[i];
    inv.corl[arr.cp[i]] = arr.corl[i];
    inv.cofb[arr.cp[i]] = arr.cofb[i];
  }
  for (int i = 0; i < 6; i++)
    inv.cpos[arr.cpos[i]] = i;

  return arrays_to_cube(inv, fAll);
}

bool read_ttables_file() {
  FILE *ttf;
  if ((ttf = fopen("ttables", "rb")) != NULL) {
    for (int m = 0; m < NMOVES; m++) {
      fread(epose_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
      fread(eposs_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
      fread(eposm_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
      fread(eofb_ttable[m],  sizeof(uint16_t), pow2to11,               ttf);
      fread(eorl_ttable[m],  sizeof(uint16_t), pow2to11,               ttf);
      fread(eoud_ttable[m],  sizeof(uint16_t), pow2to11,               ttf);
      fread(cp_ttable[m],    sizeof(uint16_t), factorial8,             ttf);
      fread(coud_ttable[m],  sizeof(uint16_t), pow3to7,                ttf);
      fread(corl_ttable[m],  sizeof(uint16_t), pow3to7,                ttf);
      fread(cofb_ttable[m],  sizeof(uint16_t), pow3to7,                ttf);
      fread(cpos_ttable[m],  sizeof(uint16_t), factorial6,             ttf);
    }
    fclose(ttf);
    return true;
  } else return false;
}

bool write_ttables_file() {
  FILE *ttf;
  if ((ttf = fopen("ttables", "wb")) != NULL) {
    for (int m = 0; m < NMOVES; m++) {
      fwrite(epose_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
      fwrite(eposs_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
      fwrite(eposm_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
      fwrite(eofb_ttable[m],  sizeof(uint16_t), pow2to11,               ttf);
      fwrite(eorl_ttable[m],  sizeof(uint16_t), pow2to11,               ttf);
      fwrite(eoud_ttable[m],  sizeof(uint16_t), pow2to11,               ttf);
      fwrite(cp_ttable[m],    sizeof(uint16_t), factorial8,             ttf);
      fwrite(coud_ttable[m],  sizeof(uint16_t), pow3to7,                ttf);
      fwrite(corl_ttable[m],  sizeof(uint16_t), pow3to7,                ttf);
      fwrite(cofb_ttable[m],  sizeof(uint16_t), pow3to7,                ttf);
      fwrite(cpos_ttable[m],  sizeof(uint16_t), factorial6,             ttf);
    }
    fclose(ttf);
    return true;
  } 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;

    CubeArray arr = {0};
    cube_to_arrays(blank_cube(), &arr, fAll);
    for (int j = 0; equiv_moves[i][j]; j++)
      move_cubearray(equiv_moves[i][j], &arr, fAll);

    intarrcopy(arr.ep,   edge_cycle[i],   12);
    intarrcopy(arr.eofb, eofb_flipped[i], 12);
    intarrcopy(arr.eorl, eorl_flipped[i], 12);
    intarrcopy(arr.eoud, eoud_flipped[i], 12);
    intarrcopy(arr.cp,   corner_cycle[i],  8);
    intarrcopy(arr.coud, coud_flipped[i],  8);
    intarrcopy(arr.corl, corl_flipped[i],  8);
    intarrcopy(arr.cofb, cofb_flipped[i],  8);
    intarrcopy(arr.cpos, center_cycle[i],  6);
  }

  if (read)
    if (read_ttables_file())
      return;

  /* Initialize transition tables */
  Cube c = {0};
  PieceFilter fe  = {.epose=true}, fs = {.eposs=true}, fm = {.eposm=true};
  PieceFilter feo = { .eofb = true, .eorl = true, .eoud = true };
  PieceFilter fcp = { .cp = true };
  PieceFilter fco = { .cofb = true, .corl = true, .coud = true };
  PieceFilter fcc = { .cpos = true };
  for (int m = 0; m < NMOVES; m++) {
    for (uint16_t i = 0; i < factorial12/factorial8; i++) {
      c.epose = i; epose_ttable[m][i] = move_via_array(m, c, fe).epose;
      c.eposs = i; eposs_ttable[m][i] = move_via_array(m, c, fs).eposs;
      c.eposm = i; eposm_ttable[m][i] = move_via_array(m, c, fm).eposm;
    }
    for (uint16_t i = 0; i < pow2to11; i++ ) {
      c.eofb = i; eofb_ttable[m][i] = move_via_array(m, c, feo).eofb;
      c.eorl = i; eorl_ttable[m][i] = move_via_array(m, c, feo).eorl;
      c.eoud = i; eoud_ttable[m][i] = move_via_array(m, c, feo).eoud;
    }
    for (uint16_t i = 0; i < factorial8; i++) {
      c.cp = i; cp_ttable[m][i] = move_via_array(m, c, fcp).cp;
    }
    for (uint16_t i = 0; i < pow3to7; i++) {
      c.coud = i; coud_ttable[m][i] = move_via_array(m, c, fco).coud;
      c.corl = i; corl_ttable[m][i] = move_via_array(m, c, fco).corl;
      c.cofb = i; cofb_ttable[m][i] = move_via_array(m, c, fco).cofb;
    }
    for (uint16_t i = 0; i < factorial6; i++) {
      c.cpos = i; cpos_ttable[m][i] = move_via_array(m, c, fcc).cpos;
    }
  }

  if (write) write_ttables_file();
}

Cube move_cube(Move m, Cube cube) {
  Cube moved = cube;

  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 compose(Cube c2, Cube c1) {
  /* This is basically the same as the move_cubearray function above */
  CubeArray arr2 = {0}, arr1 = {0};
  cube_to_arrays(c2, &arr2, fAll);
  cube_to_arrays(c1, &arr1, fAll);

  apply_permutation(arr2.ep,   arr1.ep,   12);
  apply_permutation(arr2.ep,   arr1.eofb, 12);
  apply_permutation(arr2.ep,   arr1.eorl, 12);
  apply_permutation(arr2.ep,   arr1.eoud, 12);
  sum_arrays_mod(arr2.eofb,    arr1.eofb, 12, 2);
  sum_arrays_mod(arr2.eorl,    arr1.eorl, 12, 2);
  sum_arrays_mod(arr2.eoud,    arr1.eoud, 12, 2);
  apply_permutation(arr2.cp,   arr1.cp,   8);
  apply_permutation(arr2.cp,   arr1.coud, 8);
  apply_permutation(arr2.cp,   arr1.corl, 8);
  apply_permutation(arr2.cp,   arr1.cofb, 8);
  sum_arrays_mod(arr2.coud,    arr1.coud, 8, 3);
  sum_arrays_mod(arr2.corl,    arr1.corl, 8, 3);
  sum_arrays_mod(arr2.cofb,    arr1.cofb, 8, 3);
  apply_permutation(arr2.cpos, arr1.cpos, 6);

  return arrays_to_cube(arr1, fAll);
}

Cube apply_alg(NissMove *alg, Cube cube) {
  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(cube, inverse_cube(ret));

  for (int i = 0; alg[i].m != NULLMOVE; i++)
    if (!alg[i].inverse)
      ret = move_cube(alg[i].m, ret);
  return ret;
}

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, blank_cube())),
                            move_cube(j, move_cube(i, blank_cube())));

  /* 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 == 0 ? 0 : i + 2 - 2*((i-1)%3);
}