god_edge.cpp

#include <iostream>
#include <cstdint>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>
using namespace std;

// x1 <- x2 <- x3 <- x4 <- x1
void rotate(uint8_t &x1, uint8_t &x2, uint8_t &x3, uint8_t &x4)
{
    uint8_t t = x1;
    x1 = x2;
    x2 = x3;
    x3 = x4;
    x4 = t;
}

struct Cube
{
    vector<uint8_t> EO, EP;

    Cube()
    {
        EO = vector<uint8_t>{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        EP = vector<uint8_t>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    }

    void move(int m)
    {
        switch (m)
        {
        case 0: // U
            rotate(EO[0], EO[3], EO[2], EO[1]);
            rotate(EP[0], EP[3], EP[2], EP[1]);
            break;
        case 1: // U2
            swap(EO[0], EO[2]), swap(EO[3], EO[1]);
            swap(EP[0], EP[2]), swap(EP[3], EP[1]);
            break;
        case 2: // U'
            rotate(EO[0], EO[1], EO[2], EO[3]);
            rotate(EP[0], EP[1], EP[2], EP[3]);
            break;
        case 3: // R
            rotate(EO[1], EO[6], EO[9], EO[5]);
            rotate(EP[1], EP[6], EP[9], EP[5]);
            break;
        case 4: // R2
            swap(EO[1], EO[9]), swap(EO[6], EO[5]);
            swap(EP[1], EP[9]), swap(EP[6], EP[5]);
            break;
        case 5: // R'
            rotate(EO[1], EO[5], EO[9], EO[6]);
            rotate(EP[1], EP[5], EP[9], EP[6]);
            break;
        case 6: // F
            rotate(EO[2], EO[7], EO[10], EO[6]);
            rotate(EP[2], EP[7], EP[10], EP[6]);
            EO[2] ^= 1;
            EO[7] ^= 1;
            EO[10] ^= 1;
            EO[6] ^= 1;
            break;
        case 7: // F2
            swap(EO[2], EO[10]), swap(EO[7], EO[6]);
            swap(EP[2], EP[10]), swap(EP[7], EP[6]);
            break;
        case 8: // F'
            rotate(EO[2], EO[6], EO[10], EO[7]);
            rotate(EP[2], EP[6], EP[10], EP[7]);
            EO[2] ^= 1;
            EO[6] ^= 1;
            EO[10] ^= 1;
            EO[7] ^= 1;
            break;
        case 9: // D
            rotate(EO[8], EO[9], EO[10], EO[11]);
            rotate(EP[8], EP[9], EP[10], EP[11]);
            break;
        case 10: // D2
            swap(EO[8], EO[10]), swap(EO[9], EO[11]);
            swap(EP[8], EP[10]), swap(EP[9], EP[11]);
            break;
        case 11: // D'
            rotate(EO[8], EO[11], EO[10], EO[9]);
            rotate(EP[8], EP[11], EP[10], EP[9]);
            break;
        case 12: // L
            rotate(EO[3], EO[4], EO[11], EO[7]);
            rotate(EP[3], EP[4], EP[11], EP[7]);
            break;
        case 13: // L2
            swap(EO[3], EO[11]), swap(EO[4], EO[7]);
            swap(EP[3], EP[11]), swap(EP[4], EP[7]);
            break;
        case 14: // L'
            rotate(EO[3], EO[7], EO[11], EO[4]);
            rotate(EP[3], EP[7], EP[11], EP[4]);
            break;
        case 15: // B
            rotate(EO[0], EO[5], EO[8], EO[4]);
            rotate(EP[0], EP[5], EP[8], EP[4]);
            EO[0] ^= 1;
            EO[5] ^= 1;
            EO[8] ^= 1;
            EO[4] ^= 1;
            break;
        case 16: // B2
            swap(EO[0], EO[8]), swap(EO[5], EO[4]);
            swap(EP[0], EP[8]), swap(EP[5], EP[4]);
            break;
        case 17: // B'
            rotate(EO[0], EO[4], EO[8], EO[5]);
            rotate(EP[0], EP[4], EP[8], EP[5]);
            EO[0] ^= 1;
            EO[4] ^= 1;
            EO[8] ^= 1;
            EO[5] ^= 1;
            break;
        }
    }

    uint64_t compress() const
    {
        uint64_t c = 0;
        for (int i=0; i<12; i++)
        {
            c *= 12;
            c += EP[i];
            c *= 2;
            c += EO[i];
        }
        return c;
    }

    void decompress(uint64_t c)
    {
        for (int i=11; i>=0; i--)
        {
            EO[i] = c%2;
            c /= 2;
            EP[i] = c%12;
            c /= 12;
        }
    }

    string str() const
    {
        vector<string> E = {"UB", "UR", "UF", "UL", "BL", "BR", "FR", "FL", "DB", "DR", "DF", "DL"};

        auto e = [&](int p, int o) -> char
        {
            return E[EP[p]][(2-EO[p]+o)%2];
        };
        auto c = [&](int p, int o) -> char
        {
            return '.';
        };

        string res = string() +
            ' '      + ' '      + ' '      + c( 0, 0) + e( 0, 0) + c( 1, 0) + '\n' +
            ' '      + ' '      + ' '      + e( 3, 0) + 'U'      + e( 1, 0) + '\n' +
            ' '      + ' '      + ' '      + c( 3, 0) + e( 2, 0) + c( 2, 0) + '\n' +
            c( 0, 1) + e( 3, 1) + c( 3, 2) + c( 3, 1) + e( 2, 1) + c( 2, 2) + c( 2, 1) + e( 1, 1) + c( 1, 2) + c( 1, 1) + e( 0, 1) + c( 0, 2) + '\n' +
            e( 4, 1) + 'L'      + e( 7, 1) + e( 7, 0) + 'F'      + e( 6, 0) + e( 6, 1) + 'R'      + e( 5, 1) + e( 5, 0) + 'B'      + e( 4, 0) + '\n' +
            c( 4, 2) + e(11, 1) + c( 7, 1) + c( 7, 2) + e(10, 1) + c( 6, 1) + c( 6, 2) + e( 9, 1) + c( 5, 1) + c( 5, 2) + e( 8, 1) + c( 4, 1) + '\n' +
            ' '      + ' '      + ' '      + c( 7, 0) + e(10, 0) + c( 6, 0) + '\n' +
            ' '      + ' '      + ' '      + e(11, 0) + 'D'      + e( 9, 0) + '\n' +
            ' '      + ' '      + ' '      + c( 4, 0) + e( 8, 0) + c( 5, 0) + '\n';

        string colored;
        for (char c: res)
            switch (c)
            {
            case 'U': colored += "\x1b[47mU \x1b[0m"; break;
            case 'D': colored += "\x1b[43mD \x1b[0m"; break;
            case 'L': colored += "\x1b[45mL \x1b[0m"; break;
            case 'R': colored += "\x1b[41mR \x1b[0m"; break;
            case 'F': colored += "\x1b[42mF \x1b[0m"; break;
            case 'B': colored += "\x1b[44mB \x1b[0m"; break;
            case '.': colored += ".."; break;
            case ' ': colored += "  "; break;
            case '\n': colored += "\n"; break;
            default:
                colored += "ERROR";
            }

        return colored;
    }
};

int main()
{
    const int N = 7;

    unordered_map<uint64_t, int> T;

    Cube cube;
    T[cube.compress()] = 0;

    for (int i=0; i<N; i++)
    {
        unordered_set<uint64_t> S;

        for (auto it: T)
            if (it.second==i)
            {
                cube.decompress(it.first);
                for (int m=0; m<18; m++)
                {
                    cube.move(m);
                    uint64_t c = cube.compress();
                    if (T.count(c)==0)
                        S.insert(c);
                    cube.move(m/3*3+2-m%3);
                }
            }
        for (uint64_t c: S)
            T[c] = i+1;
        cout<<i+1<<"/"<<N<<": "<<S.size()<<endl;
    }

    vector<int> C(21);

    for (int i=0; i<10000; i++)
    {
        if (i%100==0)
            cout<<i<<"/"<<10000<<endl;

        Cube cube;
        for (int i=11; i>=0; i--)
            swap(cube.EP[i], cube.EP[rand()%(i+1)]);
        for (int i=0; i<11; i++)
            if (rand()%2==0)
            {
                cube.EO[i] ^= 1;
                cube.EO[11] ^= 1;
            }

        for (int md=0; ; md++)
        {
            function<int(int, int)> f = [&](int d, int pm)
            {
                if (T.count(cube.compress())>0)
                    return d+T[cube.compress()];
                if (d>=md)
                    return -1;

                for (int m=0; m<18; m++)
                    if (pm==-1 || m/3!=pm/3)
                    {
                        cube.move(m);
                        int t = f(d+1, m);
                        cube.move(m/3*3+2-m%3);
                        if (t>=0)
                            return t;
                    }

                return -1;
            };

            int t = f(0, -1);
            if (t>=0)
            {
                C[t]++;
                break;
            }
        }
    }
    for (int i=0; i<=20; i++)
        if (C[i]>0)
            cout<<i<<": "<<C[i]<<endl;

    //vector<int> C(21);

    //for (int eo=0; eo<1<<11; eo++)
    //{
    //    vector<uint8_t> ep;
    //    for (int i=0; i<12; i++)
    //        ep.push_back(i);
    //    do
    //    {
    //        cube.EO[11] = 0;
    //        for (int i=0; i<11; i++)
    //        {
    //            cube.EO[i] = eo>>i&1;
    //            cube.EO[11] ^= eo>>i&1;
    //        }
    //        cube.EP = ep;

    //        for (int md=0; ; md++)
    //        {
    //            function<int(int)> f = [&](int d)
    //            {
    //                if (T.count(cube.compress())>0)
    //                    return d+T[cube.compress()];
    //                if (d>=md)
    //                    return -1;

    //                for (int m=0; m<18; m++)
    //                {
    //                    cube.move(m);
    //                    int t = f(d+1);
    //                    cube.move(m/3*3+2-m%3);
    //                    if (t>=0)
    //                        return t+1;
    //                }

    //                return -1;
    //            };

    //            int t = f(0);
    //            if (t>=0)
    //            {
    //                C[t]++;
    //                break;
    //            }
    //        }
    //    }
    //    while (next_permutation(ep.begin(), ep.end()));

    //    cout<<(eo+1)*479001600LL<<"/"<<(1<<11)*479001600LL<<endl;
    //    for (int i=0; i<=20; i++)
    //        if (C[i]>0)
    //            cout<<i<<": "<<C[i]<<endl;
    //}
}