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