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