#include #include #define MAX_CHECK_PERM_N 24 #define CORNER_UFR 0 #define CORNER_URB 1 #define CORNER_UBL 2 #define CORNER_ULF 3 #define CORNER_DRF 4 #define CORNER_DFL 5 #define CORNER_DLB 6 #define CORNER_DBR 7 #define CORNER_FRU 8 #define CORNER_RBU 9 #define CORNER_BLU 10 #define CORNER_LFU 11 #define CORNER_RFD 12 #define CORNER_FLD 13 #define CORNER_LBD 14 #define CORNER_BRD 15 #define CORNER_RUF 16 #define CORNER_BUR 17 #define CORNER_LUB 18 #define CORNER_FUL 19 #define CORNER_FDR 20 #define CORNER_LDF 21 #define CORNER_BDL 22 #define CORNER_RDB 23 #define EDGE_UF 0 #define EDGE_UR 1 #define EDGE_UB 2 #define EDGE_UL 3 #define EDGE_DF 4 #define EDGE_DR 5 #define EDGE_DB 6 #define EDGE_DL 7 #define EDGE_FR 8 #define EDGE_FL 9 #define EDGE_BR 10 #define EDGE_BL 11 #define EDGE_FU 12 #define EDGE_RU 13 #define EDGE_BU 14 #define EDGE_LU 15 #define EDGE_FD 16 #define EDGE_RD 17 #define EDGE_BD 18 #define EDGE_LD 19 #define EDGE_RF 20 #define EDGE_LF 21 #define EDGE_RB 22 #define EDGE_LB 23 #define FACE_F 0 #define FACE_R 1 #define FACE_U 2 #define FACE_B 3 #define FACE_L 4 #define FACE_D 5 typedef struct cube { int centers[6]; int edges[24]; int corners[24]; } Cube; static char *center_cubie_str[] = {"F", "R", "U", "B", "L", "D"}; static char *edge_cubie_str[] = {"UF", "UR", "UB", "UL", "DF", "DR", "DB", "DL", "FR", "FL", "BR", "BL", "FU", "RU", "BU", "LU", "FD", "RD", "BD", "LD", "RF", "LF", "RB", "LB"}; static int edge_cubie_color[] = { FACE_U, FACE_U, FACE_U, FACE_U, FACE_D, FACE_D, FACE_D, FACE_D, FACE_F, FACE_F, FACE_B, FACE_B, FACE_F, FACE_R, FACE_B, FACE_L, FACE_F, FACE_R, FACE_B, FACE_L, FACE_R, FACE_L, FACE_R, FACE_L }; static char *corner_cubie_str[] = {"UFR", "URB", "UBL", "ULF", "DRF", "DFL", "DLB", "DBR", "FRU", "RBU", "BLU", "LFU", "RFD", "FLD", "LBD", "BRD", "RUF", "BUR", "LUB", "FUL", "FDR", "LDF", "BDL", "RDB"}; static int corner_cubie_color[] = { FACE_U, FACE_U, FACE_U, FACE_U, FACE_D, FACE_D, FACE_D, FACE_D, FACE_F, FACE_R, FACE_B, FACE_L, FACE_R, FACE_F, FACE_L, FACE_B, FACE_R, FACE_B, FACE_L, FACE_F, FACE_F, FACE_L, FACE_B, FACE_R}; /* ========================================================================= */ void two_cycle(int array[], int ind0, int ind1) /* ------------------------------------------------------------------------- */ { int temp; temp = array[ind0]; array[ind0] = array[ind1]; array[ind1] = temp; return; } /* ========================================================================= */ void three_cycle(int array[], int ind0, int ind1, int ind2) /* ------------------------------------------------------------------------- */ { int temp; temp = array[ind0]; array[ind0] = array[ind1]; array[ind1] = array[ind2]; array[ind2] = temp; return; } /* ========================================================================= */ void four_cycle(int array[], int ind0, int ind1, int ind2, int ind3) /* ------------------------------------------------------------------------- */ { int temp; temp = array[ind0]; array[ind0] = array[ind1]; array[ind1] = array[ind2]; array[ind2] = array[ind3]; array[ind3] = temp; return; } /* ========================================================================= */ void print_cube(Cube *p_cube) /* ------------------------------------------------------------------------- */ { printf("%s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s\n", center_cubie_str[p_cube->centers[0]], center_cubie_str[p_cube->centers[1]], center_cubie_str[p_cube->centers[2]], center_cubie_str[p_cube->centers[3]], center_cubie_str[p_cube->centers[4]], center_cubie_str[p_cube->centers[5]], edge_cubie_str[p_cube->edges[0]], edge_cubie_str[p_cube->edges[1]], edge_cubie_str[p_cube->edges[2]], edge_cubie_str[p_cube->edges[3]], edge_cubie_str[p_cube->edges[4]], edge_cubie_str[p_cube->edges[5]], edge_cubie_str[p_cube->edges[6]], edge_cubie_str[p_cube->edges[7]], edge_cubie_str[p_cube->edges[8]], edge_cubie_str[p_cube->edges[9]], edge_cubie_str[p_cube->edges[10]], edge_cubie_str[p_cube->edges[11]], corner_cubie_str[p_cube->corners[0]], corner_cubie_str[p_cube->corners[1]], corner_cubie_str[p_cube->corners[2]], corner_cubie_str[p_cube->corners[3]], corner_cubie_str[p_cube->corners[4]], corner_cubie_str[p_cube->corners[5]], corner_cubie_str[p_cube->corners[6]], corner_cubie_str[p_cube->corners[7]]); return; } /* ========================================================================= */ void perm_n_init(int nn, int array_out[]) /* ------------------------------------------------------------------------- */ { int ii; for (ii = 0; ii < nn; ii++) array_out[ii] = ii; return; } /* ========================================================================= */ void cube_init(Cube *p_cube) /* ------------------------------------------------------------------------- */ { perm_n_init(6, p_cube->centers); perm_n_init(24, p_cube->edges); perm_n_init(24, p_cube->corners); return; } /* ========================================================================= */ int perm_n_check(int nn, int array_in[]) /* ------------------------------------------------------------------------- */ { int count[MAX_CHECK_PERM_N], ii; for (ii = 0; ii < nn; ii++) count[ii] = 0; for (ii = 0; ii < nn; ii++) { if ((array_in[ii] < 0) || (array_in[ii] >= nn)) return 1; count[array_in[ii]]++; } for (ii = 0; ii < nn; ii++) if (count[ii] != 1) return 1; return 0; } /* ========================================================================= */ int perm_n_parity(int nn, int array_in[]) /* ------------------------------------------------------------------------- */ { int temp_array[MAX_CHECK_PERM_N]; int ii, jj, n_cycles; for (ii = 0; ii < nn; ii++) temp_array[ii] = 0; n_cycles = 0; for (ii = 0; ii < nn; ii++) if (temp_array[ii] == 0) { n_cycles++; jj = ii; while (temp_array[jj] == 0) { temp_array[jj] = 1; jj = array_in[jj]; } } return (n_cycles + nn) % 2; } /* ========================================================================= */ int centers_check(int array_in[]) /* return -1 if invalid, 0 if even cube configuration, 1 for odd */ /* ------------------------------------------------------------------------- */ { int parity = 0; int i; int clone[6]; for(i = 0; i < 6; i++) clone[i] = array_in[i]; // put FACE_UP upwards for (i = 0; i<6; i++) if(clone[i] == FACE_U) break; switch(i) { case FACE_U: break; case FACE_F: four_cycle(clone, FACE_U, FACE_F, FACE_D, FACE_B); parity++; break; case FACE_L: four_cycle(clone, FACE_U, FACE_L, FACE_D, FACE_R); parity++; break; case FACE_R: four_cycle(clone, FACE_U, FACE_R, FACE_D, FACE_L); parity++; break; case FACE_B: four_cycle(clone, FACE_U, FACE_B, FACE_D, FACE_F); parity++; break; case FACE_D: two_cycle(clone, FACE_U, FACE_D); two_cycle(clone, FACE_F, FACE_B); break; case 6: return -1; } // now put FACE_FRONT in place for (i = 0; i<6; i++) if(clone[i] == FACE_F) break; switch(i) { case FACE_F: break; case FACE_L: four_cycle(clone, FACE_F, FACE_L, FACE_B, FACE_R); parity++; break; case FACE_R: four_cycle(clone, FACE_F, FACE_R, FACE_B, FACE_L); parity++; break; case FACE_B: two_cycle(clone, FACE_F, FACE_B); two_cycle(clone, FACE_L, FACE_R); break; case FACE_U: // this is not possible case FACE_D: case 6: return -1; } if(clone[FACE_R] != FACE_R || clone[FACE_L] != FACE_L || clone[FACE_B] != FACE_B || clone[FACE_D] != FACE_D) return -1; return parity & 1; } /* ========================================================================= */ int string_to_cube(char string[], Cube *p_cube, int give_err_msg) /* ------------------------------------------------------------------------- */ /* input: string[] */ { char center_str[6][2], edge_str[12][3], corner_str[8][4]; int center_arr[6], edge_arr[12], corner_arr[8]; int ii, jj, twist, flip, edge_par, corner_par, center_par; int stat; stat = 0; if (sscanf(string, "%1s %1s %1s %1s %1s %1s %2s %2s %2s %2s %2s %2s %2s %2s %2s %2s %2s %2s %3s %3s %3s %3s %3s %3s %3s %3s", center_str[0], center_str[1], center_str[2], center_str[3], center_str[4], center_str[5], edge_str[0], edge_str[1], edge_str[2], edge_str[3], edge_str[4], edge_str[5], edge_str[6], edge_str[7], edge_str[8], edge_str[9], edge_str[10], edge_str[11], corner_str[0], corner_str[1], corner_str[2], corner_str[3], corner_str[4], corner_str[5], corner_str[6], corner_str[7]) < 20) { if (give_err_msg) printf("invalid input!\n"); return 1; } for (ii = 0; ii < 6 ; ii++) { for (jj = 0; jj < 6; jj++) if(strcmp(center_str[ii], center_cubie_str[jj]) == 0) { p_cube->centers[ii] = jj; break; } if(jj == 6) { if (give_err_msg) printf("invalid center cubie: %s\n", center_str[ii]); stat = 1; } } for (ii = 0; ii < 12; ii++) { for (jj = 0; jj < 24; jj++) if (strcmp(edge_str[ii], edge_cubie_str[jj]) == 0) { p_cube->edges[ii] = jj; break; } if (jj == 24) { if (give_err_msg) printf("invalid edge cubie: %s\n", edge_str[ii]); stat = 1; } } for (ii = 0; ii < 8; ii++) { for (jj = 0; jj < 24; jj++) if (strcmp(corner_str[ii], corner_cubie_str[jj]) == 0) { p_cube->corners[ii] = jj; break; } if (jj == 24) { if (give_err_msg) printf("invalid corner cubie: %s\n", corner_str[ii]); stat = 1; } } if (stat) return stat; /* fill out the remaining oriented edges and corners */ for (ii = 12; ii < 24; ii++) p_cube->edges[ii] = (12 + p_cube->edges[ii - 12]) % 24; for (ii = 8; ii < 24; ii++) p_cube->corners[ii] = (8 + p_cube->corners[ii - 8]) % 24; /* now check to see that it's a legal cube */ center_par = centers_check(p_cube->centers); if (center_par == -1) { if (give_err_msg) printf("bad center cubies\n"); stat = 1; } if (perm_n_check(24, p_cube->edges)) { if (give_err_msg) printf("bad edge cubies\n"); stat = 1; } if (perm_n_check(24, p_cube->corners)) { if (give_err_msg) printf("bad corner cubies\n"); stat = 1; } if (stat) return stat; flip = 0; for (ii = 0; ii < 12; ii++) flip += (p_cube->edges[ii] / 12); if ((flip % 2) != 0) { if (give_err_msg) printf("flip any edge cubie!\n"); stat = 1; } twist = 0; for (ii = 0; ii < 8; ii++) twist += (p_cube->corners[ii] / 8); twist %= 3; if (twist != 0) { if (give_err_msg) printf("twist any corner cubie %sclockwise!\n", (twist == 1) ? "counter" : ""); stat = 1; } for (ii = 0; ii < 12; ii++) edge_arr[ii] = p_cube->edges[ii] % 12; edge_par = perm_n_parity(12, edge_arr); for (ii = 0; ii < 8; ii++) corner_arr[ii] = p_cube->corners[ii] % 8; corner_par = perm_n_parity(8, corner_arr); if (((edge_par + corner_par + center_par) & 1) == 1) { if (give_err_msg) printf("swap any two edge cubies or any two corner cubies!\n"); stat = 1; } return stat; } /* ========================================================================= */ int user_enters_cube(Cube *p_cube) /* ------------------------------------------------------------------------- */ { char line_str[256]; printf("\nenter cube (Ctrl-D to exit):\n"); line_str[0] = '\n'; while (line_str[0] == '\n') /* ignore blank lines */ { if (fgets(line_str, 256, stdin) == NULL) return -1; if (line_str[0] == '%') /* echo comments */ { printf("%s", line_str); line_str[0] = '\n'; } } return string_to_cube(line_str, p_cube, 1); } /* ========================================================================= */ int compute_pixels_front(Cube *p_cube, int pixels[9]) /* ------------------------------------------------------------------------- */ { pixels[0] = corner_cubie_color[p_cube->corners[CORNER_FUL]]; pixels[1] = edge_cubie_color[p_cube->edges[EDGE_FU]]; pixels[2] = corner_cubie_color[p_cube->corners[CORNER_FRU]]; pixels[3] = edge_cubie_color[p_cube->edges[EDGE_FL]]; pixels[4] = p_cube->centers[FACE_F]; pixels[5] = edge_cubie_color[p_cube->edges[EDGE_FR]]; pixels[6] = corner_cubie_color[p_cube->corners[CORNER_FLD]]; pixels[7] = edge_cubie_color[p_cube->edges[EDGE_FD]]; pixels[8] = corner_cubie_color[p_cube->corners[CORNER_FDR]]; } /* ========================================================================= */ int compute_pixels_back(Cube *p_cube, int pixels[9]) /* ------------------------------------------------------------------------- */ { pixels[0] = corner_cubie_color[p_cube->corners[CORNER_BUR]]; pixels[1] = edge_cubie_color[p_cube->edges[EDGE_BU]]; pixels[2] = corner_cubie_color[p_cube->corners[CORNER_BLU]]; pixels[3] = edge_cubie_color[p_cube->edges[EDGE_BR]]; pixels[4] = p_cube->centers[FACE_B]; pixels[5] = edge_cubie_color[p_cube->edges[EDGE_BL]]; pixels[6] = corner_cubie_color[p_cube->corners[CORNER_BRD]]; pixels[7] = edge_cubie_color[p_cube->edges[EDGE_BD]]; pixels[8] = corner_cubie_color[p_cube->corners[CORNER_BDL]]; } /* ========================================================================= */ int main(void) /* ------------------------------------------------------------------------- */ { Cube cube_struct; int stat; int i; int pixels[9]; while (1) { stat = user_enters_cube(&cube_struct); if (stat != 0) break; printf("cube looks fine\n"); compute_pixels_front(&cube_struct, pixels); for(i = 0; i<9; i++) printf("%d", pixels[i]); printf("\n"); compute_pixels_back(&cube_struct, pixels); for(i = 0; i<9; i++) printf("%d", pixels[i]); printf("\n"); } exit(EXIT_SUCCESS); return 0; /* haha */ }