![[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] / 43BSD / games / boggle|
Return to boggle.c CVS log | Up to [CSRG BSD Unix] / 43BSD / 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.1 (Berkeley) 5/30/85";
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:
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");
194: printf("the first argument. The first + removes the restriction that positions\n");
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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.