#include <iostream>
#include <iomanip>

#include <cstring>
#include <cmath>

#include <vector>
#include <set>
#include <queue>

#include <functional>

#include <ctime>
#include <cstdlib>

using namespace std;

const char GOAL_STATE[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0};

class Puzzle
{
protected:
    char puzzle[16];

    int index(char searched) const
    {
        for(int i=0; i<16; i++)
        {
            if (puzzle[i]==searched)
                return i;
        }
        return -1;
    }

public:

    Puzzle(const char init[16] = NULL)
    {
        if(init!=NULL)
        {
            memcpy(puzzle, init, sizeof(char)*16);
        }
        else
        {
            memcpy(puzzle, GOAL_STATE, sizeof(char)*16);
        }
    }

    void show() const
    {
        for(int i=0; i<4; i++)
        {
            for(int j=0; j<4; j++)
            {
                cout << setw(3) << (int)puzzle[i*4+j] << " ";
            }
            cout << endl;
        }
    }

    bool move(int m_pos)
    {
        int b_pos = index(0);
        int b_x = b_pos / 4;
        int b_y = b_pos % 4;
        int x = m_pos / 4;
        int y = m_pos % 4;
        if (m_pos < 16 && (
                    (x == b_x && (y == b_y + 1 || y == b_y - 1)) ||
                    (y == b_y && (x == b_x + 1 || x == b_x - 1))
                )
            )
        {
            char tmp = puzzle[m_pos];
            puzzle[m_pos] = puzzle[b_pos];
            puzzle[b_pos] = tmp;
            return true;
        }
        else
            return false;
    }

    int count_correct() const
    {
        int ret = 0;
        for(int i=0; i<16; i++)
            if ((i<15 && (puzzle[i])==i+1) || (i==15 && puzzle[i]==0))
                ret++;
        return ret;
    }

    vector<int> possible_moves() const
    {
        vector<int> ret;
        int b_pos = index(0);
        int b_x = b_pos / 4;
        int b_y = b_pos % 4;
        ret.push_back(b_y * 4 + b_x - 1);
        ret.push_back((b_y - 1) * 4 + b_x);
        if (b_x<3)
            ret.push_back(b_y * 4 + b_x + 1);
        if (b_y<3)
            ret.push_back((b_y + 1) * 4 + b_x);
        return ret;
    }

};

class AStarPuzzle : public Puzzle
{
    int H;
    int f;

public:

    int tried;

    AStarPuzzle* previous;

    AStarPuzzle(const char init[16] = NULL,
            int _f = 0, int _tried = 0, AStarPuzzle* _previous = NULL) : Puzzle(init)
    {
        f = _f;
        tried = _tried;
        previous = _previous;
    }

    AStarPuzzle (const AStarPuzzle& old) : Puzzle(old.puzzle)
    {
        f = old.f;
        tried = old.tried;
        previous = old.previous;
    }

    double heur() const
    {
        double ret = 0.0;
        for (int goalIndex = 0 ; goalIndex<16; goalIndex++)
        {
            int tileIndex = index( GOAL_STATE[goalIndex] );
            ret += abs((double)((goalIndex % 4) - (tileIndex % 4)));
            ret += abs(floor(goalIndex / 4.0) - floor(tileIndex / 4.0));

        }

        return 0.1*f + max(ret, (double)count_correct());
    }

    bool operator<(const AStarPuzzle& other) const
    {
        return heur()>other.heur();
    }

    int get_f()
    {
        return f;
    }

    void increase_f()
    {
        f++;
    }

    AStarPuzzle operator=(const AStarPuzzle& rhs)
    {
        cout << "STUB: AStarPuzzle::operator=" << endl;
        return *this; /// !!!
    }

    ~AStarPuzzle()
    {
        cout << "STUB: AStarPuzzle::~AStarPuzzle" << endl;
    }


    void operator delete(void *p)
    {
        cout << "Attempting to delete AStarPuzzle?" << endl;
    }

};


struct CompareHeuristics : public std::binary_function<AStarPuzzle*, AStarPuzzle*, bool >
{
    bool operator()(AStarPuzzle* lhs, AStarPuzzle* rhs) const
    {
        return lhs->heur() > rhs->heur();
    }
};

vector<int> retracePath(AStarPuzzle* c)
{
    vector<int> ret;
    while (c->previous!=NULL)
    {
        c = c->previous;
        ret.push_back(c->tried);
    }
    return ret;
}

vector<int> aStar(AStarPuzzle* current)
{
    set<AStarPuzzle*> openList;
    set<AStarPuzzle*> closedList;
    std::priority_queue<AStarPuzzle*, std::vector<AStarPuzzle*>, CompareHeuristics> openHeap;

    int max_corr = 0;
    int min_step = 0;


    openList.insert(current);
    openHeap.push(current);
    while (openList.size()!=0)
    {
        current = openHeap.top();
        cout << "An iteration. heur()==" << current->heur()  << endl;
        current->show();
        openHeap.top();
        if (current->count_correct() == 16)
        {
            //return vector<int>();
            return retracePath(current);
        }
        openList.erase(current);
        closedList.insert(current);
        vector<int> directions = current->possible_moves();
        for(unsigned int i=0; i<directions.size(); i++)
        {
            AStarPuzzle* tile = new AStarPuzzle(*current);
            tile->move(directions[i]);
            tile->increase_f();

            if (closedList.count(tile)==0)
            {
                int corr = tile->count_correct();
                int f = tile->get_f();
                if (corr > max_corr or (corr == max_corr && f < min_step))
                {
                    max_corr = corr;
                    min_step = f;
                    cout << corr << "," << f << endl;
                }
                tile->previous = current;
                if (openList.count(tile)==0)
                {
                    openList.insert(tile);
                    openHeap.push(tile);
                }
            }

        }
    }


    return vector<int>();
}

int main(int argc, char **argv) {

    char shuffled[16] = {0, 3, 7, 5, 9, 12 , 13 , 11, 8, 6 , 14, 4 , 15, 2 , 10 , 1 };
    memcpy(shuffled, GOAL_STATE, sizeof(char)*16);
    srand(time(0));
    for (int i=0; i<16; i++) {
        int r = i + (rand() % (16-i));
        char temp = shuffled[i];
        shuffled[i] = shuffled[r];
        shuffled[r] = temp;
    }

    

    AStarPuzzle* p = new AStarPuzzle(shuffled);
    p->show();
    aStar(p);

    return 0;
}