![[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] / 42BSD / games / boggle|
Return to boggle.c CVS log | Up to [CSRG BSD Unix] / 42BSD / games / boggle |
1.1 root 1: #ifndef lint
2: static char sccsid[] = "@(#)boggle.c 4.1 12/24/82";
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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.