2gensq1

#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <sstream>
using namespace std;

int size;
bool useMiddle=0;
unsigned char *states;
string filename;

struct puzzle{
    unsigned char pieces[18];
    unsigned char pieces2[12];
    bool middleFlipped;

    puzzle(){
        pieces[0]=1;
        pieces[1]=1;
        pieces[2]=2;
        pieces[3]=3;
        pieces[4]=3;
        pieces[5]=4;
        pieces[6]=5;
        pieces[7]=5;
        pieces[8]=6;
        pieces[9]=7;
        pieces[10]=7;
        pieces[11]=8;
        pieces[12]=9;
        pieces[13]=10;
        pieces[14]=10;
        pieces[15]=11;
        pieces[16]=12;
        pieces[17]=12;
        middleFlipped = 0;
    }

    void stringToPos(string str){
        for(int aa=0; aa<12; aa++){
            pieces2[aa]=str.at(aa)-'a'+1;
        }

        int extra=0;
        for(int aa=0; aa<12; aa++){
            pieces[aa+extra]=pieces2[aa];
            if(pieces2[aa]==1||pieces2[aa]==3||pieces2[aa]==5||pieces2[aa]==7||pieces2[aa]==10||pieces2[aa]==12){
                pieces[aa+extra+1]=pieces2[aa];
                extra++;
            }
        }

        if(str.length()==13) middleFlipped = str.at(12)-'0';
        else middleFlipped=0;
    }

    int posToInt(){
        int extra=0;
        for(int aa=0; aa<17; aa++){
            pieces2[aa-extra]=pieces[aa];
            if(pieces[aa]==pieces[aa+1]) extra++;
        }
        pieces2[11]=pieces[17];
        int t = 0;
        for(int i=0; i<12; i++){
            t*=(12-i);
            for(int j=i+1; j<12; j++){
                if(pieces2[i] > pieces2[j]) t++;
            }
        }
        return ((middleFlipped&&useMiddle)?(t+479001600):t);
    }

    void intToPos(int t){
        middleFlipped=t/479001600;
        pieces2[11]=1;
        for(int i=11; i>=1; i--){
            pieces2[i-1] = 1+(t%(13-i));
            t/=(13-i);
            for(int j=i+1; j<=12; j++){
                if(pieces2[j-1] >= pieces2[i-1]) pieces2[j-1]++;
            }
        }
        int extra=0;
        for(int aa=0; aa<12; aa++){
            pieces[aa+extra]=pieces2[aa];
            if(pieces2[aa]==1||pieces2[aa]==3||pieces2[aa]==5||pieces2[aa]==7||pieces2[aa]==10||pieces2[aa]==12){
                pieces[aa+extra+1]=pieces2[aa];
                extra++;
            }
        }
    }

    void doMove(){
        unsigned char temp = pieces[11];
        for(int aa=11; aa>0; aa--) pieces[aa] = pieces[aa-1];
        pieces[0] = temp;
    }

    bool canDoSlice(){
        return !(pieces[0]==pieces[11]||pieces[5]==pieces[6]);
    }

    void doSlice(){
        unsigned char temp;
        for(int aa=0; aa<6; aa++){
            temp = pieces[6+aa];
            pieces[6+aa] = pieces[12+aa];
            pieces[12+aa] = temp;
        }
        middleFlipped=(!middleFlipped);
    }
};

void getSolution(puzzle p, string sol){
    int d = states[p.posToInt()];
    if(d==0){
        cout<<sol<<"\n";
        return;
    }

    stringstream stream;
    int m;

    for(int aa=0; aa<12; aa++){
        p.doMove();
        if(!p.canDoSlice()) continue;
        if(states[p.posToInt()]==d-1){
            stream.str("");
            m=(aa+1)%12;
            if(m>6) m-=12;
            stream<<m;
            getSolution(p, sol+stream.str());
        }
    }
    p.doSlice();
    if(states[p.posToInt()]==d-1) getSolution(p, sol+"/");
}

bool goodInput(string input){
    if(input.length() != 12 && input.length() != 13) return false;
    if(input.length() == 13) if(input.at(12) != '1') return false;
    bool chars[12]={1,1,1,1,1,1,1,1,1,1,1,1};
    for(int aa=0; aa<12; aa++){
        if(input.at(aa)-'a'>11 || input.at(aa)-'a'<0) return false;
        if(chars[input.at(aa)-'a']!=0) chars[input.at(aa)-'a']=0;
        else return false;
    }
    for(int aa=0; aa<12; aa++) if(chars[aa]) return false;
    return true;
}

int main(){
    puzzle p = puzzle();

    char m;
    cout<<"Include middle layer? (y/n) ";
    cin>>m;
    if(m=='y') useMiddle=true;
    else if(m=='n') useMiddle=false;
    else exit(-1);

    if(useMiddle){
        filename="sq1_2gen_middle.table";
        size=958003200;
        cout<<"Loading solver (with middle layer).\n";
    }
    else{
        filename="sq1_2gen.table";
        size=479001600;
        cout<<"Loading solver (ignoring middle layer).\n";
    }

    int depth = 0;
    int newPositions;
    int totalPositions = 1;
    int index;

    states = new unsigned char[size];
    ifstream file(filename.c_str(), ios_base::binary);
    if(!file.fail()){
        cout<<"Table found on file.\n\n";
        char b;
        for(int aa=0; aa<size; aa++){
            file.read(&b, 1);
            states[aa]=b;
        }
        file.close();
    }
    else{
        for(int aa=0; aa<size; aa++) states[aa]=255;
        cout<<"depth\tpositions\n0\t1\n";
        states[p.posToInt()]=0;
        do{
            newPositions = 0;
            for(int aa=0; aa<size; aa++){
                if(states[aa]!=depth) continue;
                p.intToPos(aa);
                if(!p.canDoSlice()) continue;
                for(int ab=0; ab<11; ab++){
                    p.doMove();
                    if(!p.canDoSlice()) continue;
                    index = p.posToInt();
                    if(states[index]==255){
                        states[index]=depth+1;
                        newPositions++;
                    }
                }
                p.doMove();
                p.doSlice();
                index = p.posToInt();
                if(states[index]==255){
                    states[index]=depth+1;
                    newPositions++;
                }
            }
            depth++;
            totalPositions+=newPositions;
            cout << depth << "\t" << newPositions << "\n";
        }
        while(newPositions != 0);
        cout<<totalPositions<<" positions\n\n";

        ofstream table(filename.c_str(), ios_base::binary);
        for(int aa=0; aa<size; aa++) table<<states[aa];
        table.close();
    }

    string input;
    bool c;
    while(1){
        c=false;
        cout<<"Position: ";
        cin>>input;
        if(!goodInput(input)){
            cout<<"Bad input.\n\n";
            continue;
        }

        p.stringToPos(input);
        index=p.posToInt();
        if(states[index] == 255){
            cout<<"Bad input.\n\n";
            continue;
        }

        cout<<"\nPosition is at depth "<<(int)states[p.posToInt()]<<"\n";
        cout<<"Optimal solutions:\n";
        getSolution(p, "");
        cout<<"\n";
    }

    return 0;
}