Skip to content

Instantly share code, notes, and snippets.

@kusano

kusano/god_edge.cpp

Created November 27, 2023 16:00
Show Gist options
  • Save kusano/a5736dc66b0f219ce4f5678fe3eea332 to your computer and use it in GitHub Desktop.
Save kusano/a5736dc66b0f219ce4f5678fe3eea332 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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;
//}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment