#include <iostream>     // Bibliothèque pour les flux principaux
#include <fstream>      // Bibliothèque pour les flux de fichiers
#include <sstream>      // Bibliothèque pour les flux de conversion string -> long
#include <string>       // Bibliothèque pour l'utilisation des strings
#include <vector>       // Bibliothèque pour créer aisément des tableaux dynamiques "vector"

using namespace std;

    /** STRUCTURE UTILISEE **/

typedef struct RubikCube
{
    vector<int> face;
    int heuristic;
    int cost;
    string permut_letter;
};
    /** PROTOTYPES DES FONCTIONS **/

void basic_permut(RubikCube &original_RubikCube, int a, int b, int c, int d);
void A(RubikCube &original_RubikCube);
void B(RubikCube &original_RubikCube);
void C(RubikCube &original_RubikCube);
void D(RubikCube &original_RubikCube);
void E(RubikCube &original_RubikCube);
void F(RubikCube &original_RubikCube);
void G(RubikCube &original_RubikCube);
void H(RubikCube &original_RubikCube);
void I(RubikCube &original_RubikCube);
void J(RubikCube &original_RubikCube);
void K(RubikCube &original_RubikCube);
void L(RubikCube &original_RubikCube);
void M(RubikCube &original_RubikCube);
void N(RubikCube &original_RubikCube);
void O(RubikCube &original_RubikCube);
void P(RubikCube &original_RubikCube);
void Q(RubikCube &original_RubikCube);
void R(RubikCube &original_RubikCube);
void S(RubikCube &original_RubikCube);
void T(RubikCube &original_RubikCube);
void U(RubikCube &original_RubikCube);
void V(RubikCube &original_RubikCube);
void W(RubikCube &original_RubikCube);
void X(RubikCube &original_RubikCube);
void Y(RubikCube &original_RubikCube);
void Z(RubikCube &original_RubikCube);
void AROBASE(RubikCube &original_RubikCube);

void initialize_RubikCube(RubikCube &cube);
int compare_RubikCube_face(RubikCube a, RubikCube b);
void copy_RubikCube_face(RubikCube &copy, RubikCube original);
void calculate_heuristic(RubikCube &cube);
void display_RubikCube(RubikCube cube);
void read_file_input(RubikCube &original);
void develop_all_permut(RubikCube cube, int cost, vector<RubikCube> &opened_list, vector<RubikCube> &closed_list);
void a_star_solver(RubikCube &cube);

    /** DEBUT DU PROGRAMME **/

int main()
{
    /** ------------------------------------- COMMENCEMENT DU PROGRAMME -------------------------------------- **/


    RubikCube original;

    initialize_RubikCube(original);

    read_file_input(original);

    display_RubikCube(original);

    a_star_solver(original);

    return EXIT_SUCCESS;
}

    /** FONCTIONS DE MANIPULATION DU RUBIK CUBE **/

void initialize_RubikCube(RubikCube &cube)
{
    cube.heuristic = 0;
    cube.cost = 0;
    cube.face.resize(54);
    cube.permut_letter = "";
    int initial_color = 1;

    for(int i = 0; i < 54; i++)
    {
        if(i % 9 == 0 && i != 0)
            initial_color++;

        cube.face[i] = initial_color;
    }
}

void display_RubikCube(RubikCube cube)
{
    system("cls");

    cout << "\n                      =================================               ";
    cout << "\n                     |     Solveur de Rubik's Cube     |              ";
    cout << "\n                     |            AD - TP I            |              ";
    cout << "\n                     |       LIM - SOUTHAKAKOUMAL      |              ";
    cout << "\n                      =================================               " << endl << endl << endl;



    cout << endl << " * Rubik's cube au cout: " << cube.cost << endl;
    cout << " * Heuristique: " << cube.heuristic <<endl;

    cout << endl << "\t\t\t             " << cube.face[24] << " " << cube.face[21] << " " << cube.face[18] << endl;
    cout << "\t\t\t             " << cube.face[25] << " " << cube.face[22] << " " << cube.face[19] << endl;
    cout << "\t\t\t             " << cube.face[26] << " " << cube.face[23] << " " << cube.face[20] << endl << endl;

    cout << "\t\t\t      " << cube.face[9] << " " << cube.face[10] << " " << cube.face[11] << "  " << cube.face[0] << " " << cube.face[1] << " " << cube.face[2] << "  " << cube.face[38] << " " << cube.face[41] << " " << cube.face[44] << endl;
    cout << "\t\t\t      " << cube.face[12] << " " << cube.face[13] << " " << cube.face[14] << "  " << cube.face[3] << " " << cube.face[4] << " " << cube.face[5] << "  " << cube.face[37] << " " << cube.face[40] << " " << cube.face[43] << endl;
    cout << "\t\t\t      " << cube.face[15] << " " << cube.face[16] << " " << cube.face[17] << "  " << cube.face[6] << " " << cube.face[7] << " " << cube.face[8] << "  " << cube.face[36] << " " << cube.face[39] << " " << cube.face[42] << endl << endl;

    cout << "\t\t\t             " << cube.face[27] << " " << cube.face[28] << " " << cube.face[29] << endl;
    cout << "\t\t\t             " << cube.face[30] << " " << cube.face[31] << " " << cube.face[32] << endl;
    cout << "\t\t\t             " << cube.face[33] << " " << cube.face[34] << " " << cube.face[35] << endl << endl;

    cout << "\t\t\t             " << cube.face[51] << " " << cube.face[48] << " " << cube.face[45] << endl;
    cout << "\t\t\t             " << cube.face[52] << " " << cube.face[49] << " " << cube.face[46] << endl;
    cout << "\t\t\t             " << cube.face[53] << " " << cube.face[50] << " " << cube.face[47] << endl;
}

void read_file_input(RubikCube &original)
{
    ifstream input;                           //Un flux permettant de lire un fichier
    input.open("input.txt");                  //Ouverture du fichier

    if(input)
    {
                                    //L'ouverture s'est bien passée. On peut donc lire

        while(!input.eof())                                     // On crée une boucle que le programme pourra quitter qu'une fois la lecture du fichier terminer
        {
            string content;                                     // On crée un string qui va contenir les transition
            input >> content;                                   // Le string reçoit alors LA transition (car la lecture s'arrête quand un espace ou un saut de ligne apparait)

            const char *permutation_letter = NULL;
            permutation_letter = content.c_str();

            switch(permutation_letter[0])
            {
                case 'A':
                    A(original);
                    break;
                case 'B':
                    B(original);
                    break;
                case 'C':
                    C(original);
                    break;
                case 'D':
                    D(original);
                    break;
                case 'E':
                    E(original);
                    break;
                case 'F':
                    F(original);
                    break;
                case 'G':
                    G(original);
                    break;
                case 'H':
                    H(original);
                    break;
                case 'I':
                    I(original);
                    break;
                case 'J':
                    J(original);
                    break;
                case 'K':
                    K(original);
                    break;
                case 'L':
                    L(original);
                    break;
                case 'M':
                    M(original);
                    break;
                case 'N':
                    N(original);
                    break;
                case 'O':
                    O(original);
                    break;
                case 'P':
                    P(original);
                    break;
                case 'Q':
                    Q(original);
                    break;
                case 'R':
                    R(original);
                    break;
                case 'S':
                    S(original);
                    break;
                case 'T':
                    T(original);
                    break;
                case 'U':
                    U(original);
                    break;
                case 'V':
                    V(original);
                    break;
                case 'W':
                    W(original);
                    break;
                case 'X':
                    X(original);
                    break;
                case 'Y':
                    Y(original);
                    break;
                case 'Z':
                    Z(original);
                    break;
                default:
                    AROBASE(original);
                    break;
            }
        }

    }
    else
    {
        cout << "ERREUR: Impossible d'ouvrir le fichier 'input.txt' en lecture." << endl;
    }

    input.close();
    calculate_heuristic(original);
 }

int compare_RubikCube_face(RubikCube a, RubikCube b)
{
    int result = 1;

    for(int i = 0; i < 54; i++)
    {
        if(a.face[i] != b.face[i])
            result = 0;
    }

    return result;
}

void copy_RubikCube_face(RubikCube &copy, RubikCube original)
{
    for(int i = 0; i < 54; i++)
        copy.face[i] = original.face[i];
}

void calculate_heuristic(RubikCube &cube)
{
    int wrong_color = 0;

    for(int i = 0; i < 54; i ++)
    {
        if(cube.face[i] != (i/9)+1)
            wrong_color++;
    }
    cube.heuristic = wrong_color;
}

void a_star_solver(RubikCube &cube)
{
    int cost = 0;
    vector<RubikCube> opened_list;
    vector<RubikCube> closed_list;
    closed_list.push_back(cube);

    RubikCube current_cube;
    current_cube.face.resize(54);

    while(current_cube.heuristic != 0)
    {
        if(opened_list.size() > 1)
        {
            copy_RubikCube_face(current_cube, opened_list[0]);
            current_cube.heuristic = opened_list[0].heuristic;
            current_cube.cost = opened_list[0].cost;
            int path_chosen = 0;

            for(unsigned int i = 1; i < opened_list.size(); i++)
            {
                if((opened_list[i].heuristic + opened_list[i].cost) <= (current_cube.heuristic + current_cube.cost) && path_chosen != 1)
                {
                    closed_list.push_back(current_cube);
                    copy_RubikCube_face(current_cube, opened_list[i]);
                    current_cube.heuristic = opened_list[i].heuristic;
                    current_cube.cost = opened_list[i].cost;
                    opened_list.erase(opened_list.begin()+(i-1));
                    path_chosen = 1;
                }
            }
        }
        else
        {
            copy_RubikCube_face(current_cube, cube);
            current_cube.heuristic = cube.heuristic;
            current_cube.cost = cube.cost;
        }
        cost++;
        develop_all_permut(current_cube, cost, opened_list, closed_list);

        display_RubikCube(current_cube);
        cout << "nombre d'ouverts : " << opened_list.size() << endl;
        cout << "nombre de fermes : " << closed_list.size() << endl;

        ofstream output;
        string const file("output.txt");
        output.open(file.c_str());

        if(output)
        {
            output << current_cube.permut_letter;
        }
        else
        {
            cout << "ERREUR: Impossible d'ouvrir le fichier output." << endl;
        }
        output.close();

    }
    copy_RubikCube_face(cube, current_cube);
    cube.heuristic = current_cube.heuristic;
    cube.cost = current_cube.cost;
}

void develop_all_permut(RubikCube cube, int cost, vector<RubikCube> &opened_list, vector<RubikCube> &closed_list)
{
    vector<RubikCube> all_permut(27);

    for(unsigned int i = 0; i < all_permut.size(); i++)
    {
        all_permut[i].face.resize(54);
        copy_RubikCube_face(all_permut[i], cube);
    }

    A(all_permut[0]);
    B(all_permut[1]);
    C(all_permut[2]);
    D(all_permut[3]);
    E(all_permut[4]);
    F(all_permut[5]);
    G(all_permut[6]);
    H(all_permut[7]);
    I(all_permut[8]);
    J(all_permut[9]);
    K(all_permut[10]);
    L(all_permut[11]);
    M(all_permut[12]);
    N(all_permut[13]);
    O(all_permut[14]);
    P(all_permut[15]);
    Q(all_permut[16]);
    R(all_permut[17]);
    S(all_permut[18]);
    T(all_permut[19]);
    U(all_permut[20]);
    V(all_permut[21]);
    W(all_permut[22]);
    X(all_permut[23]);
    Y(all_permut[24]);
    Z(all_permut[25]);
    AROBASE(all_permut[26]);

    for(unsigned int i = 0; i < all_permut.size(); i++)
    {
        all_permut[i].cost = cost;
        calculate_heuristic(all_permut[i]);

        for(unsigned int j = 0; j < closed_list.size(); j++)
        {
            if(compare_RubikCube_face(all_permut[i], closed_list[j]) == 1)
            {
                all_permut.erase(all_permut.begin()+(i-1));
            }
            else
            {
                opened_list.push_back(all_permut[i]);
            }
        }
    }
}

        /** Fonctions permettant les permutations de base **/

void basic_permut(RubikCube &original_RubikCube, int a, int b, int c, int d)
{
    int temp = original_RubikCube.face[a];
    original_RubikCube.face[a] = original_RubikCube.face[b];
    original_RubikCube.face[b] = original_RubikCube.face[c];
    original_RubikCube.face[c] = original_RubikCube.face[d];
    original_RubikCube.face[d] = temp;
}

void A(RubikCube &original_RubikCube)
{
    basic_permut(original_RubikCube, 2, 18, 45, 29);
    basic_permut(original_RubikCube, 5, 19, 46, 32);
    basic_permut(original_RubikCube, 8, 20, 47, 35);
    basic_permut(original_RubikCube, 37, 41, 43, 39);
    basic_permut(original_RubikCube, 38, 44, 42, 36);
    original_RubikCube.permut_letter = "A";
}

void B(RubikCube &original_RubikCube)
{
    basic_permut(original_RubikCube, 11, 20, 36, 27);
    basic_permut(original_RubikCube, 14, 23, 37, 28);
    basic_permut(original_RubikCube, 17, 26, 38, 29);
    basic_permut(original_RubikCube, 1, 5, 7, 3);
    basic_permut(original_RubikCube, 0, 2, 8, 6);
    original_RubikCube.permut_letter = "B";
}

void C(RubikCube &original_RubikCube)
{
    basic_permut(original_RubikCube, 0, 9, 53, 38);
    basic_permut(original_RubikCube, 1, 10, 50, 41);
    basic_permut(original_RubikCube, 2, 11, 47, 44);
    basic_permut(original_RubikCube, 26, 24, 18, 20);
    basic_permut(original_RubikCube, 23, 25, 21, 19);
    original_RubikCube.permut_letter = "C";
}

void D(RubikCube &original_RubikCube)
{
    basic_permut(original_RubikCube, 0, 24, 51, 27);
    basic_permut(original_RubikCube, 3, 25, 52, 30);
    basic_permut(original_RubikCube, 6, 26, 53, 33);
    basic_permut(original_RubikCube, 11, 9, 15, 17);
    basic_permut(original_RubikCube, 10, 12, 16, 14);
    original_RubikCube.permut_letter = "D";
}

void E(RubikCube &original_RubikCube)
{
    basic_permut(original_RubikCube, 9, 18, 42, 33);
    basic_permut(original_RubikCube, 12, 21, 43, 34);
    basic_permut(original_RubikCube, 15, 24, 44, 35);
    basic_permut(original_RubikCube, 53, 47, 45, 51);
    basic_permut(original_RubikCube, 50, 46, 48, 52);
    original_RubikCube.permut_letter = "E";
}

void F(RubikCube &original_RubikCube)
{
    basic_permut(original_RubikCube, 6, 15, 51, 36);
    basic_permut(original_RubikCube, 7, 16, 48, 39);
    basic_permut(original_RubikCube, 8, 17, 45, 42);
    basic_permut(original_RubikCube, 27, 33, 35, 29);
    basic_permut(original_RubikCube, 28, 30, 34, 32);
    original_RubikCube.permut_letter = "F";
}

        /** Fonctions "composites" permettant les autres permutations **/

void G(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 3; i++)
    {
        A(original_RubikCube);
    }
    original_RubikCube.permut_letter = "G";
}

void H(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 3; i++)
    {
        B(original_RubikCube);
    }
    original_RubikCube.permut_letter = "H";
}

void I(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 3; i++)
    {
        C(original_RubikCube);
    }
    original_RubikCube.permut_letter = "I";
}

void J(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 3; i++)
    {
        D(original_RubikCube);
    }
    original_RubikCube.permut_letter = "J";
}

void K(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 3; i++)
    {
        E(original_RubikCube);
    }
    original_RubikCube.permut_letter = "K";
}

void L(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 3; i++)
    {
        F(original_RubikCube);
    }
    original_RubikCube.permut_letter = "L";
}

void M(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 2; i++)
    {
        A(original_RubikCube);
    }
    original_RubikCube.permut_letter = "M";
}

void N(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 2; i++)
    {
        B(original_RubikCube);
    }
    original_RubikCube.permut_letter = "N";
}

void O(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 2; i++)
    {
        C(original_RubikCube);
    }
    original_RubikCube.permut_letter = "O";
}

void P(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 2; i++)
    {
        D(original_RubikCube);
    }
    original_RubikCube.permut_letter = "P";
}

void Q(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 2; i++)
    {
        E(original_RubikCube);
    }
    original_RubikCube.permut_letter = "Q";
}

void R(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 2; i++)
    {
        F(original_RubikCube);
    }
    original_RubikCube.permut_letter = "R";
}

void S(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 3; i++)
    {
        A(original_RubikCube);
        D(original_RubikCube);
    }
    original_RubikCube.permut_letter = "S";
}

void T(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 3; i++)
    {
        B(original_RubikCube);
        E(original_RubikCube);
    }
    original_RubikCube.permut_letter = "T";
}

void U(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 3; i++)
    {
        F(original_RubikCube);
        I(original_RubikCube);
    }
    original_RubikCube.permut_letter = "U";
}

void V(RubikCube &original_RubikCube)
{
    A(original_RubikCube);
    D(original_RubikCube);
    original_RubikCube.permut_letter = "V";
}

void W(RubikCube &original_RubikCube)
{
    B(original_RubikCube);
    E(original_RubikCube);
    original_RubikCube.permut_letter = "W";
}

void X(RubikCube &original_RubikCube)
{
    C(original_RubikCube);
    F(original_RubikCube);
    original_RubikCube.permut_letter = "X";
}

void Y(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 2; i++)
    {
        S(original_RubikCube);
    }
    original_RubikCube.permut_letter = "Y";
}

void Z(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 2; i++)
    {
        T(original_RubikCube);
    }
    original_RubikCube.permut_letter = "Z";
}

void AROBASE(RubikCube &original_RubikCube)
{
    for(int i = 0; i < 2; i++)
    {
        U(original_RubikCube);
    }
    original_RubikCube.permut_letter = "@";
}