1 /* written by Andrew Tridgell (May 1992) */
18 enum _Direction{ACROSS,DOWN};
19 typedef enum _Direction Direction;
24 #define LONG_STRING_LENGTH 200
32 #define randomize() srand(time(NULL))
34 #define BLACKSQUARE ' '
36 #define BLACKSQUARE 'Û'
39 /*******************************************************************
40 create a matrix of any dimension. The return must be cast correctly.
41 ********************************************************************/
42 void *any_matrix(va_alist)
49 int i,j,size,ptr_size,ppos,prod;
54 /* first gather the arguments */
56 dimension = va_arg(ap, int);
57 el_size = va_arg(ap, int);
60 if (dimension <= 0) return(NULL);
61 if (el_size <= 0) return(NULL);
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);
69 /* now we've disected the arguments we can go about the real business of
70 creating the matrix */
72 /* calculate how much space all the pointers will take up */
74 for (i=0;i<(dimension-1);i++)
77 for (j=0;j<=i;j++) prod *= dims[j];
81 /* padding overcomes potential alignment errors */
82 padding = (el_size - (ptr_size % el_size)) % el_size;
84 /* now calculate the total memory taken by the array */
87 for (i=0;i<dimension;i++) prod *= dims[i];
88 size = prod + ptr_size + padding;
91 /* allocate the matrix memory */
92 mat = (void **)malloc(size);
96 fprintf(stdout,"Error allocating %d dim matrix of size %d\n",dimension,size);
101 /* now fill in the pointer values */
102 next_ptr = (void *)&mat[dims[0]];
105 for (i=0;i<(dimension-1);i++)
108 if (i == dimension-2)
110 skip = el_size*dims[i+1];
111 next_ptr = (void *)(((char *)next_ptr) + padding); /* add in the padding */
114 skip = sizeof(void *)*dims[i+1];
116 for (j=0;j<(dims[i]*prod);j++)
118 mat[ppos++] = next_ptr;
119 next_ptr = (void *)(((char *)next_ptr) + skip);
129 /*******************************************************************
130 return a random number
131 ********************************************************************/
138 /*******************************************************************
139 this returns the number of lines in a text file
140 ********************************************************************/
141 int num_text_lines(CONST char *fname)
147 file = fopen(fname,"r");
153 read_a_line(buf,2000,file);
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)
166 my_fgets(buf,maxlen,file);
167 if (strlen(buf) == 0)
168 my_fgets(buf,maxlen,file);
171 /*******************************************************************
172 like fgets but remove trailing CR or LF
173 ********************************************************************/
174 char *my_fgets(char *s,int n,FILE *stream)
178 ret = fgets(s,n,stream);
185 return(strtidy(s,"\n\r "));
188 /*******************************************************************
189 remove specified chars from front and back of a string
190 ********************************************************************/
191 char *strtidy(char *str,CONST char *chars)
194 while ((len > 0) && (strchr(chars,*str) != NULL))
196 memcpy(str,&str[1],len);
199 while ((len > 0) && (strchr(chars,str[len-1]) != NULL))
210 /*******************************************************************
212 ********************************************************************/
213 char **load_word_list(char *fname,int *num)
217 char line[LONG_STRING_LENGTH];
219 *num = num_text_lines(fname);
223 list = (char **)malloc(sizeof(char *)*(*num));
225 file = fopen(fname,"r");
226 for (i=0;i<(*num);i++)
228 read_a_line(line,LONG_STRING_LENGTH,file);
229 list[i] = (char *)malloc(strlen(line)+1);
230 strcpy(list[i],line);
237 /*******************************************************************
239 ********************************************************************/
240 void PlaceWord(char *word,int i,int j,Direction dir)
243 int len=strlen(word);
247 grid[i+k][j] = word[k];
252 grid[i][j+k] = word[k];
256 /*******************************************************************
257 determine if a word is legal in a position
258 ********************************************************************/
259 BOOL Legal(char *word,int i,int j,Direction dir)
261 int len=strlen(word);
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);
269 if (grid[i+k][j] && (grid[i+k][j] != word[k])) return(False);
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);
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);
283 if (grid[i][j+k] && (grid[i][j+k] != word[k])) return(False);
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);
293 /*******************************************************************
294 score a word in a position
295 ********************************************************************/
296 int Score(char *word,int i,int j,Direction dir)
298 int len=strlen(word);
306 if ((k == 0) || (k == (len-1)))
311 if ((j != 0) && (j != (ysize-1))) score++;
319 if ((k == 0) || (k == (len-1)))
324 if ((i != 0) && (i != (xsize-1))) score++;
329 Direction last_dir=ACROSS;
332 /*******************************************************************
333 find the best position for a word
334 ********************************************************************/
335 BOOL BestPosition(char *word,int *besti,int *bestj,Direction *dir)
341 for (i=0;i<xsize;i++)
342 for (j=0;j<ysize;j++)
346 if (Legal(word,i,j,d))
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)))
359 if (Legal(word,i,j,d))
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)))
375 /*******************************************************************
377 ********************************************************************/
378 void zero_crossword(void)
381 for (i=0;i<xsize;i++)
382 for (j=0;j<ysize;j++)
387 /*******************************************************************
389 ********************************************************************/
390 int BuildCrossword(char **list,int num)
396 BOOL *used = (BOOL *)malloc(sizeof(BOOL)*num);
400 while (remaining > 0)
405 choose = random_num() % num;
406 if (used[choose]) choose=-1;
410 if (BestPosition(list[choose],&i,&j,&d))
411 PlaceWord(list[choose],i,j,d);
418 /*******************************************************************
420 ********************************************************************/
421 int BuildBestCrossword(char **list,int num)
427 BOOL *used = (BOOL *)malloc(sizeof(BOOL)*num);
428 int *scores = (int *)malloc(sizeof(int)*num);
434 while (remaining > 0)
441 if (!used[n] && BestPosition(list[n],&i,&j,&d))
442 scores[n] = Score(list[n],i,j,d);
444 int numbest=0,bestscore=scores[0];
448 if (scores[n] == bestscore) numbest++;
449 if (scores[n] > bestscore)
451 bestscore = scores[n];
455 if (bestscore < 0) return(num-remaining);
456 k = random_num() % numbest;
460 if (scores[n] == bestscore)
462 if (numbest == k) choose=n;
467 BestPosition(list[choose],&i,&j,&d);
468 PlaceWord(list[choose],i,j,d);
472 return(num-remaining);
475 /*******************************************************************
476 display the crossword
477 ********************************************************************/
478 void DisplayCrossword(FILE *f)
481 for (j=0;j<ysize;j++)
483 for (i=0;i<xsize;i++)
488 fputc(BLACKSQUARE,f);
496 /*******************************************************************
497 save the crossword in a pzl file
498 ********************************************************************/
499 void SavePuzzle(char *fname)
501 FILE *f = fopen(fname,"w");
505 fprintf(f,"%cXWORD0%s%c%c%2d%2d",42,"Sue2",3,3,xsize,ysize);
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);
515 /*******************************************************************
516 save the crossword in a .cwd file (for ccwin15.zip)
517 ********************************************************************/
518 void SaveCross(char *fname)
520 FILE *f = fopen(fname,"w");
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);
548 void copy_to(char **g)
551 for (i=0;i<xsize;i++)
552 for (j=0;j<ysize;j++)
553 g[i][j] = grid[i][j];
561 int main(int argc,char *argv[])
570 printf("angry: Xsize Ysize WordFile\n");
573 xsize = atoi(argv[1]);
574 ysize = atoi(argv[2]);
577 grid = (char **)any_matrix(2,sizeof(char),xsize,ysize);
578 bestgrid = (char **)any_matrix(2,sizeof(char),xsize,ysize);
579 if (!grid || !bestgrid)
581 printf("invalid xsize or ysize\n");
585 wordlist = load_word_list(wordfile,&num_words);
589 n = BuildBestCrossword(wordlist,num_words);
595 printf("\nplaced %d words\n",best);
597 FILE *f = fopen("best.doc","w");
598 DisplayCrossword(stdout);
600 SavePuzzle("best.pzl");
601 SaveCross("best.cwd");