#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <stdlib.h>
#include <time.h>
#include "transformationmatrix.txt"
#define cubedatatypesize 35
#define prevmoveindex (22+depth)
#define break_on_find 1
using namespace std;
class cube{
public:
cube(){
char penguin[]="ppppwwwwbbbbyyyyoooorrrr";
for (int i=0;i<24;i++)
c[i]=penguin[i];
c[24]=9;
}
cube(char n[]){
for (int i=0;i<cubedatatypesize;i++)
c[i]=n[i];
}
cube(const cube &x, char i,char depth){
char* z=M+i*24;
int p=0;
for (;p<24;p++)
c[p]=x.c[z[p]];
for (;p<23+depth;p++)
c[p]=x.c[p];
c[p++]=i;
c[p]=9;
}
cube(int numtwists){//random cube constructor
char penguin[]="ppppwwwwbbbbyyyyoooorrrr";
for (int i=0;i<24;i++)
c[i]=penguin[i];
c[24]=9;
for (int i=1;i<=numtwists;i++)
randtwist(i);
}
int findlmi(){
int lmi=24;
for (;c[lmi]!=9 and lmi<cubedatatypesize;lmi++);
return lmi-1;
}
void randtwist(int depth){//Add random twist
int m;
if (depth==1)
m=rand()%9;
else{
int lmr=c[depth+22]/3;
m=rand()%6;
if (lmr==0) m+=3;
else if (lmr==1 and m>2) m+=3;
}
cube b(*this,m,depth);
int i=0;
for (;i<24+depth and i<cubedatatypesize;i++)
c[i]=b.c[i];
if (i!=cubedatatypesize) c[i]=9;
}
void twistchain(char* n){
int i=0;
for (;n[i]!=0;i++);
cout<<i<<endl;
for (int j=1;j<=i;j++){
cube b(*this,n[j-1]-48,j);
int k=0;
for (;b.c[k]!=9 and k<cubedatatypesize;k++)
c[k]=b.c[k];
if (k!=cubedatatypesize) c[k]=9;
}
}
cube& operator=(const cube &rhs){
for (int i=0;i<cubedatatypesize;i++)
c[i]=rhs.c[i];
return *this;
}
bool operator<(const cube &rhs) const{
for (int i=0;i<24;i++)
if (c[i]==rhs.c[i]) continue;
else return(c[i]<rhs.c[i]);
return 0;
}
bool operator==(cube &rhs){
for (int i=0;i<24;i++)
if (c[i]!=rhs.c[i]) return 0;
return 1;
}
void print(){ print(findlmi()-23); }
void printmovelist(int depth){
char m[]="R R2 R' U U2 U' F F2 F' ";
for (int i=24;i<24+depth;i++)
cout<<m[3*c[i]]<<m[3*c[i]+1]<<m[3*c[i]+2];
cout<<endl;
}
void print(int depth){
for (int i=0;i<24;i++)
cout<<c[i];
cout<<": ";
printmovelist(depth);
}
void write(int depth, ofstream &out){
for (int i=0;i<24;i++)
out<<c[i];
out<<" ";
char m[]="R R2 R' U U2 U' F F2 F' ";
for (int i=24;i<24+depth;i++)
out<<m[3*c[i]]<<m[3*c[i]+1]<<m[3*c[i]+2];
out<<endl;
}
char c[cubedatatypesize];
};
//int expand(cube &x, vector<cube> &bottom,int depth, cube &scrambled,vector<cube> &sol){
//// cout<<"expandc";
// int skip=x.c[22+depth]-x.c[22+depth]%3;
// int i=0;
// for (;i<skip;i++){
// bottom.push_back(cube(x,i,depth));
// if (bottom.back()==scrambled) {/*bottom.back().print(depth);*/sol.push_back(bottom.back());return 1;}
// }
// for (i+=3;i<9;i++){
// bottom.push_back(cube(x,i,depth));
// if (bottom.back()==scrambled) {/*bottom.back().print(depth);*/sol.push_back(bottom.back());return 1;}
// }
// return 0;
//}
//int expandvector(vector<cube> &top,vector<cube> &bottom,int depth, cube &scrambled,vector<cube> &sol){
//// cout<<"expandv top size="<<top.size()<<endl;
// int rv=0;
// for (vector<cube>::iterator i=top.begin();i<top.end();i++){
// rv=expand(*i,bottom,depth, scrambled,sol);
// if (rv) {/*cout<<"rv="<<rv; */break;}
// }
// return rv;
//}
//int expandvectormemorymanager(vector<cube>* &vp1,int depthlevelstart,int depthlevelend,cube &scrambled,vector<cube> &sol){
// int rv=0;
// for (int depth=depthlevelstart;depth<=depthlevelend;depth++){
//// cout<<"depth:"<<depth<<" depthlevelend:"<<depthlevelend<<endl;
// vector<cube>* vp2 = new vector<cube>;
// rv=expandvector(*vp1,*vp2,depth,scrambled,sol);//dereference then pass by reference LOL
// delete vp1;
// vp1=vp2;
// if (rv) { break;}
// }
// return rv;
//}
//vector<cube>* exploretodepth(cube &start, int depthlevelstart, int depthlevelend, cube &scrambled,vector<cube> &sol){
//// cout<<"dlstart:"<<depthlevelstart<<" dlend"<<depthlevelend<<endl;
// vector<cube>* vp1;
// int rv=0;
// if (depthlevelstart==1){//Can go 9 levels with 2 gigs of ram takes 14.79s
// vp1 = new vector<cube>;
// for (int i=0;i<9;i++) {vp1->push_back(cube(start,i,1));/*cout<<"pushback";*/}
// rv=expandvectormemorymanager(vp1,2,depthlevelend,scrambled,sol);
//// cout<<"rv="<<rv;
// }
// else{
// vp1 = new vector<cube>;
// vp1->push_back(start);
// rv=expandvectormemorymanager(vp1,depthlevelstart,depthlevelend,scrambled,sol);
//// cout<<"rv="<<rv;
// }
// return vp1;
//}
//void breadththendepthsearch(cube &start, cube &scrambled,vector<cube> &sol){
// //This function is used to cut the tree to a managable size.
// // It does of course create redundant cubes. (Maybe not anymore, since I changed leveljump to 9.)
// // Also this function assumes that no solutions were found leveljump deep.
//// cout<<"btdsearch"<<endl;
// const int leveljump=9;
// vector<cube>* d3 = exploretodepth(start,1,leveljump,scrambled,sol);
// if (!sol.empty()) {delete d3;return;}
// vector<cube>* tempcubevec;
//// cout<<"d3->size()"<<d3->size()<<endl;
// for (vector<cube>::iterator i=d3->begin();i<d3->end();i++){
// tempcubevec=exploretodepth(*i,leveljump+1,maxdepth,scrambled,sol);
// delete tempcubevec;
// if (!sol.empty()) break;
// }
// delete d3;
//}
//int solve(){
// cube eleven2("bypprpwbwrobbwyowoopyrry");
// vector<cube> sol;
// cube start;
// breadththendepthsearch(start,eleven2,sol);
// cout<<sol.size();
// if (!sol.empty()) sol[0].print();
//}
bool isuniqueset(cube &c, vector < set<cube> > &pyr, int highestindex){
for (int i=0;i<=highestindex;i++){
if (pyr[i].count(c)!=0) return 0;
}
return 1;
}
vector< set<cube> > buildpyramidset(int maxdepth){
// ofstream fileout;
// fileout.open("pyramidset6.txt");
cube start;
vector < set<cube> > pyr;
for (int i=0;i<=maxdepth;i++)
pyr.push_back(set<cube>());
int depth=0;
pyr[depth].insert(cube());
// start.write(0,fileout);
depth=1;
for (int i=0;i<9;i++){
pyr[depth].insert(cube(start,i,depth));
// cube(start,i,depth).write(1,fileout);
}
depth = 2;
for (;depth<=maxdepth;depth++){
// cout<<"starting level "<<depth<<" .";
// int counter=0;
for (set<cube>::iterator i=pyr[depth-1].begin(); i!=pyr[depth-1].end(); i++){
int skip = (*i).c[22+depth]-(*i).c[22+depth]%3;
int j=0;
for (;j<skip;j++){
cube b(*i,j,depth);
if (isuniqueset(b,pyr,depth)) {pyr[depth].insert(b);
// b.write(depth,fileout);
}
}
for (j+=3;j<9;j++){
cube b(*i,j,depth);
if (isuniqueset(b,pyr,depth)) {pyr[depth].insert(b);
// b.write(depth,fileout);
}
}
cout<<"\ndepth "<<depth<<" has "<<pyr[depth].size()<<" elements\n";
}
}
return pyr;
}
int main(){
vector<set <cube> > pyr = buildpyramidset(11);
int total=0;
for (int i=0;i<12;i++)
total+= pyr[i].size();
cout<<"Total number of cubes found = "<<total;
}