Skip to content

Instantly share code, notes, and snippets.

@sndyuk

sndyuk/README.md

Last active August 30, 2015 23:05
Show Gist options
  • Save sndyuk/e0d97e61486d745f40bd to your computer and use it in GitHub Desktop.
Save sndyuk/e0d97e61486d745f40bd to your computer and use it in GitHub Desktop.
Download ZIP
Rubik's Cube 3x3 Solver
Raw
README.md

Input order:

            000102
            030405
            060708
    091011 363738 272829 454647
    121314 394041 303132 484950
    151617 424344 333435 515253
            181920
            212223
            242526
Raw
input.txt
GRGGRGYOY
WWBWWBOGO
YYGOORYYG
WBBWBBRYR
RYRRYRWWB
OGOOGOWBB
result: DiFBMiCi
BBBWWWBBB
GYGOROGYG
WWWBBBWWW
YGYRORYGY
RRRGGGRRR
OOOYYYOOO
result: MMC
YYYBBRBBR
RGGBGGBGG
WWOWWOGGG
YYOYYWYYW
RRWRRWRRW
BBBOOOOOO
result: BiRi
RBORYYRBO
GGGOBBGGG
OWROGGOWR
YRYYWYYWY
WRBGRBWRB
WOBWOYWOB
result: LFiBU
BBOBBOBBO
GGGGGGGGG
WWRWWRWWR
YYYYYYYYY
RRBRRBRRB
WOOWOOWOO
result: R
WWWWWWWWW
RRROOOOOO
YYYYYYYYY
GGGBBBBBB
BBBRRRRRR
OOOGGGGGG
result:
Raw
main.cpp
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <utility>
using namespace std;
enum Color {
WHITE = 0, ORANGE = 1, YELLOW = 2, BLUE = 3, RED = 4, GREEN = 5
};
enum Command {
U = 0,
Ui = 1,
D = 2,
Di = 3,
L = 4,
Li = 5,
R = 6,
Ri = 7,
F = 8,
Fi = 9,
B = 10,
Bi = 11,
C = 12,
Ci = 13,
M = 14,
Mi = 15
};
inline int toString(Command *command, char* arr) {
int size;
switch (*command) {
case U:
arr[0] = 'U';
size = 1;
break;
case Ui:
arr[0] = 'U';
arr[1] = 'i';
size = 2;
break;
case D:
arr[0] = 'D';
size = 1;
break;
case Di:
arr[0] = 'D';
arr[1] = 'i';
size = 2;
break;
case L:
arr[0] = 'L';
size = 1;
break;
case Li:
arr[0] = 'L';
arr[1] = 'i';
size = 2;
break;
case R:
arr[0] = 'R';
size = 1;
break;
case Ri:
arr[0] = 'R';
arr[1] = 'i';
size = 2;
break;
case F:
arr[0] = 'F';
size = 1;
break;
case Fi:
arr[0] = 'F';
arr[1] = 'i';
size = 2;
break;
case B:
arr[0] = 'B';
size = 1;
break;
case Bi:
arr[0] = 'B';
arr[1] = 'i';
size = 2;
break;
case C:
arr[0] = 'C';
size = 1;
break;
case Ci:
arr[0] = 'C';
arr[1] = 'i';
size = 2;
break;
case M:
arr[0] = 'M';
size = 1;
break;
case Mi:
arr[0] = 'M';
arr[1] = 'i';
size = 2;
break;
}
return size;
}
class State {
public:
Color* cubes;
int* key;
Command* result;
int resultLen;
State() {
init();
}
State(const State& b) {
init();
copy(b);
}
~State() {
delete[] cubes;
delete[] key;
delete[] result;
}
State& operator=(const State& b) {
copy(b);
return *this;
}
private:
void copy(const State& b) {
memcpy(cubes, b.cubes, sizeof(Color) * 54);
memcpy(key, b.key, sizeof(int) * 6);
memcpy(result, b.result, sizeof(Command) * 20);
resultLen = b.resultLen;
}
void init() {
cubes = new Color[3 * 3 * 6]();
key = new int[6]();
result = new Command[20]();
resultLen = 0;
}
};
void makeKey(const State& s, int key[]) {
int _1 = 0;
for (int i = 0; i < 8; i++) {
_1 = _1 | (static_cast<int>(s.cubes[i]) << (i * 3));
}
key[0] = _1;
int _2 = 0;
for (int i = 8, p = 0; i < 17; i++, p++) {
_2 = _2 | (static_cast<int>(s.cubes[i]) << (p * 3));
}
key[1] = _2;
int _3 = 0;
for (int i = 17, p = 0; i < 26; i++, p++) {
_3 = _3 | (s.cubes[i] << (p * 3));
}
key[2] = _3;
int _4 = 0;
for (int i = 26, p = 0; i < 35; i++, p++) {
_4 = _4 | s.cubes[i] << (p * 3);
}
key[3] = _4;
int _5 = 0;
for (int i = 35, p = 0; i < 44; i++, p++) {
_5 = _5 | s.cubes[i] << (p * 3);
}
key[4] = _5;
int _6 = 0;
for (int i = 44, p = 0; i < 53; i++, p++) {
_6 = _6 | s.cubes[i] << (p * 3);
}
key[5] = _6;
}
struct cmp_key {
bool operator()(const int *a, const int *b) const {
return !(a[0] == b[0] && a[1] == b[1] && a[2] == b[2] && a[3] == b[3]
&& a[4] == b[4] && a[5] == a[5]);
}
};
bool check(Color* cubes, int start, int end) {
Color c = cubes[start];
for (int i = start + 1; i < end; i++) {
if (c != cubes[i]) {
return false;
}
}
return true;
}
bool checkAll(State* s) {
return check(s->cubes, 0, 8) && check(s->cubes, 9, 17)
&& check(s->cubes, 18, 26) && check(s->cubes, 27, 35)
&& check(s->cubes, 36, 44);
}
inline void copyState(State* newState, State* curr) {
*newState = *curr;
}
// 000102
// 030405
// 060708
// → 091011 363738 272829 454647
// 121314 394041 303132 484950
// 151617 424344 333435 515253
// 181920
// 212223
// 242526
inline void rotateUi(State* s) {
s->resultLen++;
s->result[s->resultLen - 1] = Ui;
Color _36 = s->cubes[36];
Color _37 = s->cubes[37];
Color _38 = s->cubes[38];
Color _27 = s->cubes[27];
Color _28 = s->cubes[28];
Color _29 = s->cubes[29];
Color _45 = s->cubes[45];
Color _46 = s->cubes[46];
Color _47 = s->cubes[47];
Color _09 = s->cubes[9];
Color _10 = s->cubes[10];
Color _11 = s->cubes[11];
// 36 -> 27
// 37 -> 28
// 38 -> 29
s->cubes[27] = _36;
s->cubes[28] = _37;
s->cubes[29] = _38;
// 27 -> 45
// 28 -> 46
// 29 -> 47
s->cubes[45] = _27;
s->cubes[46] = _28;
s->cubes[47] = _29;
// 45 -> 9
// 46 -> 10
// 47 -> 11
s->cubes[9] = _45;
s->cubes[10] = _46;
s->cubes[11] = _47;
// 9 -> 36
// 10 -> 37
// 11 -> 38
s->cubes[36] = _09;
s->cubes[37] = _10;
s->cubes[38] = _11;
Color _00 = s->cubes[0];
Color _01 = s->cubes[1];
Color _02 = s->cubes[2];
Color _03 = s->cubes[3];
Color _05 = s->cubes[5];
Color _06 = s->cubes[6];
Color _07 = s->cubes[7];
Color _08 = s->cubes[8];
s->cubes[6] = _00;
s->cubes[3] = _01;
s->cubes[0] = _02;
s->cubes[7] = _03;
s->cubes[1] = _05;
s->cubes[8] = _06;
s->cubes[5] = _07;
s->cubes[2] = _08;
}
// 000102
// 030405
// 060708
// ← 091011 363738 272829 454647
// 121314 394041 303132 484950
// 151617 424344 333435 515253
// 181920
// 212223
// 242526
void rotateU(State* s) {
s->resultLen++;
s->result[s->resultLen - 1] = U;
Color _36 = s->cubes[36];
Color _37 = s->cubes[37];
Color _38 = s->cubes[38];
Color _27 = s->cubes[27];
Color _28 = s->cubes[28];
Color _29 = s->cubes[29];
Color _45 = s->cubes[45];
Color _46 = s->cubes[46];
Color _47 = s->cubes[47];
Color _09 = s->cubes[9];
Color _10 = s->cubes[10];
Color _11 = s->cubes[11];
// 36 <- 27
// 37 <- 28
// 38 <- 29
s->cubes[36] = _27;
s->cubes[37] = _28;
s->cubes[38] = _29;
// 27 <- 45
// 28 <- 46
// 29 <- 47
s->cubes[27] = _45;
s->cubes[28] = _46;
s->cubes[29] = _47;
// 45 <- 9
// 46 <- 10
// 47 <- 11
s->cubes[45] = _09;
s->cubes[46] = _10;
s->cubes[47] = _11;
// 9 <- 36
// 10 <- 37
// 11 <- 38
s->cubes[9] = _36;
s->cubes[10] = _37;
s->cubes[11] = _38;
Color _00 = s->cubes[0];
Color _01 = s->cubes[1];
Color _02 = s->cubes[2];
Color _03 = s->cubes[3];
Color _05 = s->cubes[5];
Color _06 = s->cubes[6];
Color _07 = s->cubes[7];
Color _08 = s->cubes[8];
s->cubes[0] = _06;
s->cubes[1] = _03;
s->cubes[2] = _00;
s->cubes[3] = _07;
s->cubes[5] = _01;
s->cubes[6] = _08;
s->cubes[7] = _05;
s->cubes[8] = _02;
}
// 000102
// 030405
// 060708
// 091011 363738 272829 454647
// 121314 394041 303132 484950
// → 151617 424344 333435 515253
// 181920
// 212223
// 242526
inline void rotateD(State* s) {
s->resultLen++;
s->result[s->resultLen - 1] = D;
Color _42 = s->cubes[42];
Color _43 = s->cubes[43];
Color _44 = s->cubes[44];
Color _33 = s->cubes[33];
Color _34 = s->cubes[34];
Color _35 = s->cubes[35];
Color _51 = s->cubes[51];
Color _52 = s->cubes[52];
Color _53 = s->cubes[53];
Color _15 = s->cubes[15];
Color _16 = s->cubes[16];
Color _17 = s->cubes[17];
// 42 -> 33
// 43 -> 34
// 44 -> 35
s->cubes[33] = _42;
s->cubes[34] = _43;
s->cubes[35] = _44;
// 33 -> 51
// 34 -> 52
// 35 -> 53
s->cubes[51] = _33;
s->cubes[52] = _34;
s->cubes[53] = _35;
// 51 -> 15
// 52 -> 16
// 53 -> 17
s->cubes[15] = _51;
s->cubes[16] = _52;
s->cubes[17] = _53;
// 15 -> 42
// 16 -> 43
// 17 -> 44
s->cubes[42] = _15;
s->cubes[43] = _16;
s->cubes[44] = _17;
Color _18 = s->cubes[18];
Color _19 = s->cubes[19];
Color _20 = s->cubes[20];
Color _21 = s->cubes[21];
Color _23 = s->cubes[23];
Color _24 = s->cubes[24];
Color _25 = s->cubes[25];
Color _26 = s->cubes[26];
s->cubes[18] = _24;
s->cubes[19] = _21;
s->cubes[20] = _18;
s->cubes[21] = _25;
s->cubes[23] = _19;
s->cubes[24] = _26;
s->cubes[25] = _23;
s->cubes[26] = _20;
}
// 000102
// 030405
// 060708
// 091011 363738 272829 454647
// 121314 394041 303132 484950
// ← 151617 424344 333435 515253
// 181920
// 　 212223
// 242526
inline void rotateDi(State* s) {
s->resultLen++;
s->result[s->resultLen - 1] = Di;
Color _42 = s->cubes[42];
Color _43 = s->cubes[43];
Color _44 = s->cubes[44];
Color _33 = s->cubes[33];
Color _34 = s->cubes[34];
Color _35 = s->cubes[35];
Color _51 = s->cubes[51];
Color _52 = s->cubes[52];
Color _53 = s->cubes[53];
Color _15 = s->cubes[15];
Color _16 = s->cubes[16];
Color _17 = s->cubes[17];
// 42 <- 33
// 43 <- 34
// 44 <- 35
s->cubes[42] = _33;
s->cubes[43] = _34;
s->cubes[44] = _35;
// 33 <- 51
// 34 <- 52
// 35 <- 53
s->cubes[33] = _51;
s->cubes[34] = _52;
s->cubes[35] = _53;
// 51 <- 15
// 52 <- 16
// 53 <- 17
s->cubes[51] = _15;
s->cubes[52] = _16;
s->cubes[53] = _17;
// 15 <- 42
// 16 <- 43
// 17 <- 44
s->cubes[15] = _42;
s->cubes[16] = _43;
s->cubes[17] = _44;
Color _18 = s->cubes[18];
Color _19 = s->cubes[19];
Color _20 = s->cubes[20];
Color _21 = s->cubes[21];
Color _23 = s->cubes[23];
Color _24 = s->cubes[24];
Color _25 = s->cubes[25];
Color _26 = s->cubes[26];
s->cubes[24] = _18;
s->cubes[21] = _19;
s->cubes[18] = _20;
s->cubes[25] = _21;
s->cubes[19] = _23;
s->cubes[26] = _24;
s->cubes[23] = _25;
s->cubes[20] = _26;
}
// ↓↓
// 000102
// 030405
// 060708
// 091011 363738 272829 454647
// 121314 394041 303132 484950
// 151617 424344 333435 515253
// 181920
// 212223
// 242526
inline void rotateL(State* s) {
s->resultLen++;
s->result[s->resultLen - 1] = L;
Color _00 = s->cubes[0];
Color _03 = s->cubes[3];
Color _06 = s->cubes[6];
Color _36 = s->cubes[36];
Color _39 = s->cubes[39];
Color _42 = s->cubes[42];
Color _18 = s->cubes[18];
Color _21 = s->cubes[21];
Color _24 = s->cubes[24];
Color _47 = s->cubes[47];
Color _50 = s->cubes[50];
Color _53 = s->cubes[53];
// 00 -> 36
// 03 -> 39
// 06 -> 42
s->cubes[36] = _00;
s->cubes[39] = _03;
s->cubes[42] = _06;
// 36 -> 18
// 39 -> 21
// 42 -> 24
s->cubes[18] = _36;
s->cubes[21] = _39;
s->cubes[24] = _42;
// 18 -> 53
// 21 -> 50
// 24 -> 47
s->cubes[53] = _18;
s->cubes[50] = _21;
s->cubes[47] = _24;
// 53 -> 00
// 50 -> 03
// 47 -> 06
s->cubes[0] = _53;
s->cubes[3] = _50;
s->cubes[6] = _47;
// 091011
// 121314
// 151617
Color _09 = s->cubes[9];
Color _10 = s->cubes[10];
Color _11 = s->cubes[11];
Color _12 = s->cubes[12];
Color _14 = s->cubes[14];
Color _15 = s->cubes[15];
Color _16 = s->cubes[16];
Color _17 = s->cubes[17];
s->cubes[9] = _15;
s->cubes[10] = _12;
s->cubes[11] = _09;
s->cubes[12] = _16;
s->cubes[14] = _10;
s->cubes[15] = _17;
s->cubes[16] = _14;
s->cubes[17] = _11;
}
// ↑↑
// 000102
// 030405
// 060708
// 091011 363738 272829 454647
// 121314 394041 303132 484950
// 151617 424344 333435 515253
// 181920
// 212223
// 242526
inline void rotateLi(State* s) {
s->resultLen++;
s->result[s->resultLen - 1] = Li;
Color _00 = s->cubes[0];
Color _03 = s->cubes[3];
Color _06 = s->cubes[6];
Color _36 = s->cubes[36];
Color _39 = s->cubes[39];
Color _42 = s->cubes[42];
Color _18 = s->cubes[18];
Color _21 = s->cubes[21];
Color _24 = s->cubes[24];
Color _47 = s->cubes[47];
Color _50 = s->cubes[50];
Color _53 = s->cubes[53];
// 00 <- 36
// 03 <- 39
// 06 <- 42
s->cubes[0] = _36;
s->cubes[3] = _39;
s->cubes[6] = _42;
// 36 <- 18
// 39 <- 21
// 42 <- 24
s->cubes[36] = _18;
s->cubes[39] = _21;
s->cubes[42] = _24;
// 18 <- 53
// 21 <- 50
// 24 <- 47
s->cubes[18] = _53;
s->cubes[16] = _50;
s->cubes[17] = _47;
// 53 <- 00
// 50 <- 03
// 47 <- 06
s->cubes[53] = _00;
s->cubes[50] = _03;
s->cubes[47] = _06;
Color _09 = s->cubes[9];
Color _10 = s->cubes[10];
Color _11 = s->cubes[11];
Color _12 = s->cubes[12];
Color _14 = s->cubes[14];
Color _15 = s->cubes[15];
Color _16 = s->cubes[16];
Color _17 = s->cubes[17];
s->cubes[15] = _09;
s->cubes[12] = _10;
s->cubes[15] = _11;
s->cubes[16] = _12;
s->cubes[10] = _14;
s->cubes[17] = _15;
s->cubes[14] = _16;
s->cubes[11] = _17;
}
// ↑↑
// 000102
// 030405
// 060708
// 091011 363738 272829 454647
// 121314 394041 303132 484950
// 151617 424344 333435 515253
// 181920
// 212223
// 242526
void rotateR(State* s) {
s->resultLen++;
s->result[s->resultLen - 1] = R;
Color _02 = s->cubes[2];
Color _05 = s->cubes[5];
Color _08 = s->cubes[8];
Color _38 = s->cubes[38];
Color _41 = s->cubes[41];
Color _44 = s->cubes[44];
Color _20 = s->cubes[20];
Color _23 = s->cubes[23];
Color _26 = s->cubes[26];
Color _45 = s->cubes[45];
Color _48 = s->cubes[48];
Color _51 = s->cubes[51];
// 02 <- 38
// 05 <- 41
// 08 <- 44
s->cubes[2] = _38;
s->cubes[5] = _41;
s->cubes[8] = _44;
// 38 <- 20
// 41 <- 23
// 44 <- 26
s->cubes[38] = _20;
s->cubes[41] = _23;
s->cubes[44] = _26;
// 20 <- 45
// 23 <- 48
// 26 <- 51
s->cubes[20] = _45;
s->cubes[23] = _48;
s->cubes[26] = _51;
// 51 <- 02
// 48 <- 05
// 45 <- 08
s->cubes[51] = _02;
s->cubes[48] = _05;
s->cubes[45] = _08;
Color _27 = s->cubes[27];
Color _28 = s->cubes[28];
Color _29 = s->cubes[29];
Color _30 = s->cubes[30];
Color _32 = s->cubes[32];
Color _33 = s->cubes[33];
Color _34 = s->cubes[34];
Color _35 = s->cubes[35];
s->cubes[27] = _33;
s->cubes[28] = _30;
s->cubes[29] = _27;
s->cubes[30] = _34;
s->cubes[32] = _28;
s->cubes[33] = _35;
s->cubes[34] = _32;
s->cubes[35] = _29;
}
// ↓↓
// 000102
// 030405
// 060708
// 091011 363738 272829 454647
// 121314 394041 303132 484950
// 151617 424344 333435 515253
// 181920
// 212223
// 242526
inline void rotateRi(State* s) {
s->resultLen++;
s->result[s->resultLen - 1] = Ri;
Color _02 = s->cubes[2];
Color _05 = s->cubes[5];
Color _08 = s->cubes[8];
Color _38 = s->cubes[38];
Color _41 = s->cubes[41];
Color _44 = s->cubes[44];
Color _20 = s->cubes[20];
Color _23 = s->cubes[23];
Color _26 = s->cubes[26];
Color _45 = s->cubes[45];
Color _48 = s->cubes[48];
Color _51 = s->cubes[51];
// 02 -> 38
// 05 -> 41
// 08 -> 44
s->cubes[38] = _02;
s->cubes[41] = _05;
s->cubes[44] = _08;
// 38 -> 20
// 41 -> 23
// 44 -> 26
s->cubes[20] = _38;
s->cubes[23] = _41;
s->cubes[26] = _44;
// 20 -> 51
// 23 -> 48
// 26 -> 45
s->cubes[51] = _26;
s->cubes[48] = _23;
s->cubes[45] = _20;
// 51 -> 02
// 48 -> 05
// 45 -> 08
s->cubes[2] = _51;
s->cubes[5] = _48;
s->cubes[8] = _45;
Color _27 = s->cubes[27];
Color _28 = s->cubes[28];
Color _29 = s->cubes[29];
Color _30 = s->cubes[30];
Color _32 = s->cubes[32];
Color _33 = s->cubes[33];
Color _34 = s->cubes[34];
Color _35 = s->cubes[35];
s->cubes[33] = _27;
s->cubes[30] = _28;
s->cubes[27] = _29;
s->cubes[34] = _30;
s->cubes[28] = _32;
s->cubes[35] = _33;
s->cubes[32] = _34;
s->cubes[29] = _35;
}
// 000102
// 030405
// → 060708 ↓
// 091011 363738 272829 454647
// 121314 394041 303132 484950
// 151617 424344 333435 515253
// ↑ 181920 ←
// 212223
// 242526
inline void rotateF(State* s) {
s->resultLen++;
s->result[s->resultLen - 1] = F;
Color _06 = s->cubes[6];
Color _07 = s->cubes[7];
Color _08 = s->cubes[8];
Color _27 = s->cubes[27];
Color _30 = s->cubes[30];
Color _33 = s->cubes[33];
Color _18 = s->cubes[18];
Color _19 = s->cubes[19];
Color _20 = s->cubes[20];
Color _11 = s->cubes[11];
Color _14 = s->cubes[14];
Color _17 = s->cubes[17];
s->cubes[6] = _17;
s->cubes[7] = _14;
s->cubes[8] = _11;
s->cubes[27] = _06;
s->cubes[30] = _07;
s->cubes[33] = _08;
s->cubes[20] = _27;
s->cubes[19] = _30;
s->cubes[18] = _33;
s->cubes[17] = _20;
s->cubes[14] = _19;
s->cubes[11] = _18;
Color _36 = s->cubes[36];
Color _37 = s->cubes[37];
Color _38 = s->cubes[38];
Color _39 = s->cubes[39];
Color _41 = s->cubes[41];
Color _42 = s->cubes[42];
Color _43 = s->cubes[43];
Color _44 = s->cubes[44];
s->cubes[36] = _42;
s->cubes[37] = _39;
s->cubes[38] = _36;
s->cubes[39] = _43;
s->cubes[41] = _37;
s->cubes[42] = _44;
s->cubes[43] = _41;
s->cubes[44] = _38;
}
// 000102
// 030405
// ↓ 060708 ←
// 091011 363738 272829 454647
// 121314 394041 303132 484950
// 151617 424344 333435 515253
// → 181920 ↑
// 212223
// 242526
inline void rotateFi(State* s) {
s->resultLen++;
s->result[s->resultLen - 1] = Fi;
Color _06 = s->cubes[6];
Color _07 = s->cubes[7];
Color _08 = s->cubes[8];
Color _27 = s->cubes[27];
Color _30 = s->cubes[30];
Color _33 = s->cubes[33];
Color _18 = s->cubes[18];
Color _19 = s->cubes[19];
Color _20 = s->cubes[20];
Color _11 = s->cubes[11];
Color _14 = s->cubes[14];
Color _17 = s->cubes[17];
s->cubes[17] = _06;
s->cubes[14] = _07;
s->cubes[11] = _08;
s->cubes[6] = _27;
s->cubes[7] = _30;
s->cubes[8] = _33;
s->cubes[27] = _20;
s->cubes[30] = _19;
s->cubes[33] = _18;
s->cubes[20] = _17;
s->cubes[19] = _14;
s->cubes[18] = _11;
Color _36 = s->cubes[36];
Color _37 = s->cubes[37];
Color _38 = s->cubes[38];
Color _39 = s->cubes[39];
Color _41 = s->cubes[41];
Color _42 = s->cubes[42];
Color _43 = s->cubes[43];
Color _44 = s->cubes[44];
s->cubes[42] = _36;
s->cubes[39] = _37;
s->cubes[36] = _38;
s->cubes[43] = _39;
s->cubes[37] = _41;
s->cubes[44] = _42;
s->cubes[41] = _43;
s->cubes[38] = _44;
}
// 000102 ←
// 030405
// ↓ 060708
// 091011 363738 272829 454647
// 121314 394041 303132 484950
// 151617 424344 333435 515253
// 181920 ↑
// 212223
// → 242526
inline void rotateB(State* s) {
s->resultLen++;
s->result[s->resultLen - 1] = B;
Color _00 = s->cubes[0];
Color _01 = s->cubes[1];
Color _02 = s->cubes[2];
Color _09 = s->cubes[9];
Color _12 = s->cubes[12];
Color _15 = s->cubes[15];
Color _24 = s->cubes[24];
Color _25 = s->cubes[25];
Color _26 = s->cubes[26];
Color _35 = s->cubes[35];
Color _32 = s->cubes[32];
Color _29 = s->cubes[29];
s->cubes[0] = _29;
s->cubes[1] = _32;
s->cubes[2] = _35;
s->cubes[9] = _02;
s->cubes[12] = _01;
s->cubes[15] = _00;
s->cubes[24] = _09;
s->cubes[25] = _12;
s->cubes[26] = _15;
s->cubes[35] = _24;
s->cubes[32] = _25;
s->cubes[29] = _26;
Color _45 = s->cubes[45];
Color _46 = s->cubes[46];
Color _47 = s->cubes[47];
Color _48 = s->cubes[48];
Color _50 = s->cubes[50];
Color _51 = s->cubes[51];
Color _52 = s->cubes[52];
Color _53 = s->cubes[53];
s->cubes[45] = _51;
s->cubes[46] = _48;
s->cubes[47] = _45;
s->cubes[48] = _52;
s->cubes[50] = _46;
s->cubes[51] = _53;
s->cubes[52] = _50;
s->cubes[53] = _47;
}
// → 000102
// 030405
// 060708 ↓
// 091011 363738 272829 454647
// 121314 394041 303132 484950
// 151617 424344 333435 515253
// ↑ 181920
// 212223
// 242526 ←
inline void rotateBi(State* s) {
s->resultLen++;
s->result[s->resultLen - 1] = Bi;
Color _00 = s->cubes[0];
Color _01 = s->cubes[1];
Color _02 = s->cubes[2];
Color _09 = s->cubes[9];
Color _12 = s->cubes[12];
Color _15 = s->cubes[15];
Color _24 = s->cubes[24];
Color _25 = s->cubes[25];
Color _26 = s->cubes[26];
Color _35 = s->cubes[35];
Color _32 = s->cubes[32];
Color _29 = s->cubes[29];
s->cubes[29] = _00;
s->cubes[32] = _01;
s->cubes[35] = _02;
s->cubes[2] = _09;
s->cubes[1] = _12;
s->cubes[0] = _15;
s->cubes[9] = _24;
s->cubes[12] = _25;
s->cubes[15] = _26;
s->cubes[24] = _35;
s->cubes[25] = _32;
s->cubes[26] = _29;
Color _45 = s->cubes[45];
Color _46 = s->cubes[46];
Color _47 = s->cubes[47];
Color _48 = s->cubes[48];
Color _50 = s->cubes[50];
Color _51 = s->cubes[51];
Color _52 = s->cubes[52];
Color _53 = s->cubes[53];
s->cubes[51] = _45;
s->cubes[48] = _46;
s->cubes[45] = _47;
s->cubes[52] = _48;
s->cubes[46] = _50;
s->cubes[53] = _51;
s->cubes[50] = _52;
s->cubes[47] = _53;
}
// 000102
// 030405
// 060708
// 091011 363738 272829 454647
// 121314 394041 303132 484950 ←
// 151617 424344 333435 515253
// 181920
// 212223
// 242526
inline void rotateC(State* s) {
s->resultLen++;
s->result[s->resultLen - 1] = C;
Color _12 = s->cubes[12];
Color _13 = s->cubes[13];
Color _14 = s->cubes[14];
Color _39 = s->cubes[39];
Color _40 = s->cubes[40];
Color _41 = s->cubes[41];
Color _30 = s->cubes[30];
Color _31 = s->cubes[31];
Color _32 = s->cubes[32];
Color _48 = s->cubes[48];
Color _49 = s->cubes[49];
Color _50 = s->cubes[50];
s->cubes[12] = _39;
s->cubes[13] = _40;
s->cubes[14] = _41;
s->cubes[39] = _30;
s->cubes[40] = _31;
s->cubes[41] = _32;
s->cubes[30] = _48;
s->cubes[31] = _49;
s->cubes[32] = _50;
s->cubes[48] = _12;
s->cubes[49] = _13;
s->cubes[50] = _14;
}
// 000102
// 030405
// 060708
// 091011 363738 272829 454647
// →121314 394041 303132 484950
// 151617 424344 333435 515253
// 181920
// 212223
// 242526
inline void rotateCi(State* s) {
s->resultLen++;
s->result[s->resultLen - 1] = Ci;
Color _12 = s->cubes[12];
Color _13 = s->cubes[13];
Color _14 = s->cubes[14];
Color _39 = s->cubes[39];
Color _40 = s->cubes[40];
Color _41 = s->cubes[41];
Color _30 = s->cubes[30];
Color _31 = s->cubes[31];
Color _32 = s->cubes[32];
Color _48 = s->cubes[48];
Color _49 = s->cubes[49];
Color _50 = s->cubes[50];
s->cubes[39] = _12;
s->cubes[40] = _13;
s->cubes[41] = _14;
s->cubes[30] = _39;
s->cubes[31] = _40;
s->cubes[32] = _41;
s->cubes[48] = _30;
s->cubes[49] = _31;
s->cubes[50] = _32;
s->cubes[12] = _48;
s->cubes[13] = _49;
s->cubes[14] = _50;
}
// 000102
// → 030405
// 060708 ↓
// 091011 363738 272829 454647
// 121314 394041 303132 484950
// 151617 424344 333435 515253
// ↑ 181920
// 212223 ←
// 242526
inline void rotateM(State* s) {
s->resultLen++;
s->result[s->resultLen - 1] = M;
Color _03 = s->cubes[3];
Color _04 = s->cubes[4];
Color _05 = s->cubes[5];
Color _28 = s->cubes[28];
Color _31 = s->cubes[31];
Color _34 = s->cubes[34];
Color _21 = s->cubes[21];
Color _22 = s->cubes[22];
Color _23 = s->cubes[23];
Color _10 = s->cubes[10];
Color _13 = s->cubes[13];
Color _16 = s->cubes[16];
s->cubes[3] = _16;
s->cubes[4] = _13;
s->cubes[5] = _10;
s->cubes[10] = _21;
s->cubes[13] = _22;
s->cubes[16] = _23;
s->cubes[21] = _34;
s->cubes[22] = _31;
s->cubes[23] = _28;
s->cubes[28] = _03;
s->cubes[31] = _04;
s->cubes[34] = _05;
}
// 000102
// 030405 ←
// ↓ 060708
// 091011 363738 272829 454647
// 121314 394041 303132 484950
// 151617 424344 333435 515253
// 181920 ↑
// → 212223
// 242526
inline void rotateMi(State* s) {
s->resultLen++;
s->result[s->resultLen - 1] = Mi;
Color _03 = s->cubes[3];
Color _04 = s->cubes[4];
Color _05 = s->cubes[5];
Color _28 = s->cubes[28];
Color _31 = s->cubes[31];
Color _34 = s->cubes[34];
Color _21 = s->cubes[21];
Color _22 = s->cubes[22];
Color _23 = s->cubes[23];
Color _10 = s->cubes[10];
Color _13 = s->cubes[13];
Color _16 = s->cubes[16];
s->cubes[16] = _03;
s->cubes[13] = _04;
s->cubes[10] = _05;
s->cubes[21] = _10;
s->cubes[22] = _13;
s->cubes[23] = _16;
s->cubes[34] = _21;
s->cubes[31] = _22;
s->cubes[28] = _23;
s->cubes[3] = _28;
s->cubes[4] = _31;
s->cubes[5] = _34;
}
void pushQueue(State& s, queue<State*>& q, map<int*, State*, cmp_key>& m) {
makeKey(s, s.key);
map<int*, State*>::const_iterator it = m.find(s.key);
if (it == m.end()) {
q.push(&s);
m.insert(make_pair(s.key, &s));
} else {
delete &s;
}
}
State* dfs(State& curr, queue<State*>& q, map<int*, State*, cmp_key>& m) {
// U
{
State* s = new State(curr);
rotateU(s);
pushQueue(*s, q, m);
if (checkAll(s)) {
return s;
}
}
// Ui
{
State* s = new State(curr);
rotateUi(s);
pushQueue(*s, q, m);
if (checkAll(s)) {
return s;
}
}
// D
{
State* s = new State(curr);
rotateD(s);
pushQueue(*s, q, m);
if (checkAll(s)) {
return s;
}
}
// Di
{
State* s = new State(curr);
rotateDi(s);
pushQueue(*s, q, m);
if (checkAll(s)) {
return s;
}
}
// R
{
State* s = new State(curr);
rotateR(s);
pushQueue(*s, q, m);
if (checkAll(s)) {
return s;
}
}
// Ri
{
State* s = new State(curr);
rotateRi(s);
pushQueue(*s, q, m);
if (checkAll(s)) {
return s;
}
}
// L
{
State* s = new State(curr);
rotateL(s);
pushQueue(*s, q, m);
if (checkAll(s)) {
return s;
}
}
// Li
{
State* s = new State(curr);
rotateLi(s);
pushQueue(*s, q, m);
if (checkAll(s)) {
return s;
}
}
// F
{
State* s = new State(curr);
rotateF(s);
pushQueue(*s, q, m);
if (checkAll(s)) {
return s;
}
}
// Fi
{
State* s = new State(curr);
rotateFi(s);
pushQueue(*s, q, m);
if (checkAll(s)) {
return s;
}
}
// B
{
State* s = new State(curr);
rotateB(s);
pushQueue(*s, q, m);
if (checkAll(s)) {
return s;
}
}
// Bi
{
State* s = new State(curr);
rotateBi(s);
pushQueue(*s, q, m);
if (checkAll(s)) {
return s;
}
}
// C
{
State* s = new State(curr);
rotateC(s);
pushQueue(*s, q, m);
if (checkAll(s)) {
return s;
}
}
// Ci
{
State* s = new State(curr);
rotateCi(s);
pushQueue(*s, q, m);
if (checkAll(s)) {
return s;
}
}
// M
{
State* s = new State(curr);
rotateM(s);
pushQueue(*s, q, m);
if (checkAll(s)) {
return s;
}
}
// Mi
{
State* s = new State(curr);
rotateMi(s);
pushQueue(*s, q, m);
if (checkAll(s)) {
return s;
}
}
return NULL;
}
State* biDfs(State* curr, State* goal) {
if (checkAll(curr)) {
return curr;
}
queue<State*> q1;
q1.push(curr);
queue<State*> q2;
q2.push(goal);
map<int*, State*, cmp_key> m1;
map<int*, State*, cmp_key> m2;
int loop = 0;
while (!q1.empty()) {
State* s1 = q1.front();
q1.pop();
loop++;
if (loop % 100000 == 0) {
cout << loop << ":" << s1->resultLen << ":" << q1.size() << endl;
}
if (s1->resultLen > 6) {
cout << "Reach limit" << endl;
return NULL;
}
State* ret = dfs(*s1, q1, m1);
if (ret != NULL) {
return ret;
}
State* s2 = q2.front();
q2.pop();
dfs(*s2, q2, m2);
map<int*, State*>::const_iterator it = m2.find(s1->key);
if (it != m2.end()) {
cout << "found" << endl;
return it->second;
}
delete s1;
s1 = NULL;
}
return NULL;
}
void makeGoal(State* s, State* curr) {
for (int i = 0; i < 8; i++) {
s->cubes[i] = curr->cubes[4];
}
for (int i = 8; i < 17; i++) {
s->cubes[i] = curr->cubes[13];
}
for (int i = 17; i < 26; i++) {
s->cubes[i] = curr->cubes[22];
}
for (int i = 26; i < 35; i++) {
s->cubes[i] = curr->cubes[31];
}
for (int i = 35; i < 44; i++) {
s->cubes[i] = curr->cubes[40];
}
for (int i = 44; i < 53; i++) {
s->cubes[i] = curr->cubes[49];
}
}
int main() {
State* s = new State();
Color* cubes = s->cubes;
char c;
for (int i = 0; i < 54; i++) {
cin >> c;
cout << c << endl;
switch (c) {
case 'W':
cubes[i] = WHITE;
break;
case 'O':
cubes[i] = ORANGE;
break;
case 'Y':
cubes[i] = YELLOW;
break;
case 'B':
cubes[i] = BLUE;
break;
case 'R':
cubes[i] = RED;
break;
case 'G':
cubes[i] = GREEN;
break;
}
}
State* goal = new State();
makeGoal(goal, s);
State* ret = biDfs(s, goal);
if (ret != NULL) {
cout << "result: ";
for (int i = 0; i < ret->resultLen; i++) {
char str[2];
int size = toString(&ret->result[i], str);
if (size == 1) {
cout << str[0];
} else {
cout << str[0] << str[1];
}
}
cout << endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment