/*
 * @(#)PyraminxS.c
 *
 * Taken from the algorithm in The Simple Solutions to Cubic Puzzles
 * by James G. Nourse (also looked at Puzzle It Out: Cubes, Groups
 * and Puzzles by John Ewing & Czes Kosniowski)
 * Break ability taken from the X puzzle by Don Bennett, HP Labs
 *
 * Copyright 1999 - 2010  David A. Bagley, bagleyd@tux.org
 *
 * All rights reserved.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation for any purpose and without fee is hereby granted,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear in
 * supporting documentation, and that the name of the author not be
 * used in advertising or publicity pertaining to distribution of the
 * software without specific, written prior permission.
 *
 * This program is distributed in the hope that it will be "useful",
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 */

/* Solver file for Pyraminx */

#include "rngs.h"
#define JMP
#ifdef JMP
#include <setjmp.h> /* longjmp ... interrupt */
#endif
#include "PyraminxP.h"

/* Moving Nourse's large corners translates as:
 * move the whole puzzle
 * undo the face move */
#define rotateLittleCornerCW(w,f) movePuzzlePiece(w,f,0,(f%2)?TR:BL,PERIOD3,FALSE)
#define rotateLittleCornerCCW(w,f) movePuzzlePiece(w,f,0,(f%2)?BL:TR,PERIOD3,FALSE)
#define rotateCornerCW(w,f) movePuzzlePiece(w,f,1,(f%2)?TR:BL,PERIOD3,TRUE); \
	movePuzzlePiece(w,f,6,(f%2)?BL:TR,PERIOD3,FALSE)
#define rotateCornerCCW(w,f) movePuzzlePiece(w,f,1,(f%2)?BL:TR,PERIOD3,TRUE); \
	movePuzzlePiece(w,f,6,(f%2)?TR:BL,PERIOD3,FALSE)

#define topFaceTrans(tf,f) ((tf==0)?f:((tf==1)?MAX_FACES-1-(f+MAX_FACES/2)%MAX_FACES:((tf==2)?(f+MAX_FACES/2)%MAX_FACES:MAX_FACES-1-f)))

#define P_PLUS rotateCornerCW(w,topFaceTrans(topFace,0)) /* Posterior Corner CW */
#define B_PLUS rotateCornerCW(w,topFaceTrans(topFace,1)) /* Bottom Corner CW */
#define L_PLUS rotateCornerCW(w,topFaceTrans(topFace,2)) /* Left Corner CW */
#define R_PLUS rotateCornerCW(w,topFaceTrans(topFace,3)) /* Right Corner CW */
#define P_MINUS rotateCornerCCW(w,topFaceTrans(topFace,0)) /* Posterior Corner CCW */
#define B_MINUS rotateCornerCCW(w,topFaceTrans(topFace,1)) /* Bottom Corner CCW */
#define L_MINUS rotateCornerCCW(w,topFaceTrans(topFace,2)) /* Left Corner CCW */
#define R_MINUS rotateCornerCCW(w,topFaceTrans(topFace,3)) /* Right Corner CCW */

#define rotateWholeCW(w,f) movePuzzlePiece(w,f,1,(f%2)?TR:BL,PERIOD3,TRUE)
#define rotateWholeCCW(w,f) movePuzzlePiece(w,f,1,(f%2)?BL:TR,PERIOD3,TRUE)
#define B_PLUS_WHOLE rotateWholeCW(w,topFaceTrans(topFace,1)) /* Bottom Corner CW */
#define B_MINUS_WHOLE rotateWholeCCW(w,topFaceTrans(topFace,1)) /* Bottom Corner CCW */


static int indexToEdges[3] = {1, 3, 6};
static int edgesToIndex[9] = {3, 0, 3, 1, 3, 3, 2, 3, 3};
static int edgeMateFace[MAX_FACES][3] =
{
	{2, 3, 1},
	{3, 2, 0},
	{0, 1, 3},
	{1, 0, 2}
};

static Boolean solvingFlag = False;
#ifdef JMP
static Boolean abortSolvingFlag = False;
static jmp_buf solve_env;

static void
abortSolving(void)
{
	if (solvingFlag)
		abortSolvingFlag = True;
}

#ifdef WINVER
static Boolean
processMessage(UINT msg)
{
	switch (msg) {
	case WM_KEYDOWN:
	case WM_CLOSE:
	case WM_LBUTTONDOWN:
	case WM_RBUTTONDOWN:
		abortSolving();
		return True;
	default:
		return False;
	}
}
#else
static void
processButton(void /*XButtonEvent *event*/)
{
	abortSolving();
}

static void
processVisibility(XVisibilityEvent *event)
{
	if (event->state != VisibilityUnobscured)
		abortSolving();
}

static void
getNextEvent(PyraminxWidget w, XEvent *event)
{
	if (!XCheckMaskEvent(XtDisplay(w), VisibilityChangeMask, event))
		(void) XNextEvent(XtDisplay(w), event);
}

static void
processEvent(XEvent *event)
{
	switch(event->type) {
	case KeyPress:
	case ButtonPress:
		processButton(/*&event->xbutton*/);
		break;
	case VisibilityNotify:
		processVisibility(&event->xvisibility);
		break;
	default:
		break;
	}
}

static void
processEvents(PyraminxWidget w)
{
	XEvent event;

	while (XPending(XtDisplay(w))) {
		getNextEvent(w, &event);
		processEvent(&event);
	}
}
#endif
#endif

static void
movePuzzlePiece(PyraminxWidget w, int face, int position,
	int direction, int style, int control)
{
#ifdef JMP
#ifdef WINVER
	MSG msg;

	if (PeekMessage(&msg, NULL, 0, 0, 0)) {
		if (!processMessage(msg.message)) {
			if (GetMessage(&msg, NULL, 0, 0))
				DispatchMessage(&msg);
		}
	}
#else
	processEvents(w);
#endif
	if (solvingFlag && abortSolvingFlag)
		longjmp(solve_env, 1);
#endif
	movePuzzleDelay(w, face, position, direction, style, control);
}

/* This is impossible to do with Drag and Drop as implemented.
 * Use the keypad.  Turn the little corners so that the
 * colors match the adjacent pieces all around. */
static void
orientLittleCorners(PyraminxWidget w)
{
	int face, currentColor;

	for (face = 0; face < MAX_FACES; face++) {
		currentColor = w->pyraminx.facetLoc[face][0].face;
		if (currentColor != w->pyraminx.facetLoc[face][2].face) {
			if (currentColor == w->pyraminx.facetLoc[MAX_FACES - face - 1][w->pyraminx.sizeSize - 2].face) {
				rotateLittleCornerCCW(w,face);
			} else {
				rotateLittleCornerCW(w,face);
			}
		}
	}
}

static int
findFaceColor(PyraminxWidget w, int face)
{
	int colors[3], color, cornerFace;

	switch (face) {
		case 0:
			colors[0] = w->pyraminx.facetLoc[1][2].face;
			colors[1] = w->pyraminx.facetLoc[3][5].face;
			colors[2] = w->pyraminx.facetLoc[2][7].face;
			break;
		case 1:
			colors[0] = w->pyraminx.facetLoc[0][2].face;
			colors[1] = w->pyraminx.facetLoc[2][5].face;
			colors[2] = w->pyraminx.facetLoc[3][7].face;
			break;
		case 2:
			colors[0] = w->pyraminx.facetLoc[3][2].face;
			colors[1] = w->pyraminx.facetLoc[1][5].face;
			colors[2] = w->pyraminx.facetLoc[0][7].face;
			break;
		case 3:
			colors[0] = w->pyraminx.facetLoc[2][2].face;
			colors[1] = w->pyraminx.facetLoc[0][5].face;
			colors[2] = w->pyraminx.facetLoc[1][7].face;
			break;
		default:
			(void) printf("Wrong face %d.\n", face);
	}
	for (color = 0; color < MAX_FACES; color++) {
		for (cornerFace = 0; cornerFace < 3; cornerFace++) {
			if (color == colors[cornerFace])
				break;
		}
		if (cornerFace == 3)
			return color;
	}
	(void) printf("No opposite color found!\n");
	return 0;
}

static Boolean
checkPiece(PyraminxWidget w, int color, int face, int position)
{
	int newFace, newPosition, positionIndex;

	positionIndex = edgesToIndex[position];
	if (positionIndex == 3) {
		positionIndex = 0;
		(void) printf("position %d incorrect\n", position);
	}
	newFace = edgeMateFace[face][positionIndex];
	newPosition = indexToEdges[positionIndex];
	if (w->pyraminx.facetLoc[newFace][newPosition].face == color) {
		return True;
	}
	return False;
}

static void
findPiece(PyraminxWidget w, int color0, int color1, int *face, int *position)
{
	int faceSkip, positionIndex;

	/* Check starting face first */
	for (positionIndex = 0; positionIndex < 3; positionIndex++) {
		*position = indexToEdges[positionIndex];
		if (w->pyraminx.facetLoc[*face][*position].face == color0 &&
				checkPiece(w, color1, *face, *position)) {
			return;
		}
		if (w->pyraminx.facetLoc[*face][*position].face == color1 &&
				checkPiece(w, color0, *face, *position)) {
			return;
		}
	}
	faceSkip = *face;
	for (*face = 0; *face < MAX_FACES; (*face)++) {
		if (*face != faceSkip) {
			for (positionIndex = 0; positionIndex < 3; positionIndex++) {
				*position = indexToEdges[positionIndex];
				if (w->pyraminx.facetLoc[*face][*position].face == color0 &&
						checkPiece(w, color1, *face, *position)) {
					return;
				}
				if (w->pyraminx.facetLoc[*face][*position].face == color1 &&
						checkPiece(w, color0, *face, *position)) {
					return;
				}
			}
		}
	}
	(void) printf("Piece %d %d not found!\n", color0, color1);
}

static void
faceCorners(PyraminxWidget w, int face, int faceColor)
{
	int otherFace;

	if (faceColor != w->pyraminx.facetLoc[face][2].face) {
		if (faceColor == w->pyraminx.facetLoc[MAX_FACES - 1 - face][7].face) {
			rotateCornerCW(w,face);
		} else {
			rotateCornerCCW(w,face);
		}
	}
	otherFace = (face + 2) % 4;
	if (faceColor != w->pyraminx.facetLoc[face][5].face) {
		if (faceColor == w->pyraminx.facetLoc[otherFace][2].face) {
			rotateCornerCW(w,otherFace);
		} else {
			rotateCornerCCW(w,otherFace);
		}
	}
	otherFace = MAX_FACES - 1 - face;
	if (faceColor != w->pyraminx.facetLoc[face][7].face) {
		if (faceColor == w->pyraminx.facetLoc[otherFace][2].face) {
			rotateCornerCCW(w,otherFace);
		} else {
			rotateCornerCW(w,otherFace);
		}
	}
}

#if 0
/* This is a general approach that seems unwieldly right now. */
static void
faceEdge(PyraminxWidget w, int topFace, int position, int faceColor)
{
	int otherColor, newFace, newPosition;

	switch (position) {
		case 1:
			newFace = (topFace + 2) % 4;
			newPosition = position + 1;
			break;
		case 3:
			newFace = MAX_FACES - 1 - topFace;
			newPosition = position - 1;
			break;
		case 6:
			newFace = MAX_FACES - 1 - ((topFace + 2) % 4);
			newPosition = position - 1;
			break;
		default:
			(void) printf("Wrong position %d.\n", position);
	}
	otherColor = w->pyraminx.facetLoc[newFace][newPosition].face;
	/* newFace and newPosition variables are reused here */
	newFace = topFace; /* This narrows down the cases */
	findPiece(w, faceColor, otherColor, &newFace, &newPosition);
	(void) printf("topFace %d, position %d, newFace %d, newPosition %d, faceColor %d, otherColor %d\n", topFace, position, newFace, newPosition, faceColor, otherColor);
}
#else
/* Move to position 6 and then into correct position. */
static void
faceEdge6(PyraminxWidget w, int topFace, int faceColor)
{
	int otherColor, newFace, newPosition, position;

	position = 6;
	newFace = MAX_FACES - 1 - ((topFace + 2) % 4);
	newPosition = position - 1;
	otherColor = w->pyraminx.facetLoc[newFace][newPosition].face;
	/* newFace and newPosition variables are reused here */
	newFace = topFace; /* This narrows down the cases below */
	findPiece(w, faceColor, otherColor, &newFace, &newPosition);
	if (newFace == topFace) {
		switch (newPosition) {
			case 1: /* Move LT to FT */
				L_MINUS;
				B_PLUS;
				L_MINUS;
				B_MINUS;
				L_MINUS;
				break;
			case 3: /* Move FR to FT */
				R_PLUS;
				B_MINUS;
				R_PLUS;
				B_PLUS;
				R_PLUS;
				break;
			case 6: /* Move FT to FT */
				/* No move :) */
				break;
			default:
				(void) printf("Wrong new position %d.\n", newPosition);
		}
	} else { /* Little more figuring... */
		if ((newFace == topFaceTrans(topFace, 1) || newFace == topFaceTrans(topFace, 2)) && newPosition == 3) { /* Move FL to FT */
			R_MINUS;
			B_PLUS;
			R_PLUS;
		} else if ((newFace == topFaceTrans(topFace, 1) || newFace == topFaceTrans(topFace, 3)) && newPosition == 1) { /* Move FR to FT */
			L_PLUS;
			B_MINUS;
			L_MINUS;
		} else if ((newFace == topFaceTrans(topFace, 2) || newFace == topFaceTrans(topFace, 3)) && newPosition == 6) { /* Move LR to FT */
			R_MINUS;
			B_MINUS;
			R_PLUS;
		} else
			(void) printf("Wrong new face %d or new position %d.\n", newFace, newPosition);
	}
		/* Not correctly positioned... need to flip it */
	if (faceColor != w->pyraminx.facetLoc[topFace][position].face) {
		R_MINUS;
		B_PLUS;
		R_PLUS;
		L_PLUS;
		B_PLUS;
		L_MINUS;
	}
}
#endif

static int
pickTopFace(PyraminxWidget w)
{
	/* Pick a face (0) and determine which color it is by looking at its
	 * opposite corner.  Whatever color is not there is what this
	 * face should be.  Turn big corners to match */
	int topFace, faceColor, aBottomFace;

	/* Could have hard coded at 0 but this way is more challenging */
	topFace = NRAND(4);
	faceColor = findFaceColor(w, topFace);
	faceCorners(w, topFace, faceColor);
#if 0
	faceEdge(w, topFace, 1, faceColor);
	faceEdge(w, topFace, 3, faceColor);
	faceEdge(w, topFace, 6, faceColor);
#else
	faceEdge6(w, topFace, faceColor);
	aBottomFace = MAX_FACES - 1 - ((topFace + 2) % 4);
	movePuzzlePiece(w, aBottomFace, 6, (topFace % 2) ? TR : BL, PERIOD3, TRUE);
	faceEdge6(w, topFace, faceColor);
	movePuzzlePiece(w, aBottomFace, 6, (topFace % 2) ? TR : BL, PERIOD3, TRUE);
	faceEdge6(w, topFace, faceColor);
#endif
	return topFace;
}

static void
alignBigCorner(PyraminxWidget w, int topFace)
{
	int frontColor, leftColor, rightColor;

	frontColor = w->pyraminx.facetLoc[topFaceTrans(topFace, 1)][7].face;
	leftColor = w->pyraminx.facetLoc[topFaceTrans(topFace, 2)][5].face;
	rightColor = w->pyraminx.facetLoc[topFaceTrans(topFace, 3)][2].face;

	if (w->pyraminx.facetLoc[topFaceTrans(topFace, 1)][3].face == frontColor &&
			w->pyraminx.facetLoc[topFaceTrans(topFace, 2)][3].face == leftColor) {
		return;
	}
	if (w->pyraminx.facetLoc[topFaceTrans(topFace, 2)][6].face == leftColor &&
			w->pyraminx.facetLoc[topFaceTrans(topFace, 3)][6].face == rightColor) {
		B_PLUS_WHOLE;
		return;
	}
	if (w->pyraminx.facetLoc[topFaceTrans(topFace, 3)][1].face == rightColor &&
			w->pyraminx.facetLoc[topFaceTrans(topFace, 1)][1].face == frontColor) {
		B_MINUS_WHOLE;
		return;
	}

	/* CW */
	if (w->pyraminx.facetLoc[topFaceTrans(topFace, 1)][3].face == rightColor &&
			w->pyraminx.facetLoc[topFaceTrans(topFace, 2)][3].face == frontColor) {
		B_PLUS;
		B_MINUS_WHOLE;
		return;
	}
	if (w->pyraminx.facetLoc[topFaceTrans(topFace, 2)][6].face == frontColor &&
			w->pyraminx.facetLoc[topFaceTrans(topFace, 3)][6].face == leftColor) {
		B_PLUS;
		return;
	}
	if (w->pyraminx.facetLoc[topFaceTrans(topFace, 3)][1].face == leftColor &&
			w->pyraminx.facetLoc[topFaceTrans(topFace, 1)][1].face == rightColor) {
		B_PLUS;
		B_PLUS_WHOLE;
		return;
	}

	/* CCW */
	if (w->pyraminx.facetLoc[topFaceTrans(topFace, 1)][3].face == leftColor &&
			w->pyraminx.facetLoc[topFaceTrans(topFace, 2)][3].face == rightColor) {
		B_MINUS;
		B_PLUS_WHOLE;
		return;
	}
	if (w->pyraminx.facetLoc[topFaceTrans(topFace, 2)][6].face == rightColor &&
			w->pyraminx.facetLoc[topFaceTrans(topFace, 3)][6].face == frontColor) {
		B_MINUS;
		B_MINUS_WHOLE;
		return;
	}
	if (w->pyraminx.facetLoc[topFaceTrans(topFace, 3)][1].face == frontColor &&
			w->pyraminx.facetLoc[topFaceTrans(topFace, 1)][1].face == leftColor) {
		B_MINUS;
		return;
	}
	(void) printf("Could not align big corner!\n");
}

static void
bottomBigCorner(PyraminxWidget w, int topFace)
{
	int i = 0;

	alignBigCorner(w, topFace);
	while (!checkSolved(w)) {
		if (i++ > 2) {
			(void) printf("Infinite Loop detected!\n");
			return;
		}
		if (w->pyraminx.facetLoc[topFaceTrans(topFace, 1)][7].face ==
				w->pyraminx.facetLoc[topFaceTrans(topFace, 1)][1].face) {
			if (w->pyraminx.facetLoc[topFaceTrans(topFace, 1)][2].face ==
					w->pyraminx.facetLoc[topFaceTrans(topFace, 2)][3].face) {
				R_MINUS;
				B_MINUS;
				R_PLUS;
				B_MINUS;
				R_MINUS;
				B_MINUS;
				R_PLUS;
			} else {
			/* Short cut: Alternate sequence */
			/* Could be solved by using above sequence but adds extra loops. */
				R_MINUS;
				B_PLUS;
				R_PLUS;
				B_PLUS;
				R_MINUS;
				B_PLUS;
				R_PLUS;
			}
		} else {
			L_PLUS;
			B_MINUS;
			L_MINUS;
			R_MINUS;
			B_MINUS;
			R_PLUS;

			L_PLUS;
			B_MINUS;
			L_MINUS;
			R_MINUS;
			B_MINUS;
			R_PLUS;
		}
		alignBigCorner(w, topFace);
	}
#ifdef DEBUG
	(void) printf("loops %d\n", i);
#endif
}

#if 0
From Puzzle It Out: Cubes, Groups and Puzzles
/* Upper(U) = Posterior (P) */
/*      P       */
/*   e3    e4   */
/* L    e1    B */
/*   e2    e5   */
/*      R       */
#define e1_e2_e3 P_MINUS; R_PLUS; P_PLUS; R_MINUS
#define e1_e3_e2 R_PLUS; P_MINUS; R_MINUS; P_PLUS
#define e1_e3_e4 L_PLUS; P_PLUS; R_PLUS; P_MINUS; R_MINUS; L_MINUS
#define e1_e4_e3 L_PLUS; R_PLUS; P_PLUS; R_MINUS; P_MINUS; L_MINUS
#define e2_e1_e4 R_PLUS; P_PLUS; R_MINUS; P_MINUS
#define e4_e1_e2 P_PLUS; R_PLUS; P_MINUS; R_MINUS
#define e5_e1_e3 R_MINUS; P_MINUS; R_PLUS; P_PLUS
#define e3_e1_e5 P_MINUS; R_MINUS; P_PLUS; R_PLUS
#define e1_e3 R_PLUS; P_MINUS; R_MINUS; P_PLUS;\
 R_MINUS; L_PLUS; R_PLUS; L_MINUS
#define e3_e5 P_MINUS; R_MINUS; P_PLUS;\
 R_MINUS; L_PLUS; R_PLUS; L_MINUS; R_PLUS
#endif

/* This procedure coordinates the solution process. */
void
solveSomePieces(PyraminxWidget w)
{
	setPuzzle(w, ACTION_RESET);
	if (solvingFlag)
		return;
#ifdef JMP
	if (!setjmp(solve_env))
#endif
	{
		solvingFlag = True;

		if (!checkSolved(w)) {
			orientLittleCorners(w);
			if (w->pyraminx.size > 2) {
				bottomBigCorner(w, pickTopFace(w));
			}
		}
	}
#ifdef JMP
	abortSolvingFlag = False;
#endif
	solvingFlag = False;
	w->pyraminx.cheat = True; /* Assume the worst. */
	setPuzzle(w, ACTION_COMPUTED);
}