Commit | Line | Data |
---|---|---|
4dba9a68 SL |
1 | #ifndef lint |
2 | static char sccsid[] = "@(#)boggle.c 4.1 %G%"; | |
3 | #endif | |
4 | ||
5 | #include <ctype.h> | |
6 | #include <errno.h> | |
7 | #include <setjmp.h> | |
8 | #include <sgtty.h> | |
9 | #include <signal.h> | |
10 | #include <stdio.h> | |
11 | ||
12 | /* basic parameters */ | |
13 | #define N 4 | |
14 | #define SSIZE 200 | |
15 | #define MAXWORDS 1000 | |
16 | #define CWIDTH 10 | |
17 | #define LWIDTH 80 | |
18 | ||
19 | /* parameters defined in terms of above */ | |
20 | #define BSIZE (N*N) | |
21 | #define row(x) (x/N) | |
22 | #define col(x) (x%N) | |
23 | ||
24 | /* word being searched for */ | |
25 | int wlength; | |
26 | int numsame; | |
27 | char wbuff [BSIZE+1]; | |
28 | ||
29 | /* tty and process control */ | |
30 | extern int errno; | |
31 | int status; | |
32 | int pipefd[2]; | |
33 | int super = 0; | |
34 | int delct = 1; | |
35 | int zero = 0; | |
36 | int master = 1; | |
37 | int column; | |
38 | int *timept; | |
39 | int timeint[] = {60,60,50,7,1,1,1,0}; | |
40 | long timein; | |
41 | extern long int time(); | |
42 | struct sgttyb origttyb, tempttyb; | |
43 | int ctlecho = 0; | |
44 | int lctlech = LCTLECH; | |
45 | jmp_buf env; | |
46 | ||
47 | /* monitoring variables */ | |
48 | int games; | |
49 | int logfile = -1; | |
50 | long logloc; | |
51 | char logbuff[100] = {"inst\t"}; | |
52 | extern char *ctime(), *getlogin(); | |
53 | extern long lseek(); | |
54 | ||
55 | /* dictionary interface */ | |
56 | char defname[] = "/usr/games/bogdict"; | |
57 | char *dictname = &defname[0]; | |
58 | FILE *dict; | |
59 | ||
60 | /* structures for doing matching */ | |
61 | struct frame { | |
62 | struct frame *parent; | |
63 | int place; | |
64 | }; | |
65 | struct frame stack [SSIZE]; | |
66 | struct frame *level [BSIZE+1]; | |
67 | ||
68 | /* the board and subsidiary structures */ | |
69 | char present [BSIZE+1]; | |
70 | char board [BSIZE]; | |
71 | char olink [BSIZE]; | |
72 | char adj [BSIZE+1][BSIZE]; | |
73 | char occurs [26]; | |
74 | ||
75 | /* the boggle cubes */ | |
76 | char *cube [BSIZE] = { | |
77 | "forixb", "moqabj", "gurilw", "setupl", | |
78 | "cmpdae", "acitao", "slcrae", "romash", | |
79 | "nodesw", "hefiye", "onudtk", "tevign", | |
80 | "anedvz", "pinesh", "abilyt", "gkyleu" | |
81 | }; | |
82 | ||
83 | ||
84 | /* storage for words found */ | |
85 | int ubotch, ustart, wcount; | |
86 | char *word [MAXWORDS]; | |
87 | char *freesp; | |
88 | char space[10000]; | |
89 | ||
90 | endline () | |
91 | { | |
92 | if (column != 0) { | |
93 | putchar('\n'); | |
94 | column = 0; | |
95 | } | |
96 | } | |
97 | ||
98 | timeout () | |
99 | { | |
100 | if (*timept > 0) { | |
101 | signal (SIGALRM, timeout); | |
102 | alarm(*timept++); | |
103 | } | |
104 | putchar('\007'); | |
105 | } | |
106 | ||
107 | interrupt () | |
108 | { | |
109 | signal(SIGINT, interrupt); | |
110 | if (delct++ >= 1) | |
111 | longjmp(env, 1); | |
112 | timept = &zero; | |
113 | } | |
114 | ||
115 | goodbye (stat) | |
116 | int stat; | |
117 | { | |
118 | if (master != 0) { | |
119 | wait(&status); | |
120 | if ( ctlecho & LCTLECH ) { | |
121 | ioctl( fileno(stdin), TIOCLBIS, &lctlech ); | |
122 | } | |
123 | stty(fileno(stdin), &origttyb); | |
124 | } | |
125 | exit(stat); | |
126 | } | |
127 | ||
128 | clearscreen () | |
129 | { | |
130 | stty (fileno(stdin), &tempttyb); | |
131 | printf("\n\033\f\r"); | |
132 | } | |
133 | ||
134 | compare (a, b) | |
135 | char **a, **b; | |
136 | { | |
137 | return(wordcomp(*a, *b)); | |
138 | } | |
139 | ||
140 | wordcomp (p, q) | |
141 | register char *p, *q; | |
142 | { | |
143 | if (*p=='0' && *q!='0') | |
144 | return(-1); | |
145 | if (*p!='0' && *q=='0') | |
146 | return(1); | |
147 | while (*++p == *++q && isalpha(*p)) ; | |
148 | if (!isalpha(*p)) | |
149 | return(-isalpha(*q)); | |
150 | if (!isalpha(*q)) | |
151 | return(1); | |
152 | return(*p-*q); | |
153 | } | |
154 | ||
155 | printinst () | |
156 | { | |
157 | stty (fileno(stdin), &tempttyb); | |
158 | printf("instructions?"); | |
159 | if (getchar() == 'y') { | |
160 | clearscreen(); | |
161 | printf(" The object of Boggle (TM Parker Bros.) is to find, within 3\n"); | |
162 | printf("minutes, as many words as possible in a 4 by 4 grid of letters. Words\n"); | |
163 | printf("may be formed from any sequence of 3 or more adjacent letters in the\n"); | |
164 | printf("grid. The letters may join horizontally, vertically, or diagonally.\n"); | |
165 | printf("However, no position in the grid may be used more than once within any\n"); | |
166 | printf("one word. In competitive play amongst humans, each player is given\n"); | |
167 | printf("credit for those of his words which no other player has found.\n"); | |
168 | printf(" This program is intended for people wishing to sharpen their\n"); | |
169 | printf("skills at Boggle. If you invoke the program with 4 arguments of 4\n"); | |
170 | printf("letters each, (e.g. \"boggle appl epie moth erhd\") the program forms the\n"); | |
171 | printf("obvious Boggle grid and lists all the words from /usr/dict/words found\n"); | |
172 | printf("therein. If you invoke the program without arguments, it will generate\n"); | |
173 | printf("a board for you, let you enter words for 3 minutes, and then tell you\n"); | |
174 | printf("how well you did relative to /usr/dict/words.\n"); | |
175 | printf(" In interactive play, enter your words separated by spaces, tabs,\n"); | |
176 | printf("or newlines. A bell will ring when there is 2:00, 1:00, 0:10, 0:02,\n"); | |
177 | printf("0:01, and 0:00 time left. You may complete any word started before the\n"); | |
178 | printf("expiration of time. You can surrender before time is up by hitting\n"); | |
179 | printf("'break'. While entering words, your erase character is only effective\n"); | |
180 | printf("within the current word and your line kill character is ignored.\n"); | |
181 | printf(" Advanced players may wish to invoke the program with 1 or 2 +'s as\n"); | |
182 | printf("the first argument. The first + removes the restriction that postions\n"); | |
183 | printf("can only be used once in each word. The second + causes a position to\n"); | |
184 | printf("be considered adjacent to itself as well as its (up to) 8 neighbors.\n"); | |
185 | printf("Hit any key to begin.\n"); | |
186 | stty (fileno(stdin), &tempttyb); | |
187 | getchar(); | |
188 | } | |
189 | stty (fileno(stdin), &tempttyb); | |
190 | } | |
191 | ||
192 | setup () | |
193 | { | |
194 | register int i, j; | |
195 | int rd, cd, k; | |
196 | for (i=0; i<BSIZE; i++) { | |
197 | adj[i][i] = super>=2 ? 1 : 0; | |
198 | adj[BSIZE][i] = 1; | |
199 | for (j=0; j<i; j++) { | |
200 | rd = row(i)-row(j); | |
201 | cd = col(i)-col(j); | |
202 | k = 0; | |
203 | switch (rd) { | |
204 | case -1: | |
205 | case 1: | |
206 | if (-1<=cd && cd<=1) | |
207 | k = 1; | |
208 | break; | |
209 | case 0: | |
210 | if (cd==-1 || cd==1) | |
211 | k = 1; | |
212 | break; | |
213 | } | |
214 | adj[i][j] = adj[j][i] = k; | |
215 | } | |
216 | } | |
217 | stack[0].parent = &stack[0]; | |
218 | stack[0].place = BSIZE; | |
219 | level[0] = &stack[0]; | |
220 | level[1] = &stack[1]; | |
221 | } | |
222 | ||
223 | makelists () | |
224 | { | |
225 | register int i, c; | |
226 | for (i=0; i<26; i++) | |
227 | occurs[i] = BSIZE; | |
228 | for (i=0; i<BSIZE; i++) { | |
229 | c = board[i]; | |
230 | olink[i] = occurs[c-'a']; | |
231 | occurs[c-'a'] = i; | |
232 | } | |
233 | } | |
234 | ||
235 | genboard () | |
236 | { | |
237 | register int i, j; | |
238 | for (i=0; i<BSIZE; i++) | |
239 | board[i] = 0; | |
240 | for (i=0; i<BSIZE; i++) { | |
241 | j = rand()%BSIZE; | |
242 | while (board[j] != 0) | |
243 | j = (j+1)%BSIZE; | |
244 | board[j] = cube[i][rand()%6]; | |
245 | } | |
246 | } | |
247 | ||
248 | printboard () | |
249 | { | |
250 | register int i, j; | |
251 | for (i=0; i<N; i++) { | |
252 | printf("\t\t\t\t\b\b"); | |
253 | for (j=0; j<N; j++) { | |
254 | putchar ((putchar(board[i*N+j]) == 'q') ? 'u' : ' '); | |
255 | putchar(' '); | |
256 | } | |
257 | putchar('\n'); | |
258 | } | |
259 | putchar('\n'); | |
260 | } | |
261 | ||
262 | getdword () | |
263 | { | |
264 | /* input: numsame = # chars same as last word */ | |
265 | /* output: numsame = # same chars for next word */ | |
266 | /* word in wbuff[0]...wbuff[wlength-1] */ | |
267 | register int c; | |
268 | register char *p; | |
269 | if (numsame == EOF) | |
270 | return (0); | |
271 | p = &wbuff[numsame]+1; | |
272 | while ((*p++ = c = getc(dict)) != EOF && isalpha(c)) ; | |
273 | numsame = c; | |
274 | wlength = p - &wbuff[2]; | |
275 | return (1); | |
276 | } | |
277 | ||
278 | getuword () | |
279 | { | |
280 | int c; | |
281 | register char *p, *q, *r; | |
282 | numsame = 0; | |
283 | while (*timept>0 && (isspace(c=getchar()) || c==EOF)); | |
284 | if (*timept == 0) | |
285 | return(0); | |
286 | word[wcount++] = freesp; | |
287 | *freesp++ = '0'; | |
288 | r = &wbuff[1]; | |
289 | q = p = freesp; | |
290 | *p++ = c; | |
291 | while (!isspace(c = getchar())) { | |
292 | if (c == EOF) | |
293 | continue; | |
294 | if (c == origttyb.sg_erase) { | |
295 | if (p > q) | |
296 | p--; | |
297 | continue; | |
298 | } | |
299 | *p++ = c; | |
300 | } | |
301 | freesp = p; | |
302 | for (p=q; p<freesp && r<&wbuff[BSIZE]; ) | |
303 | if (islower(c = *p++) && (*r++ = *q++ = c) == 'q' && *p == 'u') | |
304 | p++; | |
305 | *(freesp = q) = '0'; | |
306 | wlength = r-&wbuff[1]; | |
307 | return(1); | |
308 | } | |
309 | ||
310 | aputuword (ways) | |
311 | int ways; | |
312 | { | |
313 | *word[wcount-1] = ways>=10 ? '*' : '0'+ways; | |
314 | } | |
315 | ||
316 | aputword (ways) | |
317 | int ways; | |
318 | { | |
319 | /* store (wbuff, ways) in next slot in space */ | |
320 | register int i; | |
321 | *freesp++ = ways>=10 ? '*' : '0'+ways; | |
322 | for (i=1; i<= wlength; i++) | |
323 | *freesp++ = wbuff[i]; | |
324 | word[++wcount] = freesp; | |
325 | } | |
326 | ||
327 | tputword (ways) | |
328 | int ways; | |
329 | { | |
330 | /* print (wbuff, ways) on terminal */ | |
331 | wbuff[wlength+1] = '0'; | |
332 | wbuff[0] = ways>=10 ? '*' : '0'+ways; | |
333 | outword(&wbuff[0]); | |
334 | } | |
335 | ||
336 | outword (p) | |
337 | register char *p; | |
338 | { | |
339 | register int newcol; | |
340 | register char *q; | |
341 | for (q=p+1; isalpha(*q); ) { | |
342 | putchar(*q); | |
343 | if (*q++ == 'q') { | |
344 | putchar('u'); | |
345 | column++; | |
346 | } | |
347 | } | |
348 | column += q-p-1; | |
349 | if (column > LWIDTH-CWIDTH) { | |
350 | putchar('\n'); | |
351 | column = 0; | |
352 | return; | |
353 | } | |
354 | newcol = ((column+CWIDTH)/CWIDTH)*CWIDTH; | |
355 | while (((column+8)/8)*8 <= newcol) { | |
356 | putchar('\t'); | |
357 | column = ((column+8)/8)*8; | |
358 | } | |
359 | while (column < newcol) { | |
360 | putchar(' '); | |
361 | column++; | |
362 | } | |
363 | } | |
364 | ||
365 | printdiff () | |
366 | { | |
367 | register int c, d, u; | |
368 | char both, donly, uonly; | |
369 | word[wcount] = freesp; | |
370 | *freesp = '0'; | |
371 | both = donly = uonly = column = d = 0; | |
372 | u = ustart; | |
373 | while (d < ubotch) { | |
374 | c = u<wcount ? wordcomp (word[d], word[u]) : -1; | |
375 | if (c == 0) { | |
376 | /* dict and user found same word */ | |
377 | if (both == 0) { | |
378 | both = 1; | |
379 | printf("\t\t\t we both found:\n"); | |
380 | } | |
381 | outword(word[d]); | |
382 | word[d++] = NULL; | |
383 | word[u++] = NULL; | |
384 | } else if (c < 0) { | |
385 | /* dict found it, user didn't */ | |
386 | donly = 1; | |
387 | d++; | |
388 | } else { | |
389 | /* user found it, dict didn't */ | |
390 | uonly = 1; | |
391 | u++; | |
392 | } | |
393 | } | |
394 | endline(); | |
395 | if (donly) { | |
396 | printf("\n\t\t\tI alone found these:\n"); | |
397 | for (d=0; d<ubotch; d++) | |
398 | if (word[d] != NULL) | |
399 | outword(word[d]); | |
400 | endline(); | |
401 | } | |
402 | if (uonly) { | |
403 | printf("\n\t\t\tyou alone found these:\n"); | |
404 | for (u=ustart; u<wcount; u++) | |
405 | if (word[u] != NULL) | |
406 | outword(word[u]); | |
407 | endline(); | |
408 | } | |
409 | if (ubotch < ustart) { | |
410 | printf("\n\t\t\t you botched these:\n"); | |
411 | for (u=ubotch; u<ustart; u++) | |
412 | outword(word[u]); | |
413 | endline(); | |
414 | } | |
415 | } | |
416 | ||
417 | numways (leaf, last) | |
418 | register struct frame *leaf; | |
419 | struct frame *last; | |
420 | { | |
421 | int count; | |
422 | register char *p; | |
423 | register struct frame *node; | |
424 | if (super > 0) | |
425 | return(last-leaf); | |
426 | count = 0; | |
427 | present[BSIZE] = 1; | |
428 | while (leaf < last) { | |
429 | for (p = &present[0]; p < &present[BSIZE]; *p++ = 0); | |
430 | for (node = leaf; present[node->place]++ == 0; node = node->parent); | |
431 | if (node == &stack[0]) | |
432 | count++; | |
433 | leaf++; | |
434 | } | |
435 | return(count); | |
436 | } | |
437 | ||
438 | evalboard (getword, putword) | |
439 | int (*getword)(), (*putword)(); | |
440 | { | |
441 | register struct frame *top; | |
442 | register int l, q; | |
443 | int fo, found; | |
444 | struct frame *parent, *lastparent; | |
445 | char *padj; | |
446 | ||
447 | numsame = found = 0; | |
448 | makelists (); | |
449 | ||
450 | while (1) { | |
451 | l = numsame; | |
452 | if (!(*getword) ()) | |
453 | break; | |
454 | top = level[l+1]; | |
455 | ||
456 | while (1) { | |
457 | level[l+1] = lastparent = top; | |
458 | /* wbuff[1]...wbuff[l] have been matched */ | |
459 | /* level[0],...,level[l] of tree built */ | |
460 | if (l == wlength) { | |
461 | if (wlength >= 3 && (q = numways(level[l], top)) != 0) { | |
462 | (*putword) (q); | |
463 | found++; | |
464 | } | |
465 | l = BSIZE+1; | |
466 | break; | |
467 | } | |
468 | if ((fo = occurs[wbuff[++l]-'a']) == BSIZE) | |
469 | break; | |
470 | /* wbuff[1]...wbuff[l-1] have been matched */ | |
471 | /* level[0],...,level[l-1] of tree built */ | |
472 | for (parent=level[l-1]; parent<lastparent; parent++) { | |
473 | padj = &adj[parent->place][0]; | |
474 | for (q=fo; q!=BSIZE; q=olink[q]) | |
475 | if (padj[q]) { | |
476 | top->parent = parent; | |
477 | top->place = q; | |
478 | if (++top >= &stack[SSIZE]) { | |
479 | printf("stack overflow\n"); | |
480 | goodbye(1); | |
481 | } | |
482 | } | |
483 | } | |
484 | /* were any nodes added? */ | |
485 | if (top == lastparent) | |
486 | break; | |
487 | } | |
488 | ||
489 | /* advance until first l characters of next word are different */ | |
490 | while (numsame >= l && (*getword)()) ; | |
491 | } | |
492 | return(found); | |
493 | } | |
494 | ||
495 | main (argc, argv) | |
496 | int argc; | |
497 | char **argv; | |
498 | { | |
499 | char *q; | |
500 | register char *p; | |
501 | register int i, c; | |
502 | ||
503 | gtty (fileno(stdin), &origttyb); | |
504 | setbuf(stdin, NULL); | |
505 | tempttyb = origttyb; | |
506 | if (setjmp(env) != 0) | |
507 | goodbye(0); | |
508 | signal (SIGINT, interrupt); | |
509 | timein = time(0L); | |
510 | if (argv[0][0] != 'a' && (logfile = open("/usr/games/boglog", 1)) >= 0) { | |
511 | p = &logbuff[5]; | |
512 | q = getlogin(); | |
513 | while (*p++ = *q++); | |
514 | p[-1] = '\t'; | |
515 | q = ctime(&timein); | |
516 | while (*p++ = *q++); | |
517 | logloc = lseek(logfile, 0L, 2); | |
518 | write(logfile, &logbuff[0], p-&logbuff[1]); | |
519 | } | |
520 | if ((dict = fopen(dictname, "r")) == NULL) { | |
521 | printf("can't open %s\n", dictname); | |
522 | goodbye (2); | |
523 | } | |
524 | while ( argc > 1 && ( argv[1][0] == '+' || argv[1][0] == '-' ) ) { | |
525 | if (argv[1][0]=='+') { | |
526 | while(*(argv[1]++) == '+') | |
527 | super++; | |
528 | argc--; | |
529 | argv++; | |
530 | } | |
531 | if ( argv[1][0] == '-' ) { | |
532 | timeint[0] = 60 * ( atol( &argv[1][1] ) - 2 ); | |
533 | if ( timeint[0] <= 0 ) { | |
534 | timeint[0] = 60; | |
535 | } | |
536 | argc--; | |
537 | argv++; | |
538 | } | |
539 | } | |
540 | setup (); | |
541 | switch (argc) { | |
542 | default: punt: | |
543 | printf("usage: boggle [+[+]] [row1 row2 row3 row4]\n"); | |
544 | goodbye (3); | |
545 | case 5: | |
546 | for (i=0; i<BSIZE; i++) { | |
547 | board[i] = c = argv[row(i)+1][col(i)]; | |
548 | if (!islower(c)) { | |
549 | printf("bad board\n"); | |
550 | goto punt; | |
551 | } | |
552 | } | |
553 | printboard(); | |
554 | column = 0; | |
555 | evalboard(getdword, tputword); | |
556 | endline(); | |
557 | if (logfile >= 0) { | |
558 | strncpy(&logbuff[0], "eval", 4); | |
559 | lseek(logfile, logloc, 0); | |
560 | write(logfile, &logbuff[0], 4); | |
561 | } | |
562 | goodbye(0); | |
563 | case 1: | |
564 | tempttyb.sg_flags |= CBREAK; | |
565 | if ( ioctl( fileno(stdin), TIOCLGET, &ctlecho ) == 0 ) { | |
566 | if ( ctlecho & LCTLECH ) { | |
567 | ioctl( fileno(stdin), TIOCLBIC, &lctlech ); | |
568 | } | |
569 | } | |
570 | printinst(); | |
571 | srand((int) timein); | |
572 | while (setjmp(env) == 0) { | |
573 | errno = 0; | |
574 | if (pipe(&pipefd[0]) != 0) { | |
575 | printf("can't create pipe\n"); | |
576 | goodbye(4); | |
577 | } | |
578 | genboard(); | |
579 | delct = wcount = 0; | |
580 | word[0] = freesp = &space[0]; | |
581 | if ((master = fork()) == 0) { | |
582 | close(pipefd[0]); | |
583 | clearscreen(); | |
584 | printboard(); | |
585 | signal(SIGALRM, timeout); | |
586 | timept = &timeint[0]; | |
587 | alarm(*timept++); | |
588 | evalboard(getuword, aputuword); | |
589 | clearscreen(); | |
590 | qsort(&word[0], wcount, sizeof (int), compare); | |
591 | for (i=0; i<wcount; i++) | |
592 | if (i==0 || wordcomp(word[i], word[i-1])!=0) { | |
593 | p = word[i]; | |
594 | while (isalpha(*++p)) ; | |
595 | write (pipefd[1], word[i], p-word[i]); | |
596 | } | |
597 | close(pipefd[1]); | |
598 | goodbye(0); | |
599 | } | |
600 | close(pipefd[1]); | |
601 | rewind(dict); | |
602 | getc(dict); | |
603 | evalboard(getdword, aputword); | |
604 | p = freesp; | |
605 | while ((i = read(pipefd[0], freesp, 512)) != 0) { | |
606 | if (i < 0) | |
607 | if (errno != EINTR) | |
608 | break; | |
609 | else | |
610 | i = 0; | |
611 | freesp += i; | |
612 | } | |
613 | close(pipefd[0]); | |
614 | ustart = ubotch = wcount; | |
615 | while (p < freesp) { | |
616 | word[wcount++] = p; | |
617 | if (*p == '0') | |
618 | ustart = wcount; | |
619 | while (isalpha(*++p)); | |
620 | } | |
621 | wait(&status); | |
622 | if (status != 0) | |
623 | goodbye (5); | |
624 | delct = 1; | |
625 | printdiff(); | |
626 | printboard(); | |
627 | games++; | |
628 | if (logfile >= 0) { | |
629 | sprintf(&logbuff[0], "%4d", games); | |
630 | lseek(logfile, logloc, 0); | |
631 | write(logfile, &logbuff[0], 4); | |
632 | } | |
633 | stty (fileno(stdin), &tempttyb); | |
634 | printf("\nanother game?"); | |
635 | if (getchar() != 'y') { | |
636 | putchar('\n'); | |
637 | break; | |
638 | } | |
639 | stty (fileno(stdin), &tempttyb); | |
640 | } | |
641 | goodbye(0); | |
642 | } | |
643 | } |