std::logic_error

// fifteen.cpp : Defines the entry point for the console application.
//

#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <iomanip>
#include <ctime>
#include <math.h>
#include <queue>
#include <stack>
#include <vector>
#include <deque>

using namespace std;

int * ulozone;
vector < int *> odwiedzone;
//int w, k;
int gotowaTablica[ 16 ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 0, 14, 15 };
//int gotowaTablica[16] = {0,1,2,7,8,9,12,10,13,3,6,4,15,14,11,5};

bool trackMode = true;



struct Stan
{
    int priorytet;
    string ruchy;
    int * tablicaStanu;
    string odwiedzoneDzieci;
   
    Stan( string _ruchy, int * _tablicaStanu )
    {
        ruchy = _ruchy;
        tablicaStanu = _tablicaStanu;
    };
    Stan( string _ruchy, int * _tablicaStanu, int _wartosc )
    {
        ruchy = _ruchy;
        tablicaStanu = _tablicaStanu;
        priorytet = _wartosc;
    };
    Stan()
    { };
};



static bool porownajTablice( int * tablica1, int * tablica2 )
{
    for( int i = 0; i < 4; i++ )
    for( int j = 0; j < 4; j++ )
         if( tablica1[ i * 4 + j ] != tablica2[ i * 4 + j ] ) return false;
   
    return true;
}
static bool znajdzWOdwiedzonych( int * array )
{
    for( int i = 0; i <( int ) odwiedzone.size(); i++ )
    {
        if( porownajTablice( array, odwiedzone[ i ] ) ) return true;
       
    }
    return false;
}
static void znajdzPusty( int * array, int & w0, int & k0 )
{
    for( int i = 0; i < 4; i++ )
    {
        for( int j = 0; j < 4; j++ )
        {
            if( array[ i * 4 + j ] == 0 ) { w0 = i; k0 = j; return; };
        }
    }
}

static Stan * przesuniecieUkladanki( Stan * stan, string kierunek )
{
    string ruchy = string( stan->ruchy );
    if(( ruchy.substr( int( ruchy.length() ) ) == "G" && kierunek == "D" ) ||
    ( ruchy.substr( int( ruchy.length() ) ) == "D" && kierunek == "G" ) ||
    ( ruchy.substr( int( ruchy.length() ) ) == "L" && kierunek == "P" ) ||
    ( ruchy.substr( int( ruchy.length() ) ) == "P" && kierunek == "L" ) )
         return 0;
   
    int * nowaTablica = new int[ 16 ];
   
    for( int i = 0; i < 4; i++ )
    for( int j = 0; j < 4; j++ )
         nowaTablica[ i * 4 + j ] = stan->tablicaStanu[ i * 4 + j ];
   
    int w0, k0;
    znajdzPusty( nowaTablica, w0, k0 );
    if( kierunek == "G" && w0 > 0 )
    {
        ruchy += "G";
        nowaTablica[ w0 * 4 + k0 ] = nowaTablica[( w0 - 1 ) * 4 + k0 ];
        nowaTablica[( w0 - 1 ) * 4 + k0 ] = 0;
    }
    if( kierunek == "D" && w0 < 3 )
    {
        ruchy += "D";
        nowaTablica[ w0 * 4 + k0 ] = nowaTablica[( w0 + 1 ) * 4 + k0 ];
        nowaTablica[( w0 + 1 ) * 4 + k0 ] = 0;
    }
    if( kierunek == "P" && k0 < 3 )
    {
        ruchy += "P";
        nowaTablica[ w0 * 4 + k0 ] = nowaTablica[ w0 * 4 + k0 + 1 ];
        nowaTablica[ w0 * 4 + k0 + 1 ] = 0;
    }
    if( kierunek == "L" && k0 > 0 )
    {
        ruchy += "L";
        nowaTablica[ w0 * 4 + k0 ] = nowaTablica[ w0 * 4 + k0 - 1 ];
        nowaTablica[ w0 * 4 + k0 - 1 ] = 0;
    }
    return new Stan( ruchy, nowaTablica );
   
}

int funkcjaHeurystyk( int * tablicaStanu, int kroki )
{
    int wartosc = 0;
    //id (kroki) = 1 liczymy ilosc plytek na zlych miejscach,
    //2 - liczymy sume ilosci krokow do osiagniecia odpowiedniego ustawienia plytek wg normy Manhatan
    if( kroki == 1 ) // pierwsza heurystyka
    {
        for( int i = 0; i < 16; i++ )
             if( tablicaStanu[ i ] != ulozone[ i ] ) wartosc++;
       
    }
    else // druga heurystyka
    {
        int j;
        int wi, ki, wj, kj;
        for( int i = 0; i < 16; i++ )
        {
            for( j = 0; j < 16; j++ )
            {
                if( tablicaStanu[ i ] == ulozone[ j ] ) break;
               
            }
            wi = i / 4;
            ki = i % 4;
            wj = j / 4;
            kj = j % 4;
            wartosc += abs( wi - wj ) + abs( ki - kj );
        }
    }
    return wartosc;
}

int * wczytajWartosci( int w, int k )
{
    int * tablica = new int[ w * k ];
    for( int j = 0; j < w; j++ )
    {
       
        string temp;
        getline( cin, temp );
        int spaceindeks = 0;
        int spaceindeks2 =( int ) temp.find_first_of( ' ', spaceindeks );
       
        for( int i = 0; i < k; i++ )
        {
            string temp2 = temp.substr( spaceindeks, spaceindeks2 - spaceindeks );
            istringstream strumien( temp2 );
            strumien >> tablica[ j * k + i ];
           
            spaceindeks = spaceindeks2 + 1;
            spaceindeks2 =( int ) temp.find_first_of( ' ', spaceindeks + 1 );
            strumien.clear();
        }
       
    }
   
    return tablica;
}

void wyswietlTablice( Stan * stan )
{
    for( int i = 0; i < 4; i++ )
    {
        for( int j = 0; j < 4; j++ )
        {
            cout << stan->tablicaStanu[ i * 4 + j ] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int main( int argc, char * argv[] )
{
   
    string wynik = "";
    string wk;
    string temp;
    int iteracje = 0;
   
   
   
    //tworzymy tablice ulozone z stanem ukladanki do ktorego dazymy
    ulozone = new int[ 16 ];
    for( int i = 0; i < 4; i++ )
    for( int j = 0; j < 4; j++ )
         ulozone[ i * 4 + j ] = i * 4 + j + 1;
   
    ulozone[ 15 ] = 0;
    iteracje = 0;
   
    //flaga mówiąca o tym czy wynik został odnaleziony
    bool flag = false;
   
    //tablicaWejsciowa
    odwiedzone.push_back( gotowaTablica );
   
    stack < Stan *> stos;
    Stan * stan = new Stan( "", gotowaTablica );
    Stan * tmpStan;
    stan->odwiedzoneDzieci = "";
    deque < Stan *> stany;
   
    string kroki[ 4 ];
    kroki[ 0 ] = "P";
    kroki[ 1 ] = "D";
    kroki[ 2 ] = "G";
    kroki[ 3 ] = "L";
   
    // string algorytm = "nn";
    int heurystyka = 1; // jak 1 to pierwsza jak cos innego to druga heurystyka
   
   
    if( string( argv[ 1 ] ) == "-d" || string( argv[ 1 ] ) == "--dfs" )
    {
        if( argc > 2 )
        for( int i = 0; i < 4; i++ )
             kroki[ i ] = argv[ 2 ][ i ];
        //if ( algorytm =="dfs")
        //{
       
        stos.push( stan );
        while( !flag )
        {
            if( iteracje > 15000 ) break;
           
            for( int j = 0; j < 4; j++ )
            {
                int indeks = stos.top()->odwiedzoneDzieci.find( kroki[ j ] );
                if( indeks < 0 )
                {
                    stos.top()->odwiedzoneDzieci += kroki[ j ];
                   
                    stan = przesuniecieUkladanki( stos.top(), kroki[ j ] );
                   
                    if( stan != 0 )
                    {
                        stan->odwiedzoneDzieci = "";
                        if( stan->tablicaStanu != 0 )
                        {
                           
                            if( !znajdzWOdwiedzonych( stan->tablicaStanu ) )
                            {
                                stos.push( stan );
                                wyswietlTablice( stan );
                                odwiedzone.push_back( stan->tablicaStanu );
                                if( porownajTablice( stan->tablicaStanu, ulozone ) )
                                {
                                   
                                    flag = true;
                                    wynik = stan->ruchy;
                                    iteracje++;
                                    break;
                                }
                            }
                        }
                        if( trackMode )
                        {
                            cout << endl;
                            system( "PAUSE" );
                            cout << endl;
                        }
                        iteracje++;
                    }
                }
            }
            while( stos.top()->odwiedzoneDzieci.length() == 4 )
            {
                stos.pop();
            }
            if( flag ||( int ) stos.size() == 0 ) break;
           
        }
    }
    if( string( argv[ 1 ] ) == "-b" || string( argv[ 1 ] ) == "--bfs" )
    {
        if( argc > 2 )
        for( int i = 0; i < 4; i++ )
             kroki[ i ] = argv[ 2 ][ i ];
        //if(algorytm == "bfs")
        //{
        int glebokosc = 0;
        while( !flag )
        {
            if( iteracje > 15000 ) break;
           
            for( int j = 0; j < 4; j++ )
            {
                int indeks = stan->odwiedzoneDzieci.find( kroki[ j ] );
                if( indeks < 0 )
                {
                    stan->odwiedzoneDzieci += kroki[ j ];
                    tmpStan = przesuniecieUkladanki( stan, kroki[ j ] );
                    if( tmpStan != 0 )
                    {
                        tmpStan->odwiedzoneDzieci = "";
                        if( tmpStan->tablicaStanu != 0 )
                        {
                           
                            if( !znajdzWOdwiedzonych( tmpStan->tablicaStanu ) )
                            {
                                stany.push_back( tmpStan );
                                wyswietlTablice( stan );
                                wyswietlTablice( tmpStan );
                                odwiedzone.push_back( tmpStan->tablicaStanu );
                                if( porownajTablice( tmpStan->tablicaStanu, ulozone ) )
                                {
                                   
                                    flag = true;
                                    wynik = tmpStan->ruchy;
                                    iteracje++;
                                    break;
                                }
                            }
                        }
                        if( trackMode )
                        {
                            cout << endl;
                            system( "PAUSE" );
                            cout << endl;
                        }
                        iteracje++;
                    }
                }
            }
            if( stan->odwiedzoneDzieci.length() == 4 )
            {
                stan = stany.at( 0 );
                stany.pop_front();
            }
            if( flag ) break;
           
        }
    }
    if( string( argv[ 1 ] ) == "-n" || string( argv[ 1 ] ) == "--nn" )
    {
        if( argc > 2 )
        {
            string temp = argv[ 2 ];
            heurystyka = atoi( temp.c_str() );
        }
        //if(algorytm == "nn")
        //{
        Stan najlepszy;
        vector < int > priorytet;
        while( !flag )
        {
           
            if( iteracje > 15000 ) break;
           
            for( int j = 0; j < 4; j++ )
            {
                int indeks = stan->odwiedzoneDzieci.find( kroki[ j ] );
                if( indeks < 0 )
                {
                    stan->odwiedzoneDzieci += kroki[ j ];
                    tmpStan = przesuniecieUkladanki( stan, kroki[ j ] );
                    if( tmpStan != 0 )
                    {
                        tmpStan->odwiedzoneDzieci = "";
                        if( tmpStan->tablicaStanu != 0 )
                        {
                           
                            if( !znajdzWOdwiedzonych( tmpStan->tablicaStanu ) )
                            {
                                stany.push_back( tmpStan );
                                cout << "\n Obecny stan\n";
                                wyswietlTablice( stan );
                                cout << "\n Stan sprawdzany\n";
                                wyswietlTablice( tmpStan );
                                priorytet.push_back( funkcjaHeurystyk( tmpStan->tablicaStanu, heurystyka ) );
                                odwiedzone.push_back( tmpStan->tablicaStanu );
                                if( porownajTablice( tmpStan->tablicaStanu, ulozone ) )
                                {
                                   
                                    flag = true;
                                    wynik = tmpStan->ruchy;
                                    iteracje++;
                                    break;
                                }
                            }
                        }
                       
                        if( trackMode )
                        {
                            cout << endl;
                            system( "PAUSE" );
                            cout << endl;
                            iteracje++;
                        }
                    }
                }
            }
            int min = 1000;
            int minpos = 0;
            for( int i = 0; i < priorytet.size(); i++ )
            {
                if( min > priorytet[ i ] )
                {
                    min = priorytet[ i ];
                    minpos = i;
                }
            }
            if( stan->odwiedzoneDzieci.length() == 4 && min != 1000 )
            {
                stan = stany.at( minpos );
                stany.clear();
                priorytet.clear();
            }
            if( min == 1000 ) flag = true;
           
            if( flag ) break;
           
        }
    }
    cout << "\n wynik : " << wynik;
    cout << endl;
    system( "PAUSE" );
    return EXIT_SUCCESS;
}