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