project/oslik/oslik/oslik.c

   1 /* Sorry, BSD for alloca(). */
   2
   3 #define _BSD_SOURCE
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include <assert.h>
   9
  10 #define HTAB_SIZE 56783
  11
  12 /* #define STSTEP 100 */
  13 /* #undef NDEBUG */
  14 /* #define BENCHMARK */
  15
  16 typedef char stt[20];
  17 #define SaXYL(x,y) ((x)+(y)*5)
  18 #define SaLX(l) ((l)%5)
  19 #define SaLY(l) ((l)/5)
  20 #define SaLXY(l,x,y) do { (x)=SaLX((l)); (y)=SaLY((l)); } while (0)
  21
  22 unsigned total=0,solutions=0;
  23 #ifdef STSTEP
  24 unsigned gone=0;
  25 #endif
  26
  27 stt init=
  28         "{}{}#"
  29         "AB^#+"
  30         "CDv#+"
  31         "{}{}#";
  32
  33 struct st {
  34         struct st *nexttogo,*nextinchain,*ost;
  35         stt data;
  36         } *togo,**togop=&togo,*togonow,*htab[HTAB_SIZE];
  37 int level=-1;
  38
  39 static void chk(void *p)
  40 {
  41         if (p) return;
  42         fprintf(stderr,"Virtual memory exhausted!\n");
  43         exit(EXIT_FAILURE);
  44 }
  45 #define chknew(a) chk((a)=malloc(sizeof(*(a))))
  46
  47 static unsigned hash(const char *st)
  48 {
  49 unsigned r=7;
  50 unsigned char i;
  51
  52         for (i=0;i<20;i++)
  53                 r=r*13+(*st++);
  54         return r%HTAB_SIZE;
  55 }
  56
  57 static struct st **findhash(const char *st,unsigned hval)
  58 {
  59 struct st **r;
  60         for (r=&htab[hval];*r;r=&(*r)->nextinchain)
  61                 if (!memcmp((*r)->data,st,20)) break;
  62         return r;
  63 }
  64
  65 static void dumpst(const char *st)
  66 {
  67 unsigned char yi;
  68
  69         for (yi=0;yi<4;yi++)
  70                 printf("  | %.5s |\n",st+SaXYL(0,yi));
  71         puts("  \\-------/");
  72 }
  73
  74 static void addstate(const char *st,struct st *ost)
  75 {
  76 struct st *now,**nowp;
  77 unsigned hval;
  78
  79         hval=hash(st);
  80         if (*(nowp=findhash(st,hval))) return;
  81 #ifndef NDEBUG
  82         if (ost) {
  83                 puts("***addstate:");
  84                 dumpst(st);
  85                 }
  86 #endif
  87         chk(now=malloc(sizeof(*now)));
  88         *togop=now;togop=&now->nexttogo; now->nexttogo=NULL;
  89         now->nextinchain=NULL; *nowp=now;
  90         memcpy(now->data,st,20);
  91         now->ost=ost;
  92         total++;
  93 }
  94
  95 static char isdest(const char *st)
  96 {
  97         return (st[SaXYL(3,1)]=='A' && st[SaXYL(4,1)]=='B'
  98               &&st[SaXYL(3,2)]=='C' && st[SaXYL(4,2)]=='D');
  99 }
 100
 101 static void trymoves(struct st *sts)
 102 {
 103 char *st=sts->data;
 104 stt nst;
 105 int blk[2],bli,oi,nbp;
 106 static const char offs[4][2]={{0,-1},{+1,0},{0,+1},{-1,0}};
 107 char bx,by,nbx,nby,gx=0,gy=0,gxs=0,gys=0,sx,sy,xi,yi;
 108
 109 #if 0
 110 /*ndef NDEBUG*/
 111         printf("Entered trymoves()\n");
 112         dumpst(st);
 113 #endif
 114         if (isdest(st)) {
 115 struct st *o;
 116 int lev=0;
 117 struct back {
 118         struct back *next;
 119         struct st *st;
 120         } *back=NULL,*b;
 121                 for (o=sts;o;o=o->ost) {
 122                         chk(b=alloca(sizeof(*b)));
 123                         b->next=back;
 124                         back=b;
 125                         b->st=o;
 126                         }
 127
 128                 solutions++;
 129 #ifndef BENCHMARK
 130 #if 1
 131                 puts("*** GOAL");
 132 #else
 133                 printf("*** GOAL: level=%d\n",level);
 134 #endif
 135 #endif
 136                 while (back) {
 137 #ifndef BENCHMARK
 138                         printf("> /-------\\ forwardtrace: level=%d\n",lev++);
 139                         dumpst(back->st->data);
 140 #endif
 141                         back=back->next;
 142                         }
 143                 }
 144         blk[0]=((char *)memchr(st           ,'+',20           ))-((char *)st); assert(blk[0]<20);
 145         blk[1]=((char *)memchr(st+(blk[0]+1),'+',20-(blk[0]+1)))-((char *)st); assert(blk[1]<20);
 146         assert(!memchr(st+(blk[1]+1),'+',20-(blk[1]+1)));
 147         for (bli=0;bli<2;bli++) {
 148                 SaLXY(blk[bli],bx,by);
 149                 for (oi=0;oi<4;oi++) {
 150                         nbx=bx+(sx=offs[oi][0]);
 151                         nby=by+(sy=offs[oi][1]);
 152                         if (nbx<0 || nbx>=5 || nby<0 || nby>=4) {
 153 failed: continue;
 154                                 }
 155
 156 #define CHKPOS(xs,ys,dx,dy) do { char nxb=nbx-dx,nyb=nby-dy; \
 157         if (nxb<0 || nxb+xs>5 || nyb<0 || nyb+ys>5) goto failed; \
 158         for (xi=0;xi<(xs);xi++) for (yi=0;yi<(ys);yi++) { \
 159                 if (xi-sx>=0&&xi-sx<xs&&yi-sy>=0&&yi-sy<ys) continue; \
 160                 if (st[SaXYL(bx-dx+xi,by-dy+yi) ]!='+') goto failed; \
 161                 } \
 162   gx=nbx-dx; gy=nby-dy; gxs=xs; gys=ys; \
 163   } while (0)
 164
 165                         nbp=SaXYL(nbx,nby);
 166                         switch (st[nbp]) {
 167                                 case '{': CHKPOS(2,1, 0, 0); break;
 168                                 case '}': CHKPOS(2,1,+1, 0); break;
 169                                 case '^': CHKPOS(1,2, 0, 0); break;
 170                                 case 'v': CHKPOS(1,2, 0,+1); break;
 171                                 case '#': CHKPOS(1,1, 0, 0); break;
 172                                 case 'A': CHKPOS(2,2, 0, 0); break;
 173                                 case 'B': CHKPOS(2,2,+1, 0); break;
 174                                 case 'C': CHKPOS(2,2, 0,+1); break;
 175                                 case 'D': CHKPOS(2,2,+1,+1); break;
 176                                 case '+': goto failed;
 177                                 default:  assert(0);
 178                                 }
 179 #undef CHKPOS
 180
 181                         memcpy(nst,st,20);
 182                         for (yi=gy;yi<gy+gys;yi++) memset(nst+SaXYL(gx,yi),'+',gxs);
 183                         for (yi=gy;yi<gy+gys;yi++) memcpy(nst+SaXYL(gx-sx,yi-sy),st+SaXYL(gx,yi),gxs);
 184 #if 0
 185 /*ndef NDEBUG*/
 186                         printf("Moving: g=(%d,%d)[%d,%d] by (%d,%d)\n",gx,gy,gxs,gys,-sx,-sy);
 187                         dumpst(nst);
 188 #endif
 189                         addstate(nst,sts);
 190                         }
 191                 }
 192 }
 193
 194 static void swtogo(void)
 195 {
 196         assert(!togonow);
 197         togonow=togo;
 198         togo=NULL;
 199         togop=&togo;
 200         level++;
 201 }
 202
 203 int main(void)
 204 {
 205 struct st *now;
 206 #ifdef STSTEP
 207 unsigned ststep=0;
 208 #endif
 209
 210         addstate(init,NULL);
 211         while (togo) {
 212                 swtogo();
 213                 while ((now=togonow)) {
 214                         togonow=now->nexttogo;
 215                         trymoves(now);
 216 #ifdef STSTEP
 217                         gone++;
 218 #if 1
 219                         if (!(gone%STSTEP)) printf("%5u+%5u=%5u\n",gone,total-gone,total);
 220 #else
 221                         if (++ststep==STSTEP || !togo) {
 222                                 printf("%5u+%5u=%5u, level=%3d\n",gone,total-gone,total,level);
 223                                 ststep=0;
 224                                 }
 225 #endif
 226 #endif
 227                         }
 228                 }
 229 #if 0
 230         printf("total=%u, maxlevel=%d, solutions=%d\n",total,level,solutions);
 231 #endif
 232         return(EXIT_SUCCESS);
 233 }