Gena Playing Hanoi

• Time : O(n * 2^n)
• Space : O(2^n)

c++

int hashOf(vector<int>& A) {
    int hash = 0;
    for(int i = 0; i < A.size(); i++) {
        hash += A[i] << (2 * i);
    }
    return hash;
}

int hanoi(vector<int> posts) {
    int res = 0;
    while(!posts.empty() and posts.back() == 1) posts.pop_back();
    if(posts.empty()) return 0;
    unordered_set<long long> us;
    queue<vector<int>> q;
    q.push(posts);
    us.insert(hashOf(posts));
    while(!q.empty()) {
        int sz = q.size();
        while(sz--) {
            auto A = q.front(); q.pop();
            int mask = 0, n = A.size();
            for(int i = 0; i < n and __builtin_popcount(mask) < 3; i++) {
                if(mask & (1<< A[i])) continue;
                mask |= (1 << A[i]);
                for(int j = 1; j <= 4; j++) {
                    if(mask & (1<<j)) continue;
                    if(i == n - 1 and j == 1) {
                        A.pop_back();
                        if(A.empty()) return res + 1;
                        int hash = hashOf(A);
                        if(!us.count(hash)) {
                            us.insert(hash);
                            q.push(A);
                        }
                        break;
                    }
                    int o = A[i];
                    A[i] = j;
                    int hash = hashOf(A);
                    if(!us.count(hash)) {
                        us.insert(hash);
                        q.push(A);
                    }

                    A[i] = o;
                }
            }
        }
        res++;
    }
    return -1;
}