15-Puzzle BnB A* search

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

#define     endl               "\n"
#define     fast_io            ios::sync_with_stdio(false); cin.tie(0);
#define     file_io            freopen("input.txt", "r", stdin);   \
                               freopen("output.txt", "w", stdout);
#define     all(x)             begin(x), end(x)
#define     debug(x)           cerr <<"Line "<< __LINE__ <<" : "<< #x " = "<< x <<endl;

template<typename T, typename TT>
ostream& operator<<(ostream &os, const pair<T, TT> &t) { return os<<"("<<t.first<<", "<<t.second<<")"; }
template<typename T>
ostream& operator<<(ostream& os, const vector<T> &t) { for(auto& i: t) os<<i<<" "; return os; }



int N;
using ull = unsigned long long int;
using pii = pair<int, int>;






#define LIMIT_DEPTH 60
#define NODE_LIMIT 10000000




// done .. hash for mapping vector in c++
struct VectorHash {
    size_t operator()(const vector<int>& v) const {
        hash<int> hasher;
        size_t seed = 0;
        for (int i : v) {
            seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }
        return seed;
    }
};





// done
vector<int> processInput(string line) {
    /// "1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0"
    vector <int> tokens;
    stringstream ss(line);
    string intermediate;
    // Tokenizing w.r.t. space ' '
    while(getline(ss, intermediate, ',')) {
        tokens.push_back(stoi(intermediate));
    }
    return tokens;
}








//done
int countInversion(const vector<int>& a, const vector<int>& b) {
    assert(a.size() == b.size());
    unordered_map<int, int> pos;
    for(int i = 0; i < (int)b.size(); ++i) pos.insert({b[i], i});
    int c(0);
    for(int i = 0; i < (int)a.size()-1; ++i) {
        for(int j = i + 1; j < (int)a.size(); ++j) {
            if(a[i] && a[j] && pos[a[i]] > pos[a[j]]) {
                ++c;
            }
        }
    }
    return c;
}













class NPuzzle {

    //done
    struct StateNode {
        StateNode* parent;
        vector<int> state;
        pii blank;
        pii cx; // cx = g(x) + h(x) //  g_score + heuristic_cost
        stack<StateNode*> children;

        //done
        explicit StateNode(const vector<int> s, const pii& prevBlank, const pii& newBlank, const int& fx, StateNode* p) {
            parent = p;
            state = s;
            swap(state[prevBlank.first*N + prevBlank.second], state[newBlank.first*N + newBlank.second]);
            blank = newBlank;
            cx = {fx, INT_MAX};
        }

        //done
        friend ostream& operator <<(ostream& out, StateNode* obj) {
            for(int i = 0; i < N; ++i) {
                for(int j = 0; j < N; ++j) {
                    out << obj->state[i*N + j] << '\t';
                }
                cout << endl;
            }
            return out;
        }

        //done
        void printPath() {
            if(this->parent) {
                parent->printPath();
                if(this->blank.first > parent->blank.first) cout << "D" << endl;
                else if(this->blank.first < parent->blank.first) cout << "U" << endl;
                else if(this->blank.second > parent->blank.second) cout << "R" << endl;
                else cout << "L" << endl;
            }
            cout << (this) << endl;
        }

        //done
        ~StateNode() {
            parent = nullptr;
            while(!children.empty()) {
                StateNode* cur = children.top();
                children.pop();

                if(cur) delete cur;
                cur = nullptr;
            }
            state.clear();
        }
    };

    //done losed f_score in heap
    struct comp {
        bool operator()(const StateNode* lhs, const StateNode* rhs) const {
            int lCost = lhs->cx.first + lhs->cx.second;
            int rCost = rhs->cx.first + rhs->cx.second;
            return (lCost == rCost)? lhs->cx.first > rhs->cx.first : lCost > rCost;
        }
    };

    //done
    bool isSafe(const pii& cell) {
        return cell.first >= 0 && cell.second >= 0 && cell.first < N && cell.second < N;
    }

    //done
    // this is heuristic 1 for h(x)
    int hammingDistance(const vector<int>& curr, const vector<int>& goal) {
        int conflicts(0);
        for(int i = 0; i < (int)curr.size(); ++i) {
            if(curr[i] && curr[i] != goal[i]) ++conflicts;
        }
        return conflicts;
    }

    //done
    // this is heuristic 2 for h(x)
    int manhattanDistance(const vector<int>& curr, const vector<int>& goal) {
        vector<pii> indx(N*N);
        int c(0);
        for(int i = 0; i < N*N; ++i) {
            indx[goal[i]] = {i/N, i%N};
        }
        for(int i = 0; i < N*N; ++i) {
            if(curr[i]) c += abs(i/N - indx[curr[i]].first) + abs(i%N - indx[curr[i]].second);
        }
        return c;
    }

    //done
    bool isSolvable(const vector<int>& a, const vector<int>& b, int blankX) {
        int invCount = countInversion(a, b);
        int pos = N - blankX;
        if (N & 1) {
            return !(invCount & 1);
        } else {
            if (pos & 1) return !(invCount & 1);
            else return invCount & 1;
        }
    }

    //done
    int findBlankX(const vector<int>& placeMents) {
        for(int i = 0; i < (int)placeMents.size(); ++i) {
            if(!placeMents[i]) {
                return i/N;
            }
        }
        return -1;
    }

public:

    void solve15puzzle(const vector<int>& initial, const vector<int>& goal,  const pii& blankCell, bool choice = false) {

        vector<int> middle(goal);
        sort(all(middle));
        if(!isSolvable(initial, middle, blankCell.first) || !isSolvable(goal, middle, findBlankX(goal))) {
            cout << "Not Solvable " << endl;
            return;
        } else {
            cout << "Solvable" << endl;
        }

        int expanded(0), maxDepth(0);
        vector<pii> dir({{1, 0}, {0, 1}, {-1, 0}, {0, -1}});




        ///closedSet all are aleary evaluated
        unordered_set< vector<int>, VectorHash > closedList;
        ///stores g_score of each node in openList with minimum
        unordered_map< vector<int>, int, VectorHash > g_score;

        ///list provides node with minimum f_score value
        priority_queue<StateNode*, vector<StateNode*>, comp> openList;





        StateNode* rootNode = new StateNode(initial, blankCell, blankCell, 0, nullptr);

        rootNode->cx.second = choice ? hammingDistance(rootNode->state, goal) : manhattanDistance(rootNode->state, goal);

        g_score[rootNode->state] = 0;

        openList.push(rootNode);

        while(!openList.empty()) {

            StateNode* curr = openList.top();
            //cout << curr->cx << endl;
            //success
            if(!curr->cx.second) {
                cout << curr->cx.first << " steps needed" << endl;
                cout << expanded << " number of nodes expanded" << endl;
                curr->printPath();
                break;
            }

            openList.pop();

            if(!closedList.count(curr->state))
                closedList.insert(curr->state);


            for(const auto& d : dir) {
                int x = d.first + curr->blank.first;
                int y = d.second + curr->blank.second;
                if(!isSafe({x, y})) continue;

                int tentative_g_score = curr->cx.first + 1;
                StateNode* neighbor = new StateNode(curr->state, curr->blank, {x, y}, tentative_g_score, curr);
                curr->children.push(neighbor);
                neighbor->cx.second = choice ? hammingDistance(neighbor->state, goal) : manhattanDistance(neighbor->state, goal);

                if(closedList.find(neighbor->state) != closedList.end()) continue;

                if(!g_score.count(neighbor->state) || tentative_g_score < g_score[neighbor->state]) {
                    neighbor->parent = curr;
                    //if(!g_score.count(neighbor->state)) {
                    //  openList.push(neighbor);
                    //}
                    openList.push(neighbor);
                    g_score[neighbor->state] = tentative_g_score;

                }
            }

            curr = nullptr;
        }

        delete rootNode;
        rootNode = nullptr;
    }

};


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

    /**
    4
    <1, 3, 0, 4, 5, 2, 6, 8, 9, 10, 7, 12, 13, 14, 11, 15>
    <1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 13, 14, 15, 12>
    1
    */

    string str;
    getline(cin, str);
    N = stoi(str);

    vector<int> initial, goal;
    pii blank;

    getline(cin, str);
    initial = processInput(str.substr(1, str.size()-2));

    for(int i = 0; i < N*N; ++i) {
        if(!initial[i]) {
            blank = {i/N, i%N};
            break;
        }
    }

    getline(cin, str);
    goal = processInput(str.substr(1, str.size()-2));

    getline(cin, str);
    bool choice = (str == "1");


    cout << "input: " << initial << endl;
    cout << "target: " << goal << endl;
    cout << "blank at cell: " << blank << endl << endl;

    NPuzzle puzzle;

    auto st = chrono::steady_clock::now();
    //solve puzzle
    puzzle.solve15puzzle(initial, goal, blank, choice);

    auto et = chrono::steady_clock::now();
    cout << "Execution Time: " << chrono::duration<double, milli>(et-st).count() << "ms" << endl << endl;


    return 0;
}