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