/*
 * Rubik's Cube Solver - C Solution
 *
 * This solution simply simulates the cube through all of its operations and
 * then checks to see if the resulting cube is solved.
 *
 * The data structure used to hold the state of the cube is a series of 3x3
 * matricies.  At first you may wonder why we did not use a 3x3x3 matrix, 
 * but this type of matrix can hold at most 27 values, and a Rubik's Cube
 * requires us to track 54 values since many of the minor cubes have multiple
 * outward-facing colored sides. 
 *
 * Each of the 3x3 matricies represents a single face. The first index into
 * one of the Rubik's Cube data types (rubiks_cube_t) identifies the face
 * of the cube as shown below:
 *
 *       0 0 0 
 *       0 0 0 
 *       0 0 0 
 * 1 1 1 2 2 2 3 3 3 4 4 4
 * 1 1 1 2 2 2 3 3 3 4 4 4
 * 1 1 1 2 2 2 3 3 3 4 4 4
 *       5 5 5 
 *       5 5 5 
 *       5 5 5 
 *
 * The second and third indicies represent the row and column, respectively,
 * for the given face:
 *
 * (0,0) (0,1) (0,2)
 * (1,0) (1,1) (1,2)
 * (2,0) (2,1) (2,2)
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <math.h>

/*************/
/* Constants */
/*************/
#if !defined(FALSE)
#define TRUE 1
#define FALSE 0
#endif

/***************************************************************/
/* Debug macros, these will print values useful when debugging */
/***************************************************************/
#define NOOP
/* #define DEBUG */
#if defined(DEBUG)
#define DPRINT0(a) fprintf(stderr,a); fflush(stderr);
#define DPRINT1(a,b) fprintf(stderr,a,b); fflush(stderr);
#define DPRINT2(a,b,c) fprintf(stderr,a,b,c); fflush(stderr);
#define DPRINT3(a,b,c,d) fprintf(stderr,a,b,c,d); fflush(stderr);
#define SHOWCUBE ShowCube();
#else
#define DPRINT0(a) NOOP
#define DPRINT1(a,b) NOOP
#define DPRINT2(a,b,c) NOOP
#define DPRINT3(a,b,c,d) NOOP
#define SHOWCUBE NOOP
#endif

/****************/
/* Custom Types */
/****************/
typedef char rubiks_cube_t[6][3][3];
#define FACE_SIZE (sizeof(rubiks_cube_t) / 6)

typedef enum 
{              FACE_TOP=0, 
    FACE_LEFT, FACE_FRONT, FACE_RIGHT, FACE_BACK, 
               FACE_BOTTOM,
    FACE_MAX
} face_t;

typedef enum { ROTATE_LEFT, ROTATE_RIGHT } rotation_t;

typedef face_t cube_position_t[FACE_MAX];

/********************/
/* Global Variables */
/********************/
rubiks_cube_t TheCube;
cube_position_t FaceAtPosition;
rubiks_cube_t TempCube;
static char YesAnswer[] = "Yes";
static char NoAnswer[] = "No";
char FaceName[6][10];

/***********************/
/* Function Prototypes */
/***********************/
void Initialize();
int ReadNextCube();
int ReadNextCommand(face_t *face, rotation_t *rotation);
void DoNextCommand(face_t face, rotation_t rotation);
void BringFaceToFront(face_t face);
void Rotate(rotation_t rotation);
void RotateCubeRight();
void RotateCubeUp();
char *IsCubeSolved();

/* Debug functions */
void ShowCube();

/**********/
/* main() */
/**********/
int 
main(int argc, char *argv[])
{
    int retCode = 0;
    char dummy_string[100]; 
    char *eofifnull = NULL;
    int numcommands;

    /* Loop through each input data set */
    while (TRUE)
    {
	/* Reset for the next game */
        Initialize();

        /* Read the 'START' line, if there is one */
        eofifnull = gets(dummy_string);
        if (eofifnull == NULL ||
            strncmp(dummy_string,"ENDOFINPUT",10) == 0)
        {
            /* Normal end of input */
            retCode = EINVAL;
            break;
        }
        else if (strcmp(dummy_string,"START"))
        {
            DPRINT1("Expected 'START' but got '%s'!\n",dummy_string);
            retCode = EINVAL;
            break;
        }

        DPRINT0("Reading next cube...\n");
        retCode = ReadNextCube();
	if (retCode != 0) 
	{
	    break;
        }

        /* Move input pointer to the start of the list of manipulations */
        eofifnull = gets(dummy_string);
        if (strcmp(dummy_string,""))
        {
            DPRINT1("Expected '' but got '%s'!\n",dummy_string);
            retCode = EINVAL;
            break;
        }

        DPRINT0("Processing commands for this cube...\n");
        numcommands = 0;
        ShowCube();
	while (TRUE) 
	{
            face_t face;
            rotation_t rotation;

	    retCode = ReadNextCommand(&face, &rotation); 
	    if (retCode != 0) 
	    {
	        break;
            }
            ++numcommands;
            DoNextCommand(face, rotation);
	}

        if (numcommands == 0)
        {
            DPRINT0("Illegal input set! All cubes must have at least one command.\n");
        }

        DPRINT0("Checking if the cube is solved...\n");
	printf("%s\n", IsCubeSolved());
    }

    return 0;
}

/**************/
/* Initialize */
/**************/
void
Initialize()
{
    /*
     * The point of this routine is to ensure that we are starting from
     * a clean slate when processing each data set.
     */
    memset(&TheCube,0,sizeof(TheCube));
    memset(&TempCube,0,sizeof(TempCube));

    /*
     * Let's also fill in the FaceNames array.
     */
    strcpy(FaceName[FACE_TOP],    "top");
    strcpy(FaceName[FACE_LEFT],   "left");
    strcpy(FaceName[FACE_FRONT],  "front");
    strcpy(FaceName[FACE_RIGHT],  "right");
    strcpy(FaceName[FACE_BACK],   "back");
    strcpy(FaceName[FACE_BOTTOM], "bottom");

    /*
     * Let's also initialize the cube's position, which is the current
     * location of each face.
     */
    FaceAtPosition[FACE_TOP]    = FACE_TOP;    
    FaceAtPosition[FACE_LEFT]   = FACE_LEFT;    
    FaceAtPosition[FACE_FRONT]  = FACE_FRONT;    
    FaceAtPosition[FACE_RIGHT]  = FACE_RIGHT;    
    FaceAtPosition[FACE_BACK]   = FACE_BACK;    
    FaceAtPosition[FACE_BOTTOM] = FACE_BOTTOM;    
}

/****************/
/* ReadNextCube */
/****************/
int
ReadNextCube()
{
    /*
     * This routine will read in the initial cube configuration for the
     * next data set.
     */

    int retCode = 0, rc = 0;
    char startStr[10], endStr[10];
    int face, row, col;

    /* First, read face zero */
    face = 0;
    for (row = 0; row <= 2; row++)
    {
        for (col = 0; col <= 2; col++)
        {
            rc = scanf(" %c", &TheCube[face][row][col]);
            if (rc != 1) 
            { 
                if (row != 0 || col != 0 || !feof(stdin))
                {
                    /* This isn't the normal end of input. */
                    DPRINT3("Error reading face %d row %d col %d",face,row,col); 
                }
                return ENODATA;
            }
        }
    }

    /* Now, read faces one through four */
    for (row = 0; row <= 2; row++)
    {
        for (face = 1; face <= 4; face++)
        {
            for (col = 0; col <= 2; col++)
            {
                rc = scanf(" %c", &TheCube[face][row][col]);
                if (rc != 1) 
                { 
                    DPRINT3("Error reading face %d row %d col %d",face,row,col); 
                    return ENODATA;
                }
            }
        }
    }

    /* Finally, read face five */
    face = 5;
    for (row = 0; row <= 2; row++)
    {
        for (col = 0; col <= 2; col++)
        {
            rc = scanf(" %c", &TheCube[face][row][col]);
            if (rc != 1) 
            { 
                DPRINT3("Error reading face %d row %d col %d",face,row,col); 
                return ENODATA;
            }
        }
    }

    return 0;
}

/*********************/
/* ReadNextCommand() */
/*********************/
int
ReadNextCommand(face_t *face, rotation_t *rotation)
{

    /*
     * This function will read the next line of input and (if it is a command)
     * will set the return values so that the caller will know which rotation
     * to apply to which face.
     */

    char *eofifnull;
    char line[100];
    char face_str[100], rotation_str[100];

    /* Read the next line */
    eofifnull = gets(line);

    /* If EOF was found, set return value to non-zero and print an error message */
    if (eofifnull == NULL)
    {
        DPRINT0("Expected a move but found EOF instead!\n");
        return ENODATA;
    }
    /* If END was found, set return value to non-zero */
    else if (!strcmp(line,"END"))
    {
        return ENODATA;
    }

    /* Otherwise, fill in the return values */
    else
    {
        sscanf(line,"%s %s", face_str, rotation_str);
        for (*face = FACE_TOP; *face < FACE_MAX; (*face)++)
        {
            if (!strcmp(FaceName[*face],face_str)) break;
        }
        if (*face == FACE_MAX) {
            DPRINT1("Invalid face name %s\n", face_str);
            return EINVAL;
        }

        if (!strcmp(rotation_str,"left"))
        {
            *rotation = ROTATE_LEFT;
            DPRINT1("Rotating %s face left (counter-clockwise)\n",FaceName[*face]);
        }
        else if (!strcmp(rotation_str,"right"))
        {
            *rotation = ROTATE_RIGHT;
            DPRINT1("Rotating %s face right (clockwise)\n",FaceName[*face]);
        }
        else
        {
            DPRINT1("Invalid rotation direction '%s'!\n.", rotation_str);
            return EINVAL;
        }
    }

    /* Return success */
    return 0;
}

/*****************/
/* DoNextCommand */
/*****************/
void
DoNextCommand(face_t face, rotation_t rotation)
{
    /* Bring the named face to the front */
    BringFaceToFront(face);
    ShowCube();

    /* Rotate the face */
    Rotate(rotation);
    ShowCube();

    return;
}

/****************/
/* IsCubeSolved */
/****************/
char *
IsCubeSolved()
{
    int i,j;
    face_t face;
    char *Answer = YesAnswer;

    /* We just have to check that each side is self-consistent */

    /* Check each side for consistency */
    for (face = FACE_TOP; face < FACE_MAX; face++)
    {
        for (i=0; i<3; i++)
        {
            for (j=0; j<3; j++)
            {
                if (TheCube[face][i][j] != TheCube[face][1][1])
                {
                    Answer = NoAnswer;
                }
            }
        }
    }

    return Answer;
}

/********************/
/* BringFaceToFront */
/********************/
void
BringFaceToFront(face_t face)
{
    int TrueRightFalseUp; /* TRUE -> right, FALSE -> up */
    int NumMoves = 0;
    int i;

    /* 
     * Determine which move direction (up or right) is required and the
     * number of such moves. 
     */
    if (FaceAtPosition[FACE_FRONT] == face)
    {
        /* No work is needed, just return */
        return;
    }

    if (FaceAtPosition[FACE_TOP] == face)
    {
        TrueRightFalseUp = FALSE; /* turn it up */
        NumMoves = 3;
    }

    if (FaceAtPosition[FACE_BOTTOM] == face)
    {
        TrueRightFalseUp = FALSE; /* turn it up */
        NumMoves = 1;
    }

    if (FaceAtPosition[FACE_LEFT] == face)
    {
        TrueRightFalseUp = TRUE; /* turn it right */
        NumMoves = 1;
    }

    if (FaceAtPosition[FACE_RIGHT] == face)
    {
        TrueRightFalseUp = TRUE; /* turn it right */
        NumMoves = 3;
    }

    if (FaceAtPosition[FACE_BACK] == face)
    {
        TrueRightFalseUp = TRUE; /* turn it right */
        NumMoves = 2;
    }

    /*
     * Now rotate the face to the front.
     */

    for (i = 0; i < NumMoves; i++)
    {
        if (TrueRightFalseUp == TRUE) /* Rotate right */
        {
            RotateCubeRight();
        }
        else /* Rotate up */
        {
            RotateCubeUp();
        }
    }
}

/****************/
/* RotateCubeUp */
/****************/
void
RotateCubeUp()
{
    face_t tempface;
    int i,j;

    /* First set the new position of the cube's faces */
    tempface = FaceAtPosition[FACE_FRONT];
    FaceAtPosition[FACE_FRONT] = FaceAtPosition[FACE_BOTTOM];
    FaceAtPosition[FACE_BOTTOM] = FaceAtPosition[FACE_BACK];
    FaceAtPosition[FACE_BACK] = FaceAtPosition[FACE_TOP];
    FaceAtPosition[FACE_TOP] = tempface;

    /* Now actually move the faces */

    /* Front to top */
    memcpy(TempCube[FACE_TOP],TheCube[FACE_FRONT],FACE_SIZE);

    /* Top to back */
    for (i=0; i<3; i++) 
    {
        for (j=0; j<3; j++)
        {
            TempCube[FACE_BACK][2-i][2-j] = TheCube[FACE_TOP][i][j];
        }
    }

    /* Back to bottom */
    for (i=0; i<3; i++) 
    {
        for (j=0; j<3; j++)
        {
            TempCube[FACE_BOTTOM][2-i][2-j] = TheCube[FACE_BACK][i][j];
        }
    }

    /* Bottom to front */
    memcpy(TempCube[FACE_FRONT],TheCube[FACE_BOTTOM],FACE_SIZE);

    /* Left face counter clockwise */
    for (i=0; i<3; i++) 
    {
        for (j=0; j<3; j++)
        {
            TempCube[FACE_LEFT][2-j][i] = TheCube[FACE_LEFT][i][j];
        }
    }

    /* Right face clockwise */
    for (i=0; i<3; i++) 
    {
        for (j=0; j<3; j++)
        {
            TempCube[FACE_RIGHT][j][2-i] = TheCube[FACE_RIGHT][i][j];
        }
    }

    /* Now that the temp cube is set, copy it to the real one */
    memcpy(TheCube, TempCube, sizeof(TheCube));
    
}

/*******************/
/* RotateCubeRight */
/*******************/
void
RotateCubeRight()
{
    face_t tempface;
    int i,j;

    /* First set the new position of the cube's faces */
    tempface = FaceAtPosition[FACE_FRONT];
    FaceAtPosition[FACE_FRONT] = FaceAtPosition[FACE_LEFT];
    FaceAtPosition[FACE_LEFT] = FaceAtPosition[FACE_BACK];
    FaceAtPosition[FACE_BACK] = FaceAtPosition[FACE_RIGHT];
    FaceAtPosition[FACE_RIGHT] = tempface;

    /* Now actually move the faces */

    /* Front to right */
    memcpy(TempCube[FACE_RIGHT],TheCube[FACE_FRONT],FACE_SIZE);

    /* Right to back */
    memcpy(TempCube[FACE_BACK],TheCube[FACE_RIGHT],FACE_SIZE);

    /* Back to left */
    memcpy(TempCube[FACE_LEFT],TheCube[FACE_BACK],FACE_SIZE);

    /* Left to front */
    memcpy(TempCube[FACE_FRONT],TheCube[FACE_LEFT],FACE_SIZE);

    /* Top face counter-clockwise */
    for (i=0; i<3; i++) 
    {
        for (j=0; j<3; j++)
        {
            TempCube[FACE_TOP][2-j][i] = TheCube[FACE_TOP][i][j];
        }
    }

    /* Bottom face clockwise */
    for (i=0; i<3; i++) 
    {
        for (j=0; j<3; j++)
        {
            TempCube[FACE_BOTTOM][j][2-i] = TheCube[FACE_BOTTOM][i][j];
        }
    }

    /* Now that the temp cube is set, copy it to the real one */
    memcpy(TheCube, TempCube, sizeof(TheCube));
    
}

/**********/
/* Rotate */
/**********/
void
Rotate(rotation_t rotation)
{
    int i,j;

    /* First copy the cube */
    memcpy(TempCube,TheCube,sizeof(TheCube));

    /* If we're turning left (counter-clockwise), do it. */
    if (rotation == ROTATE_LEFT)
    {
        /* Start by turning the front face */
        for (i=0; i<3; i++) 
        {
            for (j=0; j<3; j++)
            {
                TempCube[FACE_FRONT][2-j][i] = TheCube[FACE_FRONT][i][j];
            }
        }

        /* Now turn the edges of the front face */
        for (i=0; i<3; i++)
        {
                TempCube[FACE_TOP][2][i] = TheCube[FACE_RIGHT][i][0];
                TempCube[FACE_LEFT][2-i][2] = TheCube[FACE_TOP][2][i];
                TempCube[FACE_BOTTOM][0][2-i] = TheCube[FACE_LEFT][2-i][2];
                TempCube[FACE_RIGHT][i][0] = TheCube[FACE_BOTTOM][0][2-i];
        } 
    }

    /* Otherwise, turn it right */
    else {
        /* Start by turning the front face */
        for (i=0; i<3; i++) 
        {
            for (j=0; j<3; j++)
            {
                TempCube[FACE_FRONT][j][2-i] = TheCube[FACE_FRONT][i][j];
            }
        }

        /* Now turn the edges of the front face */
        for (i=0; i<3; i++)
        {
                TempCube[FACE_TOP][2][i] = TheCube[FACE_LEFT][2-i][2];
                TempCube[FACE_LEFT][2-i][2] = TheCube[FACE_BOTTOM][0][2-i];
                TempCube[FACE_BOTTOM][0][2-i] = TheCube[FACE_RIGHT][i][0];
                TempCube[FACE_RIGHT][i][0] = TheCube[FACE_TOP][2][i];
        } 
    }

    /* Now copy the temp cube to the cube */
    memcpy(TheCube, TempCube, sizeof(TheCube));

    return;
}

/*****************************/
/* ShowCube - debug function */
/*****************************/
void
ShowCube()
{
#if defined DEBUG
    /*
     * This routine will print the current cube to stdout.
     */

    int face, row, col;

    /* First, print face zero */
    face = 0;
    for (row = 0; row <= 2; row++, printf("\n"))
    {
        printf("      ");
        for (col = 0; col <= 2; col++)
        {
            printf("%c ", TheCube[face][row][col]);
        }
    }

    /* Now, print faces one through four */
    for (row = 0; row <= 2; row++, printf("\n"))
    {
        for (face = 1; face <= 4; face++)
        {
            for (col = 0; col <= 2; col++)
            {
                printf("%c ", TheCube[face][row][col]);
            }
        }
    }

    /* Finally, print face five */
    face = 5;
    for (row = 0; row <= 2; row++, printf("\n"))
    {
        printf("      ");
        for (col = 0; col <= 2; col++)
        {
            printf("%c ", TheCube[face][row][col]);
        }
    }
#endif

    return;
}