path: root/src/coord.c

#include "coord.h"

static uint64_t    index_eofb(Cube cube);
static uint64_t    index_eofbepos(Cube cube);
static uint64_t    index_epud(Cube cube);
static uint64_t    index_coud(Cube cube);
static uint64_t    index_corners(Cube cube);
static uint64_t    index_cp(Cube cube);
static uint64_t    index_cphtr(Cube cube);
static uint64_t    index_cornershtr(Cube cube);
static uint64_t    index_cornershtrfin(Cube cube);
static uint64_t    index_drud(Cube cube);
static uint64_t    index_drud_eofb(Cube cube);
static uint64_t    index_htr_drud(Cube cube);
static uint64_t    index_htrfin(Cube cube);
static uint64_t    index_cpud_separate(Cube cube);

static uint64_t    move_eofb(Move m, uint64_t ind);
static uint64_t    move_eofbepos(Move m, uint64_t ind);
static uint64_t    move_epud(Move m, uint64_t ind);
static uint64_t    move_coud(Move m, uint64_t ind);
static uint64_t    move_corners(Move m, uint64_t ind);
static uint64_t    move_cp(Move m, uint64_t ind);
static uint64_t    move_cphtr(Move m, uint64_t ind);
static uint64_t    move_cornershtr(Move m, uint64_t ind);
static uint64_t    move_cornershtrfin(Move m, uint64_t ind);
static uint64_t    move_drud(Move m, uint64_t ind);
static uint64_t    move_drud_eofb(Move m, uint64_t ind);
static uint64_t    move_htr_drud(Move m, uint64_t ind);
static uint64_t    move_htrfin(Move m, uint64_t ind);
static uint64_t    move_cpud_separate(Move m, uint64_t ind);

static void        init_cphtr_cosets();
static void        init_cphtr_left_cosets_bfs(int i, int c);
static void        init_cphtr_right_cosets_color(int i, int c);
static void        init_cpud_separate();
static void        init_cornershtrfin();
static void        init_htr_eposs();


/* All sorts of useful costants and tables  **********************************/

static int              cphtr_left_cosets[FACTORIAL8];
static int              cphtr_right_cosets[FACTORIAL8];
static int              cphtr_right_rep[BINOM8ON4*6];
int                     cpud_separate_ind[FACTORIAL8];
int                     cpud_separate_ant[BINOM8ON4];
static int              cornershtrfin_ind[FACTORIAL8];
int                     cornershtrfin_ant[24*24/6];
static int              htr_eposs_ind[BINOM12ON4];
static int              htr_eposs_ant[BINOM8ON4];

/* Coordinates and their implementation **************************************/

Coordinate
coord_eofb = {
	.index  = index_eofb,
	.max    = POW2TO11,
	.move   = move_eofb,
};

Coordinate
coord_eofbepos = {
	.index  = index_eofbepos,
	.max    = POW2TO11 * BINOM12ON4,
	.move   = move_eofbepos,
};

Coordinate
coord_coud = {
	.index  = index_coud,
	.max    = POW3TO7,
	.move   = move_coud,
};

Coordinate
coord_corners = {
	.index  = index_corners,
	.max    = POW3TO7 * FACTORIAL8,
	.move   = move_corners,
};

Coordinate
coord_cp = {
	.index  = index_cp,
	.max    = FACTORIAL8,
	.move   = move_cp,
};

Coordinate
coord_cphtr = {
	.index  = index_cphtr,
	.max    = BINOM8ON4 * 6,
	.move   = move_cphtr,
};

Coordinate
coord_cornershtr = {
	.index  = index_cornershtr,
	.max    = POW3TO7 * BINOM8ON4 * 6,
	.move   = move_cornershtr,
};

Coordinate
coord_cornershtrfin = {
	.index  = index_cornershtrfin,
	.max    = 24*24/6,
	.move   = move_cornershtrfin,
};

Coordinate
coord_epud = {
	.index  = index_epud,
	.max    = FACTORIAL8,
	.move   = move_epud,
};

Coordinate
coord_drud = {
	.index  = index_drud,
	.max    = POW2TO11 * POW3TO7 * BINOM12ON4,
	.move   = move_drud,
};

Coordinate
coord_htr_drud = {
	.index  = index_htr_drud,
	.max    = BINOM8ON4 * 6 * BINOM8ON4,
	.move   = move_htr_drud,
};

Coordinate
coord_htrfin = {
	.index  = index_htrfin,
	.max    = 24 * 24 * 24 *24 * 24 / 6, /* should be /12 but it's ok */
	.move   = move_htrfin,
};

Coordinate
coord_drud_eofb = {
	.index  = index_drud_eofb,
	.max    = POW3TO7 * BINOM12ON4,
	.move   = move_drud_eofb,
};

Coordinate
coord_cpud_separate = {
	.index  = index_cpud_separate,
	.max    = BINOM8ON4,
	.move   = move_cpud_separate,
};

/* Indexers ******************************************************************/

static uint64_t
index_eofb(Cube cube)
{
	return cube.eofb;
}

static uint64_t
index_eofbepos(Cube cube)
{
	return (cube.epose / FACTORIAL4) * POW2TO11 + cube.eofb;
}

static uint64_t
index_epud(Cube cube)
{
	uint64_t ret;
	CubeArray *arr = new_cubearray(cube, pf_ep);

	ret = perm_to_index(arr->ep, 8);
	free_cubearray(arr, pf_ep);

	return ret;
}

static uint64_t
index_coud(Cube cube)
{
	return cube.coud;
}

static uint64_t
index_corners(Cube cube)
{
	return cube.coud * FACTORIAL8 + cube.cp;
}

static uint64_t
index_cp(Cube cube)
{
	return cube.cp;
}

static uint64_t
index_cphtr(Cube cube)
{
	return cphtr_right_cosets[cube.cp];
}

static uint64_t
index_cornershtr(Cube cube)
{
	return cube.coud * BINOM8ON4 * 6 + index_cphtr(cube);
}

static uint64_t
index_cornershtrfin(Cube cube)
{
	return cornershtrfin_ind[cube.cp];
}

static uint64_t
index_drud(Cube cube)
{
	uint64_t a, b, c;

	a = cube.eofb;
	b = cube.coud;
	c = cube.epose / FACTORIAL4;

	b *= POW2TO11;
	c *= POW2TO11 * POW3TO7;

	return a + b + c;
}

static uint64_t
index_drud_eofb(Cube cube)
{
	return index_drud(cube) / POW2TO11;
}

static uint64_t
index_htr_drud(Cube cube)
{
	uint64_t a, b;

	a = index_cphtr(cube);
	b = htr_eposs_ind[cube.eposs/24];

	return a * BINOM8ON4 + b;
}

static uint64_t
index_htrfin(Cube cube)
{
	uint64_t epe, eps, epm, cp, ep;

	epe = cube.epose % 24;
	eps = cube.eposs % 24;
	epm = cube.eposm % 24;
	ep = (epe * 24 + eps) *24 + epm;
	cp = index_cornershtrfin(cube);

	return cp * 24 * 24 * 24 + ep;
}

static uint64_t
index_cpud_separate(Cube cube)
{
	return cpud_separate_ind[cube.cp];
}

/* Coordinate movers *********************************************************/

static uint64_t
move_eofb(Move m, uint64_t ind)
{
	return eofb_mtable[m][ind];
}

static uint64_t
move_eofbepos(Move m, uint64_t ind)
{
	uint64_t a, b;

	a = epose_mtable[m][(ind / POW2TO11)*24];
	b = eofb_mtable[m][ind % POW2TO11];

	return (a/24) * POW2TO11 + b;
}

static uint64_t
move_epud(Move m, uint64_t ind)
{
	/* TODO: save to file? */
	static bool initialized = false;
	static int a[12] = { [8] = 8, [9] = 9, [10] = 10, [11] = 11 };
	static int shortlist[NMOVES] = {
		[U] = 0, [U2] = 1, [U3] = 2, [D] = 3, [D2] = 4, [D3] = 5,
		[R2] = 6, [L2] = 7, [F2] = 8, [B2] = 9
	};
	static uint64_t aux[10][FACTORIAL8];
	uint64_t ui;
	int j;
	Move mj;
	Cube c;
	CubeArray *arr, *auxarr;

	if (!moveset_drud.allowed(m)) {
		fprintf(stderr, "Move not allowed for epud\n"
		                "This is a bug, please report\n");
		return coord_epud.max;
	}

	if (!initialized) {
		auxarr = malloc(sizeof(CubeArray));
		auxarr->ep = a;
		for (ui = 0; ui < coord_epud.max; ui++) {
			index_to_perm(ui, 8, a);
			c = arrays_to_cube(auxarr, pf_ep);
			for (j = 0; moveset_drud.sorted_moves[j] != NULLMOVE;
			    j++) {
				mj = moveset_drud.sorted_moves[j];
				arr = new_cubearray(apply_move(mj, c), pf_ep);
				aux[shortlist[mj]][ui] =
				    perm_to_index(arr->ep, 8);
				free_cubearray(arr, pf_ep);
			}
		}
		free(auxarr);

		initialized = true;
	}

	return aux[shortlist[m]][ind];
}

static uint64_t
move_coud(Move m, uint64_t ind)
{
	return coud_mtable[m][ind];
}

static uint64_t
move_corners(Move m, uint64_t ind)
{
	uint64_t a, b;

	a = coud_mtable[m][ind / FACTORIAL8];
	b = cp_mtable[m][ind % FACTORIAL8];

	return a * FACTORIAL8 + b;
}

static uint64_t
move_cp(Move m, uint64_t ind)
{
	return cp_mtable[m][ind];
}

static uint64_t
move_cphtr(Move m, uint64_t ind)
{
	static bool initialized = false;
	static uint64_t aux[NMOVES][BINOM8ON4*6];
	uint64_t ui;
	Move j;

	if (!initialized) {
		for (ui = 0; ui < BINOM8ON4*6; ui++)
			for (j = U; j < NMOVES; j++)
				aux[j][ui] = index_cphtr(
				    cp_mtable[j][cphtr_right_rep[ui]]);

		initialized = true;
	}

	return aux[m][ind];
}

static uint64_t
move_cornershtr(Move m, uint64_t ind)
{
	uint64_t a, b;

	a = coud_mtable[m][ind/(BINOM8ON4 * 6)];
	b = move_cphtr(m, ind % (BINOM8ON4 * 6));

	return a * BINOM8ON4 * 6 + b;
}

static uint64_t
move_cornershtrfin(Move m, uint64_t ind)
{
	int a;

	a = cp_mtable[m][cornershtrfin_ant[ind]];

	return cornershtrfin_ind[a];
}

static uint64_t
move_drud(Move m, uint64_t ind)
{
	uint64_t a, b, c;

	a = eofb_mtable[m][ind % POW2TO11];
	b = coud_mtable[m][(ind / POW2TO11) % POW3TO7];
	c = epose_mtable[m][ind / (POW2TO11 * POW3TO7)];

	return a + (b + c * POW3TO7) * POW2TO11;
}

static uint64_t
move_drud_eofb(Move m, uint64_t ind)
{
	uint64_t a, b;

	a = coud_mtable[m][ind % POW3TO7];
	b = epose_mtable[m][(ind / POW3TO7) * 24] / 24;

	return a + b * POW3TO7;
}

static uint64_t
move_htr_drud(Move m, uint64_t ind)
{
	uint64_t a, b;

	a = move_cphtr(m, ind/BINOM8ON4);
	b = eposs_mtable[m][htr_eposs_ant[ind%BINOM8ON4]];

	return a*BINOM8ON4 + htr_eposs_ind[b/24];
}

static uint64_t
move_htrfin(Move m, uint64_t ind)
{
	uint64_t a, b, bm, bs, be;

	a = move_cornershtrfin(m, ind % (24*24*24));
	bm = eposm_mtable[m][ind%24] % 24;
	bs = eposs_mtable[m][(ind/24)%24] % 24;
	be = epose_mtable[m][ind/(24*24)] % 24;
	b = (be * 24 + bs) * 24 + bm;

	return a * (24*24*24) + b;
}

static uint64_t
move_cpud_separate(Move m, uint64_t ind)
{
	return cpud_separate_ind[cp_mtable[m][cpud_separate_ant[ind]]];
}

/* Init functions implementation *********************************************/

/*
 * There is certainly a better way to do this, but for now I just use
 * a "graph coloring" algorithm to compute the left cosets, and I compose
 * with every possible cp to get the right cosets (it is possible that I am
 * mixing up left and right).
 * 
 * For doing it better "Mathematically", we need 3 things:
 *   - Checking that cp separates the orbits (UFR,UBL,DFL,DBR) and the other
 *     This is easy and it is done in the commented function cphtr_cp().
 *   - Check that there is no ep/cp parity
 *   - Check that we are not in the "3c" case; this is the part I don't
 *     know how to do.
 */
static void
init_cphtr_cosets()
{
	unsigned int i; 
	int c = 0, d = 0;

	for (i = 0; i < FACTORIAL8; i++) {
		cphtr_left_cosets[i]  = -1;
		cphtr_right_cosets[i] = -1;
	}

	/* First we compute left cosets with a bfs */
	for (i = 0; i < FACTORIAL8; i++)
		if (cphtr_left_cosets[i] == -1)
			init_cphtr_left_cosets_bfs(i, c++);

	/* Then we compute right cosets using compose() */
	for (i = 0; i < FACTORIAL8; i++)
		if (cphtr_right_cosets[i] == -1)
			init_cphtr_right_cosets_color(i, d++);
}

static void
init_cphtr_left_cosets_bfs(int i, int c)
{
	int j, jj, next[FACTORIAL8], next2[FACTORIAL8], n, n2;

	Move k;

	n = 1;
	next[0] = i;
	cphtr_left_cosets[i] = c;

	while (n != 0) {
		for (j = 0, n2 = 0; j < n; j++) {
			for (k = U2; k < B3; k++) {
				if (!moveset_htr.allowed(k))
					continue;
				jj = apply_move(k, (Cube){ .cp = next[j] }).cp;

				if (cphtr_left_cosets[jj] == -1) {
					cphtr_left_cosets[jj] = c;
					next2[n2++] = jj;
				}
			}
		}

		for (j = 0; j < n2; j++)
			next[j] = next2[j];
		n = n2;
	}
}

static void
init_cphtr_right_cosets_color(int i, int d)
{
	int cp;
	unsigned int j;

	cphtr_right_rep[d] = i;
	for (j = 0; j < FACTORIAL8; j++) {
		if (cphtr_left_cosets[j] == 0) {
			cp = compose((Cube){.cp = i}, (Cube){.cp = j}).cp;
			cphtr_right_cosets[cp] = d;
		}
	}
}

static void
init_cpud_separate()
{
	unsigned int ui;
	int i, co[8];

	for (ui = 0; ui < FACTORIAL8; ui++) {
		for (i = 0; i < 8; i++)
			co[i] = what_corner_at((Cube){.cp=ui},i)>UBR ?  1 : 0;
		cpud_separate_ind[ui] = subset_to_index(co, 8, 4);
		cpud_separate_ant[cpud_separate_ind[ui]] = ui;
	}
}

static void
init_cornershtrfin()
{
	unsigned int i, j;
	int n, c;
	Move m;

	for (i = 0; i < FACTORIAL8; i++)
		cornershtrfin_ind[i] = -1;
	cornershtrfin_ind[0] = 0;

	/* 10-pass, I think 5 is enough, but just in case */
	n = 1;
	for (i = 0; i < 10; i++) {
		for (j = 0; j < FACTORIAL8; j++) {
			if (cornershtrfin_ind[j] == -1)
				continue;
			for (m = U; m < NMOVES; m++) {
				if (moveset_htr.allowed(m)) {
					c = apply_move(m, (Cube){.cp = j}).cp;
					if (cornershtrfin_ind[c] == -1) {
						cornershtrfin_ind[c] = n;
						cornershtrfin_ant[n] = c;
						n++;
					}
				}
			}
		}
	}
}

void
init_htr_eposs()
{
	int ep[12], ep2[12];
	int eps_solved[4] = {UL, UR, DL, DR};
	unsigned int i, j;

	for (i = 0; i < BINOM12ON4; i++) {
		for (j = 0; j < 12; j++)
			ep[j] = ep2[j] = 0;
		epos_to_partial_ep(i*24, ep, eps_solved);
		for (j = 0; j < 8; j++)
			ep2[j/2 + 4*(j%2)] = ep[j] ? 1 : 0;
		htr_eposs_ind[i] = subset_to_index(ep2, 8, 4);
		htr_eposs_ant[htr_eposs_ind[i]] = i*24;
	}
}

void
init_coord()
{
	static bool initialized = false;
	if (initialized)
		return;
	initialized = true;

	init_trans();

	init_cphtr_cosets();
	init_cornershtrfin();
	init_htr_eposs();
	init_cpud_separate();
}