research/2008-rubik/rubikutils/rubik.c

#include <stdio.h>
#include <stdlib.h>

#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  */
}