project/Nokia61/Nokia61.c

   1 #define SIZE_EDGE (3)
   2 #define SIZE_ROT (2)
   3 #define PROGRESS 5000
   4 #define ROT_ONEKEY 1
   5 /*
   6 #define DEBUG 1
   7  */
   8 #define NDEBUG 1
   9
  10 #include <stdio.h>
  11 #include <string.h>
  12 #include <stdlib.h>
  13 #include <time.h>
  14 #include <unistd.h>
  15 #include <assert.h>
  16
  17 #define SIZE_TOT (SIZE_EDGE*SIZE_EDGE)
  18
  19 typedef unsigned char num;
  20 typedef unsigned int pos;
  21 typedef num field[SIZE_TOT];
  22
  23 #define INVALID_POS ((pos)-1)
  24
  25 #define RC_ENTRY(x,y) ((y)*SIZE_EDGE+(x))
  26
  27 #if SIZE_EDGE==3
  28 #define STATES_TOT (362880)
  29 #define FILENAME_23 "Nokia61_23.cache"
  30 #define ROUNDCYCLE_TOT (sizeof(roundcycle)/sizeof(*roundcycle))
  31 static const unsigned char roundcycle[]={
  32         RC_ENTRY(0,0),
  33         RC_ENTRY(1,0),
  34         RC_ENTRY(1,1),
  35         RC_ENTRY(0,1),
  36         };
  37 #else
  38 #error "STATES_TOT not known!"
  39 #endif
  40
  41 struct state {
  42         pos todo_next;
  43         pos parent;
  44         pos depth;
  45         } states[STATES_TOT];
  46 pos todo=INVALID_POS;
  47 pos *todo_tail=&todo;
  48
  49 #ifdef PROGRESS
  50 pos states_touched=0,states_retouched=0,states_done=0;
  51 pos maxdepth=0;
  52 #endif
  53
  54 static const num ascending[25]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24};
  55
  56 static int check_field(const field fld)
  57 {
  58 unsigned char used[SIZE_TOT];
  59 int i;
  60
  61         memset(used,0,sizeof(used));
  62         for (i=0;i<SIZE_TOT;i++) {
  63                 if (fld[i]>=SIZE_TOT || used[fld[i]])
  64                         return(0);
  65                 used[fld[i]]=1;
  66                 }
  67         return(1);
  68 }
  69
  70 #define assert_field(fld) assert(check_field(fld))
  71
  72 static void dump_field(const field fld)
  73 {
  74 unsigned char y,x;
  75
  76         for (y=0;y<SIZE_EDGE;y++) {
  77                 fputs("  ",stdout);
  78                 for (x=0;x<SIZE_EDGE;x++)
  79                         printf(" %2u",fld[y*SIZE_EDGE+x]+1);
  80                 putchar('\n');
  81                 }
  82 }
  83
  84 static pos field_to_pos(const field fld)
  85 {
  86 num points[SIZE_TOT],remains;
  87 pos r=0;
  88
  89 #ifdef DEBUG
  90         puts("field_to_pos(");
  91         dump_field(fld);
  92 #endif
  93
  94         assert_field(fld);
  95         memcpy(points,ascending,sizeof(points));
  96         for (remains=SIZE_TOT;remains;remains--) {
  97 num n=*fld++;
  98
  99                 n=(num *)memchr(points,n,remains)-points;
 100                 r*=remains;
 101                 r+=n;
 102                 memmove(points+n,points+n+1,remains-n-1);
 103                 }
 104
 105 #ifdef DEBUG
 106         printf("  )=%u\n",r);
 107 #endif
 108
 109         return(r);
 110 }
 111
 112 static void pos_to_field(field fld,pos p)
 113 {
 114 num points[SIZE_TOT],expanded[SIZE_TOT],remains;
 115 #if defined(DEBUG) || !defined(NDEBUG)
 116 num *fld_orig=fld;
 117 #endif
 118 #ifndef NDEBUG
 119 pos p_orig=p;
 120 #endif
 121
 122 #ifdef DEBUG
 123         printf("pos_to_field(%u)=\n",p);
 124 #endif
 125
 126         for (remains=1;remains<=SIZE_TOT;remains++) {
 127 num n=p%remains;
 128
 129                 p/=remains;
 130                 expanded[SIZE_TOT-remains]=n;
 131                 }
 132         memcpy(points,ascending,sizeof(points));
 133         for (remains=SIZE_TOT;remains;remains--) {
 134 num n=expanded[SIZE_TOT-remains];
 135
 136                 p/=remains;
 137                 *fld++=points[n];
 138                 memmove(points+n,points+n+1,remains-n-1);
 139                 }
 140
 141 #ifdef DEBUG
 142         dump_field(fld_orig);
 143 #endif
 144
 145         assert(!p);
 146         assert(p_orig==field_to_pos(fld_orig));
 147 }
 148
 149 static void mark(pos p,pos parent,pos depth)
 150 {
 151 struct state *state;
 152
 153         assert(p>=0 && p<STATES_TOT);
 154         state=states+p;
 155         if (!(state->parent==INVALID_POS || state->depth>depth))
 156                 return;
 157 #ifdef PROGRESS
 158         if (maxdepth<depth)
 159                 maxdepth=depth;
 160 #endif
 161         state->parent=parent;
 162         state->depth=depth;
 163         if (state->todo_next==INVALID_POS) {
 164                 *todo_tail=p;
 165                 todo_tail=&state->todo_next;
 166 #ifdef PROGRESS
 167                 states_touched++;
 168 #endif
 169                 }
 170         else {
 171 #ifdef PROGRESS
 172                 states_retouched++;
 173 #endif
 174                 }
 175 }
 176
 177 static void progress_dump(void)
 178 {
 179 #ifdef PROGRESS
 180         printf("TOUCHED=%6u (RETOUCHED %6u), DONE=%6u, KNOWN TODO=%6u, UNTOUCHED=%6u, MAXDEPTH=%6u\n",
 181                         states_touched,states_retouched,states_done,states_touched-states_done,STATES_TOT-states_touched,maxdepth);
 182 #endif
 183 }
 184
 185 #ifdef PROGRESS
 186 static void states_progress(void)
 187 {
 188 static unsigned period=0;
 189 static time_t time_last=0;
 190 time_t time_new;
 191
 192         if (period++<PROGRESS)
 193                 return;
 194         period=0;
 195         if (time(&time_new)<5+time_last)
 196                 return;
 197         time_last=time_new;
 198         progress_dump();
 199 }
 200 #endif
 201
 202 static void cycle(void)
 203 {
 204 pos p;
 205
 206         while ((p=todo)!=INVALID_POS) {
 207 struct state *state=states+p;
 208 field fld;
 209 unsigned char y,x,cyc;
 210
 211                 pos_to_field(fld,p);
 212 #ifdef DEBUG
 213                 printf("START: %u\n",p);
 214 #endif
 215                 for (y=0;y<=SIZE_EDGE-SIZE_ROT;y++)
 216                 for (x=0;x<=SIZE_EDGE-SIZE_ROT;x++)
 217                 for (cyc=0;cyc<ROUNDCYCLE_TOT;cyc++) {
 218 num swap,*base;
 219 unsigned char cyci;
 220
 221                         base=fld+y*SIZE_EDGE+x;
 222                         for (cyci=0;cyci<ROUNDCYCLE_TOT-1;cyci++) {
 223                                 swap=base[roundcycle[cyci]];
 224                                 base[roundcycle[cyci]]=base[roundcycle[cyci+1]];
 225                                 base[roundcycle[cyci+1]]=swap;
 226                                 }
 227 #ifdef ROT_ONEKEY
 228                         if (!(cyc&1))
 229 #endif
 230                                 mark(field_to_pos(fld),p,state->depth+1);
 231                         }
 232                 todo=state->todo_next;
 233                 state->todo_next=INVALID_POS;
 234 #ifdef PROGRESS
 235                 states_done++;
 236                 states_progress();
 237 #endif
 238                 }
 239 }
 240
 241 static void final(void)
 242 {
 243 #ifdef PROGRESS
 244 pos *maxes,p;
 245 int maxi;
 246 #endif
 247
 248         puts("FINAL:");
 249         progress_dump();
 250 #ifdef PROGRESS
 251         fputs("Depth distribution:",stdout);
 252         maxes=malloc(sizeof(*maxes)*(maxdepth+1));
 253         memset(maxes,0,sizeof(maxes));
 254         for (p=0;p<STATES_TOT;p++)
 255                 maxes[states[p].depth]++;
 256         for (maxi=0;maxi<=maxdepth;maxi++)
 257                 printf(" %d(=%d)",maxi,maxes[maxi]);
 258         free(maxes);
 259         putchar('\n');
 260 #endif
 261         putchar('\n');
 262 }
 263
 264 #if SIZE_EDGE==3
 265
 266 static struct item_23 {
 267         unsigned char a[3];
 268         } *states_23;
 269 #define STATES_23_SIZEOF (sizeof(*states_23)*STATES_TOT)
 270
 271 static int read_23(void)
 272 {
 273 FILE *f;
 274 pos p;
 275 unsigned char eof_mark;
 276
 277         if (!(f=fopen(FILENAME_23,"rb")))
 278                 return(1);
 279         if (!(states_23=malloc(STATES_23_SIZEOF))) {
 280 fail_fclose:
 281                 fclose(f);
 282                 return(1);
 283                 }
 284         if (fread(states_23,1,STATES_23_SIZEOF,f)!=STATES_23_SIZEOF) {
 285 fail_free:
 286                 free(states_23);
 287                 goto fail_fclose;
 288                 }
 289         if (fread(&eof_mark,1,1,f))
 290                 goto fail_free;
 291         for (p=0;p<STATES_TOT;p++) {
 292                 states[p].depth=0;
 293                 states[p].parent=(states_23[p].a[0]<<16)
 294                                | (states_23[p].a[1]<< 8)
 295                                                                          | (states_23[p].a[2]<< 0);
 296                 }
 297         fclose(f);
 298         free(states_23);
 299 #ifdef PROGRESS
 300         printf("Cache read from \"%s\".\n",FILENAME_23);
 301 #endif
 302         return(0);
 303 }
 304
 305 static void write_23(void)
 306 {
 307 FILE *f;
 308 pos p;
 309
 310         if (!(f=fopen(FILENAME_23,"wb"))) {
 311 fail:
 312 #ifdef PROGRESS
 313                 printf("Failed to write cache to \"%s\"!\n",FILENAME_23);
 314 #endif
 315                 return;
 316                 }
 317         if (!(states_23=malloc(STATES_23_SIZEOF))) {
 318 fail_unlink:
 319                 fclose(f);
 320                 unlink(FILENAME_23);
 321                 goto fail;
 322                 }
 323         for (p=0;p<STATES_TOT;p++) {
 324                 states_23[p].a[0]=(states[p].parent>>16);
 325                 states_23[p].a[1]=(states[p].parent>> 8);
 326                 states_23[p].a[2]=(states[p].parent>> 0);
 327                 }
 328         if (fwrite(states_23,1,STATES_23_SIZEOF,f)!=STATES_23_SIZEOF) {
 329 fail_free:
 330                 free(states_23);
 331                 goto fail_unlink;
 332                 }
 333         if (fclose(f))
 334                 goto fail_free;
 335         free(states_23);
 336 #ifdef PROGRESS
 337                 printf("Cache written to \"%s\".\n",FILENAME_23);
 338 #endif
 339 }
 340
 341 #endif /* SIZE_EDGE==3 */
 342
 343 static void input(void)
 344 {
 345 field fld;
 346 int x,y,i;
 347 pos p;
 348 struct state *state;
 349
 350         for (;;) {
 351 restart:
 352                 for (y=0;y<SIZE_EDGE;y++) {
 353                         printf("Enter line #%d/%d: ",y+1,SIZE_EDGE); fflush(stdout);
 354                         for (x=0;x<SIZE_EDGE;x++) {
 355                                 if (1!=scanf("%d",&i)) {
 356                                         if (!y && !x)
 357                                                 return;
 358                                         puts("Error reading input, restarting!");
 359                                         goto restart;
 360                                         }
 361                                 fld[y*SIZE_EDGE+x]=i-1;
 362                                 }
 363                         }
 364                 if (!check_field(fld)) {
 365                         puts("Field not valid!");
 366                         continue;
 367                         }
 368                 puts("-->");
 369                 p=field_to_pos(fld);
 370                 do {
 371                         state=states+p;
 372                         printf("STATE %6u: DEPTH=%6u, PARENT=%6u\n",p,state->depth,state->parent);
 373                         pos_to_field(fld,p);
 374                         dump_field(fld);
 375                         puts("----------");
 376                         p=state->parent;
 377                         } while (state!=states+0);
 378                 putchar('\n');
 379                 }
 380 }
 381
 382 int main(void)
 383 {
 384 #if SIZE_EDGE==3
 385         if (read_23())
 386 #endif
 387         {
 388                 memset(states,-1,sizeof(states));
 389                 mark(0,0,0);
 390                 cycle();
 391                 final();
 392 #if SIZE_EDGE==3
 393                 write_23();
 394 #endif
 395                 }
 396         input();
 397         return(EXIT_SUCCESS);
 398 }