source: research/2008-rubik/rubikutils/rubik.c @ 3200

Last change on this file since 3200 was 2740, checked in by kali, 15 years ago
  • two function to compute pixels shown on front and back face
File size: 17.2 KB
Line 
1#include <stdio.h>
2#include <stdlib.h>
3
4#define  MAX_CHECK_PERM_N                   24
5
6#define  CORNER_UFR                          0
7#define  CORNER_URB                          1
8#define  CORNER_UBL                          2
9#define  CORNER_ULF                          3
10#define  CORNER_DRF                          4
11#define  CORNER_DFL                          5
12#define  CORNER_DLB                          6
13#define  CORNER_DBR                          7
14
15#define  CORNER_FRU                          8
16#define  CORNER_RBU                          9
17#define  CORNER_BLU                         10
18#define  CORNER_LFU                         11
19#define  CORNER_RFD                         12
20#define  CORNER_FLD                         13
21#define  CORNER_LBD                         14
22#define  CORNER_BRD                         15
23
24#define  CORNER_RUF                         16
25#define  CORNER_BUR                         17
26#define  CORNER_LUB                         18
27#define  CORNER_FUL                         19
28#define  CORNER_FDR                         20
29#define  CORNER_LDF                         21
30#define  CORNER_BDL                         22
31#define  CORNER_RDB                         23
32
33#define  EDGE_UF                             0
34#define  EDGE_UR                             1
35#define  EDGE_UB                             2
36#define  EDGE_UL                             3
37#define  EDGE_DF                             4
38#define  EDGE_DR                             5
39#define  EDGE_DB                             6
40#define  EDGE_DL                             7
41#define  EDGE_FR                             8
42#define  EDGE_FL                             9
43#define  EDGE_BR                            10
44#define  EDGE_BL                            11
45
46#define  EDGE_FU                            12
47#define  EDGE_RU                            13
48#define  EDGE_BU                            14
49#define  EDGE_LU                            15
50#define  EDGE_FD                            16
51#define  EDGE_RD                            17
52#define  EDGE_BD                            18
53#define  EDGE_LD                            19
54#define  EDGE_RF                            20
55#define  EDGE_LF                            21
56#define  EDGE_RB                            22
57#define  EDGE_LB                            23
58
59#define  FACE_F                              0
60#define  FACE_R                              1
61#define  FACE_U                              2
62#define  FACE_B                              3
63#define  FACE_L                              4
64#define  FACE_D                              5
65
66
67typedef struct cube
68        {
69        int             centers[6];
70        int             edges[24];
71        int             corners[24];
72        }
73        Cube;
74
75
76static char            *center_cubie_str[] = {"F", "R", "U",
77                                              "B", "L", "D"};
78
79static char            *edge_cubie_str[] = {"UF", "UR", "UB", "UL",
80                                            "DF", "DR", "DB", "DL",
81                                            "FR", "FL", "BR", "BL",
82                                            "FU", "RU", "BU", "LU",
83                                            "FD", "RD", "BD", "LD",
84                                            "RF", "LF", "RB", "LB"};
85
86static int              edge_cubie_color[] = {
87                            FACE_U, FACE_U, FACE_U, FACE_U,
88                            FACE_D, FACE_D, FACE_D, FACE_D,
89                            FACE_F, FACE_F, FACE_B, FACE_B,
90                            FACE_F, FACE_R, FACE_B, FACE_L,
91                            FACE_F, FACE_R, FACE_B, FACE_L,
92                            FACE_R, FACE_L, FACE_R, FACE_L
93                                };
94
95static char            *corner_cubie_str[] = {"UFR", "URB", "UBL", "ULF",
96                                              "DRF", "DFL", "DLB", "DBR",
97                                              "FRU", "RBU", "BLU", "LFU",
98                                              "RFD", "FLD", "LBD", "BRD",
99                                              "RUF", "BUR", "LUB", "FUL",
100                                              "FDR", "LDF", "BDL", "RDB"};
101
102static int              corner_cubie_color[] = {
103                            FACE_U, FACE_U, FACE_U, FACE_U,
104                            FACE_D, FACE_D, FACE_D, FACE_D,
105                            FACE_F, FACE_R, FACE_B, FACE_L,
106                            FACE_R, FACE_F, FACE_L, FACE_B,
107                            FACE_R, FACE_B, FACE_L, FACE_F,
108                            FACE_F, FACE_L, FACE_B, FACE_R};
109
110/* ========================================================================= */
111   void  two_cycle(int  array[], int  ind0, int  ind1)
112/* ------------------------------------------------------------------------- */
113
114{
115int                     temp;
116
117
118temp = array[ind0];
119array[ind0] = array[ind1];
120array[ind1] = temp;
121
122return;
123}
124
125
126/* ========================================================================= */
127   void  three_cycle(int  array[], int  ind0, int  ind1, int  ind2)
128/* ------------------------------------------------------------------------- */
129
130{
131int                     temp;
132
133
134temp = array[ind0];
135array[ind0] = array[ind1];
136array[ind1] = array[ind2];
137array[ind2] = temp;
138
139return;
140}
141
142
143/* ========================================================================= */
144   void  four_cycle(int  array[], int  ind0, int  ind1, int  ind2, int  ind3)
145/* ------------------------------------------------------------------------- */
146
147{
148int                     temp;
149
150
151temp = array[ind0];
152array[ind0] = array[ind1];
153array[ind1] = array[ind2];
154array[ind2] = array[ind3];
155array[ind3] = temp;
156
157return;
158}
159
160
161/* ========================================================================= */
162   void  print_cube(Cube  *p_cube)
163/* ------------------------------------------------------------------------- */
164
165{
166printf("%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",
167 center_cubie_str[p_cube->centers[0]], center_cubie_str[p_cube->centers[1]],
168 center_cubie_str[p_cube->centers[2]], center_cubie_str[p_cube->centers[3]],
169 center_cubie_str[p_cube->centers[4]], center_cubie_str[p_cube->centers[5]],
170       edge_cubie_str[p_cube->edges[0]], edge_cubie_str[p_cube->edges[1]],
171       edge_cubie_str[p_cube->edges[2]], edge_cubie_str[p_cube->edges[3]],
172       edge_cubie_str[p_cube->edges[4]], edge_cubie_str[p_cube->edges[5]],
173       edge_cubie_str[p_cube->edges[6]], edge_cubie_str[p_cube->edges[7]],
174       edge_cubie_str[p_cube->edges[8]], edge_cubie_str[p_cube->edges[9]],
175       edge_cubie_str[p_cube->edges[10]], edge_cubie_str[p_cube->edges[11]],
176   corner_cubie_str[p_cube->corners[0]], corner_cubie_str[p_cube->corners[1]],
177   corner_cubie_str[p_cube->corners[2]], corner_cubie_str[p_cube->corners[3]],
178   corner_cubie_str[p_cube->corners[4]], corner_cubie_str[p_cube->corners[5]],
179   corner_cubie_str[p_cube->corners[6]], corner_cubie_str[p_cube->corners[7]]);
180
181return;
182}
183
184/* ========================================================================= */
185   void  perm_n_init(int  nn, int  array_out[])
186/* ------------------------------------------------------------------------- */
187
188{
189int                     ii;
190
191
192for (ii = 0; ii < nn; ii++)
193    array_out[ii] = ii;
194
195return;
196}
197
198
199/* ========================================================================= */
200   void  cube_init(Cube  *p_cube)
201/* ------------------------------------------------------------------------- */
202
203{
204perm_n_init(6, p_cube->centers);
205perm_n_init(24, p_cube->edges);
206perm_n_init(24, p_cube->corners);
207
208return;
209}
210
211/* ========================================================================= */
212   int  perm_n_check(int  nn, int  array_in[])
213/* ------------------------------------------------------------------------- */
214
215{
216int                     count[MAX_CHECK_PERM_N], ii;
217
218
219for (ii = 0; ii < nn; ii++)
220    count[ii] = 0;
221
222for (ii = 0; ii < nn; ii++)
223    {
224    if ((array_in[ii] < 0) || (array_in[ii] >= nn))
225       return 1;
226
227    count[array_in[ii]]++;
228    }
229
230for (ii = 0; ii < nn; ii++)
231    if (count[ii] != 1)
232       return 1;
233
234return 0;
235}
236
237/* ========================================================================= */
238   int  perm_n_parity(int  nn, int  array_in[])
239/* ------------------------------------------------------------------------- */
240
241{
242int                     temp_array[MAX_CHECK_PERM_N];
243int                     ii, jj, n_cycles;
244
245
246for (ii = 0; ii < nn; ii++)
247    temp_array[ii] = 0;
248
249n_cycles = 0;
250
251for (ii = 0; ii < nn; ii++)
252    if (temp_array[ii] == 0)
253       {
254       n_cycles++;
255       jj = ii;
256       while (temp_array[jj] == 0)
257             {
258             temp_array[jj] = 1;
259             jj = array_in[jj];
260             }
261       }
262
263return (n_cycles + nn) % 2;
264}
265
266
267
268/* ========================================================================= */
269   int  centers_check(int  array_in[])
270/* return -1 if invalid, 0 if even cube configuration, 1 for odd */
271/* ------------------------------------------------------------------------- */
272
273{
274    int parity = 0;
275    int i;
276
277    int clone[6];
278    for(i = 0; i < 6; i++)
279        clone[i] = array_in[i];
280
281    // put FACE_UP upwards
282    for (i = 0; i<6; i++)
283        if(clone[i] == FACE_U)
284            break;
285
286    switch(i) {
287        case FACE_U:
288            break;
289        case FACE_F:
290            four_cycle(clone, FACE_U, FACE_F, FACE_D, FACE_B);
291            parity++;
292            break;
293        case FACE_L:
294            four_cycle(clone, FACE_U, FACE_L, FACE_D, FACE_R);
295            parity++;
296            break;
297        case FACE_R:
298            four_cycle(clone, FACE_U, FACE_R, FACE_D, FACE_L);
299            parity++;
300            break;
301        case FACE_B:
302            four_cycle(clone, FACE_U, FACE_B, FACE_D, FACE_F);
303            parity++;
304            break;
305        case FACE_D:
306            two_cycle(clone, FACE_U, FACE_D);
307            two_cycle(clone, FACE_F, FACE_B);
308            break;
309        case 6:
310            return -1;
311    }
312
313    // now put FACE_FRONT in place
314    for (i = 0; i<6; i++)
315        if(clone[i] == FACE_F)
316            break;
317    switch(i) {
318        case FACE_F:
319            break;
320        case FACE_L:
321            four_cycle(clone, FACE_F, FACE_L, FACE_B, FACE_R);
322            parity++;
323            break;
324        case FACE_R:
325            four_cycle(clone, FACE_F, FACE_R, FACE_B, FACE_L);
326            parity++;
327            break;
328        case FACE_B:
329            two_cycle(clone, FACE_F, FACE_B);
330            two_cycle(clone, FACE_L, FACE_R);
331            break;
332        case FACE_U: // this is not possible
333        case FACE_D:
334        case 6:
335            return -1;
336    }
337
338    if(clone[FACE_R] != FACE_R || clone[FACE_L] != FACE_L
339        || clone[FACE_B] != FACE_B || clone[FACE_D] != FACE_D)
340        return -1;
341
342    return parity & 1;
343}
344
345/* ========================================================================= */
346   int  string_to_cube(char  string[], Cube  *p_cube, int  give_err_msg)
347/* ------------------------------------------------------------------------- */
348
349/*  input:  string[]  */
350
351{
352char                    center_str[6][2], edge_str[12][3], corner_str[8][4];
353int                     center_arr[6], edge_arr[12], corner_arr[8];
354int                     ii, jj, twist, flip, edge_par, corner_par, center_par;
355int                     stat;
356
357
358stat = 0;
359
360if (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",
361           center_str[0], center_str[1], center_str[2],
362           center_str[3], center_str[4], center_str[5],
363           edge_str[0], edge_str[1], edge_str[2], edge_str[3],
364           edge_str[4], edge_str[5], edge_str[6], edge_str[7],
365           edge_str[8], edge_str[9], edge_str[10], edge_str[11],
366           corner_str[0], corner_str[1], corner_str[2], corner_str[3],
367           corner_str[4], corner_str[5], corner_str[6], corner_str[7]) < 20)
368   {
369   if (give_err_msg)
370      printf("invalid input!\n");
371   return 1;
372   }
373
374for (ii = 0; ii < 6  ; ii++)
375    {
376    for (jj = 0; jj < 6; jj++)
377        if(strcmp(center_str[ii], center_cubie_str[jj]) == 0)
378        {
379            p_cube->centers[ii] = jj;
380            break;
381        }
382        if(jj == 6)
383       {
384       if (give_err_msg)
385          printf("invalid center cubie: %s\n", center_str[ii]);
386       stat = 1;
387       }
388    }
389
390for (ii = 0; ii < 12; ii++)
391    {
392    for (jj = 0; jj < 24; jj++)
393        if (strcmp(edge_str[ii], edge_cubie_str[jj]) == 0)
394           {
395           p_cube->edges[ii] = jj;
396           break;
397           }
398    if (jj == 24)
399       {
400       if (give_err_msg)
401          printf("invalid edge cubie: %s\n", edge_str[ii]);
402       stat = 1;
403       }
404    }
405
406for (ii = 0; ii < 8; ii++)
407    {
408    for (jj = 0; jj < 24; jj++)
409        if (strcmp(corner_str[ii], corner_cubie_str[jj]) == 0)
410           {
411           p_cube->corners[ii] = jj;
412           break;
413           }
414    if (jj == 24)
415       {
416       if (give_err_msg)
417          printf("invalid corner cubie: %s\n", corner_str[ii]);
418       stat = 1;
419       }
420    }
421
422if (stat)
423   return stat;
424
425/*  fill out the remaining oriented edges and corners  */
426
427for (ii = 12; ii < 24; ii++)
428    p_cube->edges[ii] = (12 + p_cube->edges[ii - 12]) % 24;
429
430for (ii = 8; ii < 24; ii++)
431    p_cube->corners[ii] = (8 + p_cube->corners[ii - 8]) % 24;
432
433/*  now check to see that it's a legal cube  */
434
435center_par = centers_check(p_cube->centers);
436if (center_par == -1)
437    {
438   if (give_err_msg)
439      printf("bad center cubies\n");
440   stat = 1;
441    }
442
443if (perm_n_check(24, p_cube->edges))
444   {
445   if (give_err_msg)
446      printf("bad edge cubies\n");
447   stat = 1;
448   }
449
450if (perm_n_check(24, p_cube->corners))
451   {
452   if (give_err_msg)
453      printf("bad corner cubies\n");
454   stat = 1;
455   }
456
457if (stat)
458   return stat;
459
460flip = 0;
461for (ii = 0; ii < 12; ii++)
462    flip += (p_cube->edges[ii] / 12);
463
464if ((flip % 2) != 0)
465   {
466   if (give_err_msg)
467      printf("flip any edge cubie!\n");
468   stat = 1;
469   }
470
471twist = 0;
472for (ii = 0; ii < 8; ii++)
473    twist += (p_cube->corners[ii] / 8);
474
475twist %= 3;
476
477if (twist != 0)
478   {
479   if (give_err_msg)
480      printf("twist any corner cubie %sclockwise!\n",
481              (twist == 1) ? "counter" : "");
482   stat = 1;
483   }
484
485for (ii = 0; ii < 12; ii++)
486    edge_arr[ii] = p_cube->edges[ii] % 12;
487
488edge_par = perm_n_parity(12, edge_arr);
489
490for (ii = 0; ii < 8; ii++)
491    corner_arr[ii] = p_cube->corners[ii] % 8;
492
493corner_par = perm_n_parity(8, corner_arr);
494
495if (((edge_par +  corner_par + center_par) & 1) == 1)
496   {
497   if (give_err_msg)
498      printf("swap any two edge cubies or any two corner cubies!\n");
499   stat = 1;
500   }
501
502return stat;
503}
504
505
506/* ========================================================================= */
507   int  user_enters_cube(Cube  *p_cube)
508/* ------------------------------------------------------------------------- */
509
510{
511char                     line_str[256];
512
513
514printf("\nenter cube (Ctrl-D to exit):\n");
515
516line_str[0] = '\n';
517
518while (line_str[0] == '\n')           /*  ignore blank lines  */
519      {
520      if (fgets(line_str, 256, stdin) == NULL)
521         return -1;
522
523      if (line_str[0] == '%')         /*  echo comments  */
524         {
525         printf("%s", line_str);
526         line_str[0] = '\n';
527         }
528      }
529
530return string_to_cube(line_str, p_cube, 1);
531}
532
533/* ========================================================================= */
534   int  compute_pixels_front(Cube  *p_cube, int pixels[9])
535/* ------------------------------------------------------------------------- */
536
537{
538    pixels[0] = corner_cubie_color[p_cube->corners[CORNER_FUL]];
539    pixels[1] = edge_cubie_color[p_cube->edges[EDGE_FU]];
540    pixels[2] = corner_cubie_color[p_cube->corners[CORNER_FRU]];
541
542    pixels[3] = edge_cubie_color[p_cube->edges[EDGE_FL]];
543    pixels[4] = p_cube->centers[FACE_F];
544    pixels[5] = edge_cubie_color[p_cube->edges[EDGE_FR]];
545
546    pixels[6] = corner_cubie_color[p_cube->corners[CORNER_FLD]];
547    pixels[7] = edge_cubie_color[p_cube->edges[EDGE_FD]];
548    pixels[8] = corner_cubie_color[p_cube->corners[CORNER_FDR]];
549}
550
551
552/* ========================================================================= */
553   int  compute_pixels_back(Cube  *p_cube, int pixels[9])
554/* ------------------------------------------------------------------------- */
555
556{
557    pixels[0] = corner_cubie_color[p_cube->corners[CORNER_BUR]];
558    pixels[1] = edge_cubie_color[p_cube->edges[EDGE_BU]];
559    pixels[2] = corner_cubie_color[p_cube->corners[CORNER_BLU]];
560
561    pixels[3] = edge_cubie_color[p_cube->edges[EDGE_BR]];
562    pixels[4] = p_cube->centers[FACE_B];
563    pixels[5] = edge_cubie_color[p_cube->edges[EDGE_BL]];
564
565    pixels[6] = corner_cubie_color[p_cube->corners[CORNER_BRD]];
566    pixels[7] = edge_cubie_color[p_cube->edges[EDGE_BD]];
567    pixels[8] = corner_cubie_color[p_cube->corners[CORNER_BDL]];
568}
569
570/* ========================================================================= */
571   int  main(void)
572/* ------------------------------------------------------------------------- */
573
574{
575Cube                    cube_struct;
576int                     stat;
577int                     i;
578int                     pixels[9];
579
580while (1)
581      {
582      stat = user_enters_cube(&cube_struct);
583      if (stat != 0)
584         break;
585    printf("cube looks fine\n");
586compute_pixels_front(&cube_struct, pixels);
587for(i = 0; i<9; i++)
588    printf("%d", pixels[i]);
589    printf("\n");
590compute_pixels_back(&cube_struct, pixels);
591for(i = 0; i<9; i++)
592    printf("%d", pixels[i]);
593    printf("\n");
594    }
595exit(EXIT_SUCCESS);
596
597return 0;  /*  haha  */
598}
Note: See TracBrowser for help on using the repository browser.