// PllAttack.cpp : Defines the entry point for the console application.
// By Bruce Norskog
// Finds PLL orderings for a PLL attack to end up with a solved cube,
// given exact permutations for one's specific PLLs.

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef unsigned char UBYTE;
typedef unsigned short USHORT;
typedef unsigned int UINT;

const double THIRTEEN_FACTORIAL = 13.0*12.0*11.0*90.0*40320.0;

USHORT apply_pll[288][21];
USHORT plls[21];

void search (bool allow_AUF, bool show_solutions, double startval = 0.0, double endval = THIRTEEN_FACTORIAL);
void swap (int n1, int n2, UBYTE* p);
void three_cycle (int n1, int n2, int n3, UBYTE* p);
void calc_plls ();
void init_tables ();
UINT get_perm_number (const UBYTE* pcorner, const UBYTE* pedge);
void unpack_perm_number (UINT x, UBYTE* pcorner, UBYTE* pedge);
UINT perm_n_pack (UINT n, const UBYTE* array_in);
void perm_n_unpack (UINT n, UINT idx, UBYTE* array_out);
void perm_n_unpackx (UINT n, double idx, UBYTE* array_out);
int get_parity (int n, UINT x);

int
_tmain(int argc, _TCHAR* argv[])
{
#if 0
	int i;
	UBYTE tc[4], te[4];
#endif
	calc_plls ();
	init_tables ();
#if 0
	//test: Apply PLLs in order.
	UINT x = 0;
	for (i = 0; i < 21; ++i) {
		x = apply_pll[x][i];
		unpack_perm_number (x, &tc[0], &te[0]);
	}
	printf ("Test result: %u\n", x);
#endif
	search (false, true);
	return 0;
}

void
search (bool allow_AUF, bool show_solutions, double startval, double endval)
{
	UBYTE ordering[13];
	double d;
	int i;
	double start;
	modf (startval, &start);	//Ensure we use integer values.
	UINT x = 0;
	UINT count = 0;
	for (d = start; d < endval; d += 1.0) {
		if (fmod (d, 100000000.0) == 0.0) {
			static char buf[80];
			sprintf (&buf[0], "title search %g %u\n", d, count);
			system (&buf[0]);
		}
		perm_n_unpackx (13, d, &ordering[0]);
		x = 0;
		for (i = 0; i < 13; ++i) {
			switch (ordering[i]) {
			case 0:
				x = apply_pll[x][0];	//Aa
				x = apply_pll[x][1];	//Ab
				break;
			case 1:
				x = apply_pll[x][2];	//E
				break;
			case 2:
				x = apply_pll[x][3];	//F
				break;
			case 3:
				x = apply_pll[x][4];	//Ga
				x = apply_pll[x][5];	//Gb
				x = apply_pll[x][6];	//Gc
				x = apply_pll[x][7];	//Gd
				break;
			case 4:
				x = apply_pll[x][8];	//H
				break;
			case 5:
				x = apply_pll[x][9];	//Ja
				x = apply_pll[x][10];	//Jb
				break;
			case 6:
				x = apply_pll[x][11];	//Na
				x = apply_pll[x][12];	//Nb
				break;
			case 7:
				x = apply_pll[x][13];	//Ra
				x = apply_pll[x][14];	//Rb
				break;
			case 8:
				x = apply_pll[x][15];	//T
				break;
			case 9:
				x = apply_pll[x][16];	//Ua
				x = apply_pll[x][17];	//Ub
				break;
			case 10:
				x = apply_pll[x][18];	//V
				break;
			case 11:
				x = apply_pll[x][19];	//Y
				break;
			case 12:
				x = apply_pll[x][20];	//Z
				break;
			}
		}
		bool got_solution = (x == 0);
		if (allow_AUF) {
			if (x == 112 || x == 200 || x == 225) {
				got_solution = true;
			}
		}
		if (got_solution) {
			++count;
			if (show_solutions) {
				for (i = 0; i < 13; ++i) {
					switch (ordering[i]) {
					case 0:
						printf (" Aa Ab");
						break;
					case 1:
						printf (" E");
						break;
					case 2:
						printf (" F");
						break;
					case 3:
						printf (" Ga Gb Gc Gd");
						break;
					case 4:
						printf (" H");
						break;
					case 5:
						printf (" Ja Jb");
						break;
					case 6:
						printf (" Na Nb");
						break;
					case 7:
						printf (" Ra Rb");
						break;
					case 8:
						printf (" T");
						break;
					case 9:
						printf (" Ua Ub");
						break;
					case 10:
						printf (" V");
						break;
					case 11:
						printf (" Y");
						break;
					case 12:
						printf (" Z");
						break;
					}
				}
				printf ("\n");
			}
		}
	}
	printf ("%u solutions found.\n", count);
}

void
swap (int n1, int n2, UBYTE* p)
{
	UBYTE t = p[n2];
	p[n2] = p[n1];
	p[n1] = t;
}

void
three_cycle (int n1, int n2, int n3, UBYTE* p)
{
	UBYTE t = p[n3];
	p[n3] = p[n2];
	p[n2] = p[n1];
	p[n1] = t;
}

void
compose_perm (const UBYTE *p1, const UBYTE *p2, UBYTE* result)
{
	int i;
	for (i = 0; i < 4; ++i) {
		result[i] = p1[p2[i]];
	}
}

void
calc_plls ()
{
	int i, j;

	UBYTE tc[4], te[4];
	for (i = 0; i < 21; ++i) {
		for (j = 0; j < 4; ++j) {
			tc[j] = te[j] = j;
		}
		switch (i) {
		case 0: //Aa
			three_cycle (1, 3, 2, &tc[0]);
			break;
		case 1: //Ab
			three_cycle (0, 1, 2, &tc[0]);
			break;
		case 2: //E
			swap (0, 1, &tc[0]);
			swap (2, 3, &tc[0]);
			break;
		case 3: //F
			swap (1, 3, &te[0]);
			swap (2, 3, &tc[0]);
			break;
		case 4: //Ga
			three_cycle (0, 2, 3, &te[0]);
			three_cycle (0, 3, 1, &tc[0]);
			break;
		case 5: //Gb
			three_cycle (0, 3, 2, &te[0]);
			three_cycle (0, 1, 3, &tc[0]);
			break;
		case 6: //Gc
			three_cycle (0, 2, 1, &te[0]);
			three_cycle (0, 1, 2, &tc[0]);
			break;
		case 7: //Gd
			three_cycle (0, 1, 2, &te[0]);
			three_cycle (0, 2, 1, &tc[0]);
			break;
		case 8: //H
			swap (0, 2, &te[0]);
			swap (1, 3, &te[0]);
			break;
		case 9: //Ja
			swap (0, 3, &te[0]);
			swap (0, 3, &tc[0]);
			break;
		case 10: //Jb
			swap (0, 1, &te[0]);
			swap (1, 2, &tc[0]);
			break;
		case 11: //Na
			swap (1, 3, &te[0]);
			swap (0, 2, &tc[0]);
			break;
		case 12: //Nb
			swap (1, 3, &te[0]);
			swap (1, 3, &tc[0]);
			break;
		case 13: //Ra
			swap (1, 2, &te[0]);
			swap (0, 1, &tc[0]);
			break;
		case 14: //Rb
			swap (0, 1, &te[0]);
			swap (2, 3, &tc[0]);
			break;
		case 15: //T
			swap (1, 3, &te[0]);
			swap (1, 2, &tc[0]);
			break;
		case 16: //Ua
			three_cycle (1, 2, 3, &te[0]);
			break;
		case 17: //Ub
			three_cycle (1, 3, 2, &te[0]);
			break;
		case 18: //V
			swap (1, 2, &te[0]);
			swap (1, 3, &tc[0]);
			break;
		case 19: //Y
			swap (2, 3, &te[0]);
			swap (1, 3, &tc[0]);
			break;
		case 20: //Z
			swap (0, 1, &te[0]);
			swap (2, 3, &te[0]);
			break;
		}
		plls[i] = get_perm_number (&tc[0], &te[0]);
	}
#if 0
	//Calculate AUF permutation numbers.
	//U
	for (j = 0; j < 4; ++j) {
		tc[j] = te[j] = j;
	}
	three_cycle (2, 1, 0, &tc[0]);
	swap (2, 3, &tc[0]);
	three_cycle (2, 1, 0, &te[0]);
	swap (2, 3, &te[0]);
	UINT permval = get_perm_number (&tc[0], &te[0]);
	printf ("U = %u\n", permval);

	//U2
	for (j = 0; j < 4; ++j) {
		tc[j] = te[j] = j;
	}
	swap (0, 2, &tc[0]);
	swap (1, 3, &tc[0]);
	swap (0, 2, &te[0]);
	swap (1, 3, &te[0]);
	permval = get_perm_number (&tc[0], &te[0]);
	printf ("U2 = %u\n", permval);

	//U'
	for (j = 0; j < 4; ++j) {
		tc[j] = te[j] = j;
	}
	three_cycle (0, 1, 2, &tc[0]);
	swap (0, 3, &tc[0]);
	three_cycle (0, 1, 2, &te[0]);
	swap (0, 3, &te[0]);
	permval = get_perm_number (&tc[0], &te[0]);
	printf ("U' = %u\n", permval);
#endif
}

void
init_tables ()
{
	int i, j;
	UBYTE tc[4], te[4];
	UBYTE tc2[4], te2[4];
	UBYTE tc3[4], te3[4];
	for (i = 0; i < 288; ++i) {
		unpack_perm_number (i, &tc[0], &te[0]);
		for (j = 0; j < 21; ++j) {
			UINT pll = plls[j];
			unpack_perm_number (pll, &tc2[0], &te2[0]);
			compose_perm (&tc[0], &tc2[0], &tc3[0]);
			compose_perm (&te[0], &te2[0], &te3[0]);
			apply_pll[i][j] = get_perm_number (&tc3[0], &te3[0]);
		}
	}
}

UINT
get_perm_number (const UBYTE* pcorner, const UBYTE* pedge)
{
	UINT yc = perm_n_pack (4, pcorner);
	UINT ye = perm_n_pack (4, pedge);
	return 12*yc + (ye >> 1);
}

void
unpack_perm_number (UINT x, UBYTE* pcorner, UBYTE* pedge)
{
	UINT uc = x/12;
	UINT ue = 2*(x % 12);
	perm_n_unpack (4, uc, pcorner);
	int cpar = get_parity (4, uc);
	int epar = get_parity (4, ue);
	if (epar != cpar) {
		ue |= 1;
	}
	perm_n_unpack (4, ue, pedge);
}

UINT
perm_n_pack (UINT n, const UBYTE* array_in)
{
	UINT idx;
	UINT i, j;

	idx = 0;

	for (i = 0; i < n; ++i) {
		idx *= (n - i);

		for (j = i + 1; j < n; ++j) {
			if (array_in[j] < array_in[i]) {
				++idx;
			}
		}
	}
	return idx;
}

void
perm_n_unpack (UINT n, UINT idx, UBYTE* array_out)
{
	int i, j;
	int nn = static_cast<int>(n);

	for (i = nn - 1; i >= 0; --i) {
		array_out[i] = idx % (nn - i);
		idx /= (nn - i);

		for (j = i + 1; j < nn; ++j) {
			if (array_out[j] >= array_out[i]) {
				array_out[j]++;
			}
		}
	}
}

void
perm_n_unpackx (UINT n, double idx, UBYTE* array_out)
{
	int i, j;
	int nn = static_cast<int>(n);

	for (i = nn - 1; i >= 0; --i) {
		array_out[i] = static_cast<UBYTE>(fmod (idx, static_cast<double>(nn - i)));
		idx /= (nn - i);

		for (j = i + 1; j < nn; ++j) {
			if (array_out[j] >= array_out[i]) {
				array_out[j]++;
			}
		}
	}
}

int
get_parity (int n, UINT x)
{
	//max for n is 12, due to range of UINT
	int i, j;
	int parity = 0;
	UBYTE t[12];
	perm_n_unpack (n, x, &t[0]);
	for (i = 0; i < n - 1; ++i) {
		if (t[i] == i) {
			continue;
		}
		for (j = i + 1; j < n; ++j) {
			if (t[j] == i) {
				//"swap" the i & j elements, but don't bother updating the "i"-element
				//as it isn't needed anymore.
				t[j] = t[i];
			}
		}
		parity ^= 1;
	}
	return parity;
}