angry.c

   1 /* written by Andrew Tridgell (May 1992) */
   2
   3
   4 #include <stdio.h>
   5 #include <malloc.h>
   6 #include <varargs.h>
   7 #include <stdlib.h>
   8 #include <time.h>
   9
  10 int xsize=0;
  11 int ysize=0;
  12
  13 char **grid;
  14 char *wordfile;
  15 char **wordlist=NULL;
  16 int num_words=0;
  17
  18 enum _Direction{ACROSS,DOWN};
  19 typedef enum _Direction Direction;
  20 typedef int BOOL;
  21 #define True 1
  22 #define False 0
  23 #define CONST const
  24 #define LONG_STRING_LENGTH 200
  25
  26 char *strtidy();
  27 void read_a_line();
  28 char *my_fgets();
  29
  30
  31 #ifndef MSDOS
  32 #define randomize() srand(time(NULL))
  33 #define ctrlbrk(fn)
  34 #define BLACKSQUARE ' '
  35 #else
  36 #define BLACKSQUARE 'Û'
  37 #endif
  38
  39 /*******************************************************************
  40 create a matrix of any dimension. The return must be cast correctly.
  41 ********************************************************************/
  42 void *any_matrix(va_alist)
  43 va_dcl
  44 {
  45 int dimension;
  46 int el_size;
  47 int *dims=NULL;
  48 void **mat;
  49 int i,j,size,ptr_size,ppos,prod;
  50 int padding;
  51 void *next_ptr;
  52 va_list ap;
  53
  54 /* first gather the arguments */
  55 va_start(ap);
  56 dimension = va_arg(ap, int);
  57 el_size = va_arg(ap, int);
  58
  59
  60 if (dimension <= 0) return(NULL);
  61 if (el_size <= 0) return(NULL);
  62
  63 dims = (int *)malloc(dimension * sizeof(int));
  64 if (dims == NULL) return(NULL);
  65 for (i=0;i<dimension;i++)
  66         dims[i] = va_arg(ap, int);
  67 va_end(ap);
  68
  69 /* now we've disected the arguments we can go about the real business of
  70 creating the matrix */
  71
  72 /* calculate how much space all the pointers will take up */
  73 ptr_size = 0;
  74 for (i=0;i<(dimension-1);i++)
  75         {
  76         prod=sizeof(void *);
  77         for (j=0;j<=i;j++) prod *= dims[j];
  78         ptr_size += prod;
  79         }
  80
  81 /* padding overcomes potential alignment errors */
  82 padding = (el_size - (ptr_size % el_size)) % el_size;
  83
  84 /* now calculate the total memory taken by the array */
  85 {
  86 prod=el_size;
  87 for (i=0;i<dimension;i++) prod *= dims[i];
  88 size = prod + ptr_size + padding;
  89 }
  90
  91 /* allocate the matrix memory */
  92 mat = (void **)malloc(size);
  93
  94 if (mat == NULL)
  95         {
  96         fprintf(stdout,"Error allocating %d dim matrix of size %d\n",dimension,size);
  97         free(dims);
  98         return(NULL);
  99         }
 100
 101 /* now fill in the pointer values */
 102 next_ptr = (void *)&mat[dims[0]];
 103 ppos = 0;
 104 prod = 1;
 105 for (i=0;i<(dimension-1);i++)
 106 {
 107 int skip;
 108 if (i == dimension-2)
 109   {
 110     skip = el_size*dims[i+1];
 111     next_ptr = (void *)(((char *)next_ptr) + padding); /* add in the padding */
 112   }
 113 else
 114   skip = sizeof(void *)*dims[i+1];
 115
 116 for (j=0;j<(dims[i]*prod);j++)
 117   {
 118     mat[ppos++] = next_ptr;
 119     next_ptr = (void *)(((char *)next_ptr) + skip);
 120   }
 121 prod *= dims[i];
 122 }
 123
 124 free(dims);
 125 return((void *)mat);
 126 }
 127
 128
 129 /*******************************************************************
 130 return a random number
 131 ********************************************************************/
 132 int random_num(void)
 133 {
 134 return(rand());
 135 }
 136
 137
 138 /*******************************************************************
 139 this returns the number of lines in a text file
 140 ********************************************************************/
 141 int num_text_lines(CONST char *fname)
 142 {
 143 FILE *file;
 144 int count = 0;
 145 char buf[2000];
 146
 147 file = fopen(fname,"r");
 148 if (!file)
 149   return(0);
 150
 151 while (!feof(file))
 152   {
 153     read_a_line(buf,2000,file);
 154     if (*buf) count++;
 155   }
 156
 157 fclose(file);
 158 return(count);
 159 }
 160
 161 /*******************************************************************
 162 read a line from a file. If the line is of 0 length then read another
 163 ********************************************************************/
 164 void read_a_line(char *buf,int maxlen,FILE *file)
 165 {
 166 my_fgets(buf,maxlen,file);
 167 if (strlen(buf) == 0)
 168         my_fgets(buf,maxlen,file);
 169 }
 170
 171 /*******************************************************************
 172 like fgets but remove trailing CR or LF
 173 ********************************************************************/
 174 char *my_fgets(char *s,int n,FILE *stream)
 175 {
 176 char *ret;
 177
 178 ret = fgets(s,n,stream);
 179 if (ret == NULL)
 180   {
 181     *s = 0;
 182     return(NULL);
 183   }
 184
 185 return(strtidy(s,"\n\r "));
 186 }
 187
 188 /*******************************************************************
 189 remove specified chars from front and back of a string
 190 ********************************************************************/
 191 char *strtidy(char *str,CONST char *chars)
 192 {
 193 int len=strlen(str);
 194 while ((len > 0) && (strchr(chars,*str) != NULL))
 195         {
 196         memcpy(str,&str[1],len);
 197         len--;
 198         }
 199 while ((len > 0) && (strchr(chars,str[len-1]) != NULL))
 200         {
 201         str[len-1]=0;
 202         len--;
 203         }
 204 return(str);
 205 }
 206
 207
 208
 209
 210 /*******************************************************************
 211 load a list of words
 212 ********************************************************************/
 213 char **load_word_list(char *fname,int *num)
 214 {
 215 FILE *file;
 216 int i;
 217 char line[LONG_STRING_LENGTH];
 218 char **list;
 219 *num = num_text_lines(fname);
 220 if (*num < 1)
 221   return(NULL);
 222
 223 list = (char **)malloc(sizeof(char *)*(*num));
 224
 225 file = fopen(fname,"r");
 226 for (i=0;i<(*num);i++)
 227   {
 228     read_a_line(line,LONG_STRING_LENGTH,file);
 229     list[i] = (char *)malloc(strlen(line)+1);
 230     strcpy(list[i],line);
 231   }
 232 fclose(file);
 233
 234 return(list);
 235 }
 236
 237 /*******************************************************************
 238 place a word
 239 ********************************************************************/
 240 void PlaceWord(char *word,int i,int j,Direction dir)
 241 {
 242 int k;
 243 int len=strlen(word);
 244 if (dir == ACROSS)
 245   {
 246     for (k=0;k<len;k++)
 247       grid[i+k][j] = word[k];
 248   }
 249 else
 250   {
 251     for (k=0;k<len;k++)
 252       grid[i][j+k] = word[k];
 253   }
 254 }
 255
 256 /*******************************************************************
 257 determine if a word is legal in a position
 258 ********************************************************************/
 259 BOOL Legal(char *word,int i,int j,Direction dir)
 260 {
 261 int len=strlen(word);
 262 if (dir == ACROSS)
 263   {
 264     int k;
 265     if (i+len > xsize) return(False);
 266     if ((i != 0) && grid[i-1][j]) return(False);
 267     if (((i+len) != xsize) && grid[i+len][j]) return(False);
 268     for (k=0;k<len;k++)
 269       if (grid[i+k][j] && (grid[i+k][j] != word[k])) return(False);
 270     for (k=0;k<len;k++)
 271       {
 272         if ((j != 0) && grid[i+k][j-1] && !grid[i+k][j]) return(False);
 273         if ((j != (ysize-1)) && grid[i+k][j+1] && !grid[i+k][j]) return(False);
 274       }
 275   }
 276 else
 277   {
 278     int k;
 279     if (j+len > ysize) return(False);
 280     if ((j != 0) && grid[i][j-1]) return(False);
 281     if (((j+len) != ysize) && grid[i][j+len]) return(False);
 282     for (k=0;k<len;k++)
 283       if (grid[i][j+k] && (grid[i][j+k] != word[k])) return(False);
 284     for (k=0;k<len;k++)
 285       {
 286         if ((i != 0) && grid[i-1][j+k] && !grid[i][j+k]) return(False);
 287         if ((i != (xsize-1)) && grid[i+1][j+k] && !grid[i][j+k]) return(False);
 288       }
 289   }
 290 return(True);
 291 }
 292
 293 /*******************************************************************
 294 score a word in a position
 295 ********************************************************************/
 296 int Score(char *word,int i,int j,Direction dir)
 297 {
 298 int len=strlen(word);
 299 int score=0;
 300 if (dir == ACROSS)
 301   {
 302     int k;
 303     for (k=0;k<len;k++)
 304       if (grid[i+k][j])
 305         {
 306           if ((k == 0) || (k == (len-1)))
 307             score += 2;
 308           else
 309             score += 3;
 310         }
 311     if ((j != 0) && (j != (ysize-1))) score++;
 312   }
 313 else
 314   {
 315     int k;
 316     for (k=0;k<len;k++)
 317       if (grid[i][j+k])
 318         {
 319           if ((k == 0) || (k == (len-1)))
 320             score += 4;
 321           else
 322             score += 6;
 323         }
 324     if ((i != 0) && (i != (xsize-1))) score++;
 325   }
 326 return(score);
 327 }
 328
 329 Direction last_dir=ACROSS;
 330
 331
 332 /*******************************************************************
 333 find the best position for a word
 334 ********************************************************************/
 335 BOOL BestPosition(char *word,int *besti,int *bestj,Direction *dir)
 336 {
 337 int best;
 338 int i,j;
 339 Direction d;
 340 best = -1;
 341 for (i=0;i<xsize;i++)
 342   for (j=0;j<ysize;j++)
 343     {
 344       int s;
 345       d = ACROSS;
 346       if (Legal(word,i,j,d))
 347         {
 348           s = Score(word,i,j,d);
 349           if (last_dir != d) s++;
 350           if (s > best || ((s == best) && ((random_num()%(xsize*ysize/4))!=0)))
 351             {
 352               best = s;
 353               *besti = i;
 354               *bestj = j;
 355               *dir = d;
 356             }
 357         }
 358       d = DOWN;
 359       if (Legal(word,i,j,d))
 360         {
 361           s = Score(word,i,j,d);
 362           if (last_dir != d) s++;
 363           if (s > best || ((s == best) && ((random_num()%(xsize*ysize/4))!=0)))
 364             {
 365               best = s;
 366               *besti = i;
 367               *bestj = j;
 368               *dir = d;
 369             }
 370         }
 371     }
 372 return(best >= 0);
 373 }
 374
 375 /*******************************************************************
 376 zero a crossword
 377 ********************************************************************/
 378 void zero_crossword(void)
 379 {
 380 int i,j;
 381 for (i=0;i<xsize;i++)
 382   for (j=0;j<ysize;j++)
 383     grid[i][j] = 0;
 384 }
 385
 386
 387 /*******************************************************************
 388 build a crossword
 389 ********************************************************************/
 390 int BuildCrossword(char **list,int num)
 391 {
 392 int i,j;
 393 Direction d;
 394 int remaining=num;
 395 int bad=0;
 396 BOOL *used = (BOOL *)malloc(sizeof(BOOL)*num);
 397 for (i=0;i<num;i++)
 398   used[i] = False;
 399 zero_crossword();
 400 while (remaining > 0)
 401   {
 402     int choose=-1;
 403     while (choose==-1)
 404       {
 405         choose = random_num() % num;
 406         if (used[choose]) choose=-1;
 407       }
 408     used[choose] = True;
 409     remaining--;
 410     if (BestPosition(list[choose],&i,&j,&d))
 411       PlaceWord(list[choose],i,j,d);
 412     else
 413       bad++;
 414   }
 415 return(num-bad);
 416 }
 417
 418 /*******************************************************************
 419 build a crossword
 420 ********************************************************************/
 421 int BuildBestCrossword(char **list,int num)
 422 {
 423 int i,j;
 424 Direction d;
 425 int remaining=num;
 426 int bad=0;
 427 BOOL *used = (BOOL *)malloc(sizeof(BOOL)*num);
 428 int *scores = (int *)malloc(sizeof(int)*num);
 429
 430 for (i=0;i<num;i++)
 431   used[i] = False;
 432
 433 zero_crossword();
 434 while (remaining > 0)
 435   {
 436     int n;
 437     int choose;
 438     for (i=0;i<num;i++)
 439       scores[i] = -1;
 440     for (n=0;n<num;n++)
 441       if (!used[n] && BestPosition(list[n],&i,&j,&d))
 442         scores[n] = Score(list[n],i,j,d);
 443     {
 444       int numbest=0,bestscore=scores[0];
 445       int k;
 446       for (n=0;n<num;n++)
 447         {
 448           if (scores[n] == bestscore) numbest++;
 449           if (scores[n] > bestscore)
 450             {
 451               bestscore = scores[n];
 452               numbest = 1;
 453             }
 454         }
 455       if (bestscore < 0) return(num-remaining);
 456       k = random_num() % numbest;
 457       numbest=0;
 458       for (n=0;n<num;n++)
 459         {
 460           if (scores[n] == bestscore)
 461             {
 462               if (numbest == k) choose=n;
 463               numbest++;
 464             }
 465         }
 466     }
 467     BestPosition(list[choose],&i,&j,&d);
 468     PlaceWord(list[choose],i,j,d);
 469     used[choose] = True;
 470     remaining--;
 471   }
 472 return(num-remaining);
 473 }
 474
 475 /*******************************************************************
 476 display the crossword
 477 ********************************************************************/
 478 void DisplayCrossword(FILE *f)
 479 {
 480 int i,j;
 481 for (j=0;j<ysize;j++)
 482   {
 483     for (i=0;i<xsize;i++)
 484       {
 485         if (grid[i][j])
 486           fputc(grid[i][j],f);
 487         else
 488           fputc(BLACKSQUARE,f);
 489       }
 490     fputc('\n',f);
 491   }
 492 putchar('\n');
 493 }
 494
 495
 496 /*******************************************************************
 497 save the crossword in a pzl file
 498 ********************************************************************/
 499 void SavePuzzle(char *fname)
 500 {
 501 FILE *f = fopen(fname,"w");
 502 int i,j;
 503 if (!f) return;
 504
 505 fprintf(f,"%cXWORD0%s%c%c%2d%2d",42,"Sue2",3,3,xsize,ysize);
 506
 507 for (j=0;j<ysize;j++)
 508     for (i=0;i<xsize;i++)
 509       fprintf(f,"%c %c",(grid[i][j]?grid[i][j]:' '),3);
 510
 511 fclose(f);
 512 }
 513
 514
 515 /*******************************************************************
 516 save the crossword in a .cwd file (for ccwin15.zip)
 517 ********************************************************************/
 518 void SaveCross(char *fname)
 519 {
 520 FILE *f = fopen(fname,"w");
 521 int i,j;
 522 char head[10];
 523
 524 if (!f) return;
 525
 526 memset(head,0,10);
 527 head[0] = 'j';
 528 head[4] = '\n';
 529 head[6] = 1;
 530 head[8] = xsize;
 531 head[9] = ysize;
 532
 533 fwrite(head,1,10,f);
 534
 535 for (j=0;j<ysize;j++)
 536   for (i=0;i<xsize;i++)
 537     fprintf(f,"%c",grid[i][j]?(char)toupper(grid[i][j]):0333);
 538
 539 head[0] = 0;
 540 head[1] = 0;
 541
 542 fwrite(head,1,2,f);
 543
 544 fclose(f);
 545 }
 546
 547
 548 void copy_to(char **g)
 549 {
 550 int i,j;
 551 for (i=0;i<xsize;i++)
 552 for (j=0;j<ysize;j++)
 553         g[i][j] = grid[i][j];
 554 }
 555
 556 int cbreak(void)
 557 {
 558 return(0);
 559 }
 560
 561 int main(int argc,char *argv[])
 562 {
 563 char **bestgrid;
 564 int best=-1;
 565 ctrlbrk(cbreak);
 566
 567 randomize();
 568 if (argc < 4)
 569   {
 570     printf("angry: Xsize Ysize WordFile\n");
 571     return(0);
 572   }
 573 xsize = atoi(argv[1]);
 574 ysize = atoi(argv[2]);
 575 wordfile = argv[3];
 576
 577 grid = (char **)any_matrix(2,sizeof(char),xsize,ysize);
 578 bestgrid = (char **)any_matrix(2,sizeof(char),xsize,ysize);
 579 if (!grid || !bestgrid)
 580   {
 581     printf("invalid xsize or ysize\n");
 582     return(0);
 583   }
 584
 585 wordlist = load_word_list(wordfile,&num_words);
 586 while (True)
 587   {
 588   int n;
 589     n = BuildBestCrossword(wordlist,num_words);
 590     putchar('.');
 591     if (n > best)
 592         {
 593         best = n;
 594         copy_to(bestgrid);
 595         printf("\nplaced %d words\n",best);
 596         {
 597         FILE *f = fopen("best.doc","w");
 598         DisplayCrossword(stdout);
 599         DisplayCrossword(f);
 600         SavePuzzle("best.pzl");
 601         SaveCross("best.cwd");
 602         fclose(f);
 603         }
 604         }
 605     fflush(stdout);
 606   }
 607 }