xref: /original-bsd/games/boggle/boggle/bog.c (revision e0a151eb) 
1 /* vi: set tabstop=4 : */
2 
3 /*
4  * bog - the game of boggle
5  *
6  * 6-Mar-89     changed loaddict() to use a large buffer and check for overflow,
7  *              minor cleanup
8  */
9 
10 #include "bog.h"
11 
12 #include <ctype.h>
13 #include <stdio.h>
14 
15 char *version = "bog V1.3 brachman@ubc.csnet 6-Mar-89";
16 
17 struct dictindex dictindex[26];
18 
19 /*
20  * Cube position numbering:
21  *
22  *	0 1 2 3
23  *	4 5 6 7
24  *	8 9 A B
25  *	C D E F
26  */
27 static int adjacency[16][16] = {
28 /*    0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F */
29 	{ 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },		/* 0 */
30 	{ 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },		/* 1 */
31 	{ 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },		/* 2 */
32 	{ 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },		/* 3 */
33 	{ 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0 },		/* 4 */
34 	{ 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0 },		/* 5 */
35 	{ 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0 },		/* 6 */
36 	{ 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0 },		/* 7 */
37 	{ 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0 },		/* 8 */
38 	{ 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0 },		/* 9 */
39 	{ 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1 },		/* A */
40 	{ 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1 },		/* B */
41 	{ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0 },		/* C */
42 	{ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0 },		/* D */
43 	{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1 },		/* E */
44 	{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0 }		/* F */
45 };
46 
47 static int letter_map[26][16];
48 
49 char board[17];
50 int wordpath[MAXWORDLEN + 1];
51 int wordlen;		/* Length of last word returned by nextword() */
52 int usedbits;
53 
54 char *pword[MAXPWORDS], pwords[MAXPSPACE], *pwordsp;
55 int npwords;
56 
57 char *mword[MAXMWORDS], mwords[MAXMSPACE], *mwordsp;
58 int nmwords;
59 
60 int ngames = 0;
61 int tnmwords = 0, tnpwords = 0;
62 
63 #ifdef TIMER
64 #include <setjmp.h>
65 
66 jmp_buf env;
67 #endif TIMER
68 
69 long start_t;
70 
71 static FILE *dictfp = (FILE *) NULL;
72 
73 int batch;
74 int debug;
75 int minlength;
76 int reuse;
77 int tlimit;
78 
79 char *batchword(), *getline();
80 
81 long atol();
82 long random();
83 
84 main(argc, argv)
85 int argc;
86 char **argv;
87 {
88 	int done, i, selfuse, sflag;
89 	char *bspec, *p;
90 	long seed;
91 	FILE *opendict();
92 
93 	debug = 0;
94 	bspec = (char *) NULL;
95 	reuse = 0;
96 	batch = 0;
97 	selfuse = 0;
98 	minlength = 3;
99 	tlimit = 180;		/* 3 minutes is standard */
100 	sflag = 0;
101 
102 	for (i = 1; i < argc; i++) {
103 		if (argv[i][0] == '-') {
104 			switch (argv[i][1]) {
105 			case 'b':
106 				batch = 1;
107 				break;
108 			case 'd':
109 				debug = 1;
110 				break;
111 			case 's':
112 				sflag = 1;
113 				seed = atol(&argv[i][2]);
114 				break;
115 			case 't':
116 				if ((tlimit = atoi(&argv[i][2])) < 1) {
117 					(void) fprintf(stderr, "Bad time limit\n");
118 					exit(1);
119 				}
120 				break;
121 			case 'w':
122 				if ((minlength = atoi(&argv[i][2])) < 3) {
123 					(void) fprintf(stderr, "Min word length must be > 2\n");
124 					exit(1);
125 				}
126 				break;
127 			default:
128 				usage();
129 				/*NOTREACHED*/
130 			}
131 		}
132 		else if (strcmp(argv[i], "+") == 0)
133 			reuse = 1;
134 		else if (strcmp(argv[i], "++") == 0)
135 			selfuse = 1;
136 		else if (islower(argv[i][0])) {
137 			if (strlen(argv[i]) != 16) {
138 				usage();
139 				/*NOTREACHED*/
140 			}
141 			/* This board is assumed to be valid... */
142 			bspec = argv[i];
143 		}
144 		else {
145 			usage();
146 			/*NOREACHED*/
147 		}
148 	}
149 
150 	if (batch && bspec == (char *) NULL) {
151 		(void) fprintf(stderr, "Must give both -b and a board setup\n");
152 		exit(1);
153 	}
154 
155 	if (selfuse) {
156 		for (i = 0; i < 16; i++)
157 			adjacency[i][i] = 1;
158 	}
159 
160 	if (batch) {
161 		newgame(bspec);
162 		while ((p = batchword(stdin)) != (char *) NULL)
163 			(void) printf("%s\n", p);
164 	}
165 	else {
166 		setup(sflag, seed);
167 		prompt("Loading the dictionary...");
168 		if ((dictfp = opendict(DICT)) == (FILE *) NULL) {
169 			(void) fprintf(stderr, "Can't load %s\n", DICT);
170 			cleanup();
171 			exit(1);
172 		}
173 #ifdef LOADDICT
174 		if (loaddict(dictfp) < 0) {
175 			(void) fprintf(stderr, "Can't load %s\n", DICT);
176 			cleanup();
177 			exit(1);
178 		}
179 		(void) fclose(dictfp);
180 		dictfp = (FILE *) NULL;
181 #endif
182 		if (loadindex(DICTINDEX) < 0) {
183 			(void) fprintf(stderr, "Can't load %s\n", DICTINDEX);
184 			cleanup();
185 			exit(1);
186 		}
187 
188 		prompt("Type <space> to begin...");
189 		while (inputch() != ' ')
190 			;
191 
192 		done = 0;
193 		while (!done) {
194 			newgame(bspec);
195 			bspec = (char *) NULL;		/* reset for subsequent games */
196 			playgame();
197 			prompt("Type <space> to continue, any cap to quit...");
198 			delay(50);					/* wait for user to quit typing */
199 			flushin(stdin);
200 			while (1) {
201 				int ch;
202 
203 				ch = inputch();
204 				if (ch == '\033')
205 					findword();
206 				else if (ch == '\014' || ch == '\022')	/* ^l or ^r */
207 					redraw();
208 				else {
209 					if (isupper(ch)) {
210 						done = 1;
211 						break;
212 					}
213 					if (ch == ' ')
214 						break;
215 				}
216 			}
217 		}
218 		cleanup();
219 	}
220 	exit(0);
221 }
222 
223 /*
224  * Read a line from the given stream and check if it is legal
225  * Return a pointer to a legal word or a null pointer when EOF is reached
226  */
227 char *
228 batchword(fp)
229 FILE *fp;
230 {
231 	register int *p, *q;
232 	register char *w;
233 	char *nextword();
234 
235 	q = &wordpath[MAXWORDLEN + 1];
236 	p = wordpath;
237 	while (p < q)
238 		*p++ = -1;
239 	while ((w = nextword(fp)) != (char *) NULL) {
240 		if (wordlen < minlength)
241 			continue;
242 		p = wordpath;
243 		while (p < q && *p != -1)
244 			*p++ = -1;
245 		usedbits = 0;
246 		if (checkword(w, -1, wordpath) != -1)
247 			return(w);
248 	}
249 	return((char *) NULL);
250 }
251 
252 /*
253  * Play a single game
254  * Reset the word lists from last game
255  * Keep track of the running stats
256  */
257 playgame()
258 {
259 	/* Can't use register variables if setjmp() is used! */
260 	int i, *p, *q;
261 	long t;
262 	char buf[MAXWORDLEN + 1];
263 	int compar();
264 
265 	ngames++;
266 	npwords = 0;
267 	pwordsp = pwords;
268 	nmwords = 0;
269 	mwordsp = mwords;
270 
271 	time(&start_t);
272 
273 	q = &wordpath[MAXWORDLEN + 1];
274 	p = wordpath;
275 	while (p < q)
276 		*p++ = -1;
277 	showboard(board);
278 	startwords();
279 	if (setjmp(env)) {
280 		badword();
281 		goto timesup;
282 	}
283 
284 	while (1) {
285 		if (getline(buf) == (char *) NULL) {
286 			if (feof(stdin))
287 				clearerr(stdin);
288 			break;
289 		}
290 		time(&t);
291 		if (t - start_t >= tlimit) {
292 			badword();
293 			break;
294 		}
295 		if (buf[0] == '\0') {
296 			int remaining;
297 
298 			remaining = tlimit - (int) (t - start_t);
299 			(void) sprintf(buf, "%d:%02d", remaining / 60, remaining % 60);
300 			showstr(buf, 1);
301 			continue;
302 		}
303 		if (strlen(buf) < minlength) {
304 			badword();
305 			continue;
306 		}
307 
308 		p = wordpath;
309 		while (p < q && *p != -1)
310 			*p++ = -1;
311 		usedbits = 0;
312 
313 		if (checkword(buf, -1, wordpath) < 0)
314 			badword();
315 		else {
316 			if (debug) {
317 				(void) printf("[");
318 				for (i = 0; wordpath[i] != -1; i++)
319 					(void) printf(" %d", wordpath[i]);
320 				(void) printf(" ]\n");
321 			}
322 			for (i = 0; i < npwords; i++) {
323 				if (strcmp(pword[i], buf) == 0)
324 					break;
325 			}
326 			if (i != npwords) {			/* already used the word */
327 				badword();
328 				showword(i);
329 			}
330 			else if (!validword(buf))
331 				badword();
332 			else {
333 				int len;
334 
335 				len = strlen(buf) + 1;
336 				if (npwords == MAXPWORDS - 1 ||
337 						pwordsp + len >= &pwords[MAXPSPACE]) {
338 					(void) fprintf(stderr, "Too many words!\n");
339 					cleanup();
340 					exit(1);
341 				}
342 				pword[npwords++] = pwordsp;
343 				(void) strcpy(pwordsp, buf);
344 				pwordsp += len;
345 				addword(buf);
346 			}
347 		}
348 	}
349 
350 timesup: ;
351 
352 	/*
353 	 * Sort the player's words and terminate the list with a null
354 	 * entry to help out checkdict()
355 	 */
356 	qsort(pword, npwords, sizeof(pword[0]), compar);
357 	pword[npwords] = (char *) NULL;
358 
359 	/*
360 	 * These words don't need to be sorted since the dictionary is sorted
361 	 */
362 	checkdict();
363 
364 	tnmwords += nmwords;
365 	tnpwords += npwords;
366 
367 	results();
368 }
369 
370 /*
371  * Check if the given word is present on the board, with the constraint
372  * that the first letter of the word is adjacent to square 'prev'
373  * Keep track of the current path of squares for the word
374  * A 'q' must be followed by a 'u'
375  * Words must end with a null
376  * Return 1 on success, -1 on failure
377  */
378 checkword(word, prev, path)
379 char *word;
380 int prev, *path;
381 {
382 	register char *p, *q;
383 	register int i, *lm;
384 
385 	if (debug) {
386 		(void) printf("checkword(%s, %d, [", word, prev);
387 			for (i = 0; wordpath[i] != -1; i++)
388 				(void) printf(" %d", wordpath[i]);
389 			(void) printf(" ]\n");
390 	}
391 
392 	if (*word == '\0')
393 		return(1);
394 
395 	lm = letter_map[*word - 'a'];
396 
397 	if (prev == -1) {
398 		char subword[MAXWORDLEN + 1];
399 
400 		/*
401 		 * Check for letters not appearing in the cube to eliminate some
402 		 * recursive calls
403 		 * Fold 'qu' into 'q'
404 		 */
405 		p = word;
406 		q = subword;
407 		while (*p != '\0') {
408 			if (*letter_map[*p - 'a'] == -1)
409 				return(-1);
410 			*q++ = *p;
411 			if (*p++ == 'q') {
412 				if (*p++ != 'u')
413 					return(-1);
414 			}
415 		}
416 		*q = '\0';
417 		while (*lm != -1) {
418 			*path = *lm;
419 			usedbits |= (1 << *lm);
420 			if (checkword(subword + 1, *lm, path + 1) > 0)
421 				return(1);
422 			usedbits &= ~(1 << *lm);
423 			lm++;
424 		}
425 		return(-1);
426 	}
427 
428 	/*
429 	 * A cube is only adjacent to itself in the adjacency matrix if selfuse
430 	 * was set, so a cube can't be used twice in succession if only the reuse
431 	 * flag is set
432 	 */
433 	for (i = 0; lm[i] != -1; i++) {
434 		if (adjacency[prev][lm[i]]) {
435 			int used;
436 
437 			used = 1 << lm[i];
438 			/* If necessary, check if the square has already been used */
439 			if (!reuse && (usedbits & used))
440 					continue;
441 			*path = lm[i];
442 			usedbits |= used;
443 			if (checkword(word + 1, lm[i], path + 1) > 0)
444 				return(1);
445 			usedbits &= ~used;
446 		}
447 	}
448 	*path = -1;		/* in case of a backtrack */
449 	return(-1);
450 }
451 
452 /*
453  * A word is invalid if it is not in the dictionary
454  * At this point it is already known that the word can be formed from
455  * the current board
456  */
457 validword(word)
458 char *word;
459 {
460 	register int j;
461 	register char *q, *w;
462 	char *nextword();
463 
464 	j = word[0] - 'a';
465 	if (dictseek(dictfp, dictindex[j].start, 0) < 0) {
466 		(void) fprintf(stderr, "Seek error\n");
467 		cleanup();
468 		exit(1);
469 	}
470 
471 	while ((w = nextword(dictfp)) != (char *) NULL) {
472 		int ch;
473 
474 		if (*w != word[0])	/* end of words starting with word[0] */
475 			break;
476 		q = word;
477 		while ((ch = *w++) == *q++ && ch != '\0')
478 			;
479 		if (*(w - 1) == '\0' && *(q - 1) == '\0')
480 			return(1);
481 	}
482 	if (dictfp != (FILE *) NULL && feof(dictfp))	/* Special case for z's */
483 		clearerr(dictfp);
484 	return(0);
485 }
486 
487 /*
488  * Check each word in the dictionary against the board
489  * Delete words from the machine list that the player has found
490  * Assume both the dictionary and the player's words are already sorted
491  */
492 checkdict()
493 {
494 	register char *p, **pw, *w;
495 	register int i;
496 	int prevch, previndex, *pi, *qi, st;
497 
498 	mwordsp = mwords;
499 	nmwords = 0;
500 	pw = pword;
501 	prevch ='a';
502 	qi = &wordpath[MAXWORDLEN + 1];
503 
504 	(void) dictseek(dictfp, 0L, 0);
505 	while ((w = nextword(dictfp)) != (char *) NULL) {
506 		if (wordlen < minlength)
507 			continue;
508 		if (*w != prevch) {
509 			/*
510 			 * If we've moved on to a word with a different first letter
511 			 * then we can speed things up by skipping all words starting
512 			 * with a letter that doesn't appear in the cube
513 			 */
514 			i = (int) (*w - 'a');
515 			while (i < 26 && letter_map[i][0] == -1)
516 				i++;
517 			if (i == 26)
518 				break;
519 			previndex = prevch - 'a';
520 			prevch = i + 'a';
521 			/*
522 			 * Fall through if the word's first letter appears in the cube
523 			 * (i.e., if we can't skip ahead), otherwise seek to the
524 			 * beginning of words in the dictionary starting with the
525 			 * next letter (alphabetically) appearing in the cube and then
526 			 * read the first word
527 			 */
528 			if (i != previndex + 1) {
529 				if (dictseek(dictfp, dictindex[i].start, 0) < 0) {
530 					(void) fprintf(stderr, "Seek error in checkdict()\n");
531 					cleanup();
532 					exit(1);
533 				}
534 				continue;
535 			}
536 		}
537 
538 		pi = wordpath;
539 		while (pi < qi && *pi != -1)
540 			*pi++ = -1;
541 		usedbits = 0;
542 		if (checkword(w, -1, wordpath) == -1)
543 			continue;
544 
545 		st = 1;
546 		while (*pw != (char *) NULL && (st = strcmp(*pw, w)) < 0)
547 			pw++;
548 		if (st == 0)			/* found it */
549 			continue;
550 		if (nmwords == MAXMWORDS ||
551 					mwordsp + wordlen + 1 >= &mwords[MAXMSPACE]) {
552 			(void) fprintf(stderr, "Too many words!\n");
553 			cleanup();
554 			exit(1);
555 		}
556 		mword[nmwords++] = mwordsp;
557 		p = w;
558 		while (*mwordsp++ = *p++)
559 			;
560 	}
561 }
562 
563 /*
564  * Crank up a new game
565  * If the argument is non-null then it is assumed to be a legal board spec
566  * in ascending cube order, oth. make a random board
567  */
568 newgame(b)
569 char *b;
570 {
571 	register int i, p, q;
572 	char *tmp;
573 	int *lm[26];
574 	static char *cubes[16] = {
575 		"ednosw", "aaciot", "acelrs", "ehinps",
576 		"eefhiy", "elpstu", "acdemp", "gilruw",
577 		"egkluy", "ahmors", "abilty", "adenvz",
578 		"bfiorx", "dknotu", "abjmoq", "egintv"
579 	};
580 
581 	if (b == (char *) NULL) {
582 		/*
583 		 * Shake the cubes and make the board
584 		 */
585 		i = 0;
586 		while (i < 100) {
587 			p = (int) (random() % 16);
588 			q = (int) (random() % 16);
589 			if (p != q) {
590 				tmp = cubes[p];
591 				cubes[p] = cubes[q];
592 				cubes[q] = tmp;
593 				i++;
594 			}
595 			/* else try again */
596 		}
597 
598 		for (i = 0; i < 16; i++)
599 			board[i] = cubes[i][random() % 6];
600 	}
601 	else {
602 		for (i = 0; i < 16; i++)
603 			board[i] = b[i];
604 	}
605 	board[16] = '\0';
606 
607 	/*
608 	 * Set up the map from letter to location(s)
609 	 * Each list is terminated by a -1 entry
610 	 */
611 	for (i = 0; i < 26; i++) {
612 		lm[i] = letter_map[i];
613 		*lm[i] = -1;
614 	}
615 
616 	for (i = 0; i < 16; i++) {
617 		register int j;
618 
619 		j = (int) (board[i] - 'a');
620 		*lm[j] = i;
621 		*(++lm[j]) = -1;
622 	}
623 
624 	if (debug) {
625 		for (i = 0; i < 26; i++) {
626 			int ch, j;
627 
628 			(void) printf("%c:", 'a' + i);
629 			for (j = 0; (ch = letter_map[i][j]) != -1; j++)
630 				(void) printf(" %d", ch);
631 			(void) printf("\n");
632 		}
633 	}
634 
635 }
636 
637 compar(p, q)
638 char **p, **q;
639 {
640 	return(strcmp(*p, *q));
641 }
642 
643 usage()
644 {
645 (void) fprintf(stderr,
646 "Usage: bog [-b] [-d] [-s#] [-t#] [-w#] [+[+]] [boardspec]\n");
647 (void) fprintf(stderr, "-b: 'batch mode' (boardspec must be present)\n");
648 (void) fprintf(stderr, "-d: debug\n");
649 (void) fprintf(stderr, "-s#: use # as the random number seed\n");
650 (void) fprintf(stderr, "-t#: time limit is # seconds\n");
651 (void) fprintf(stderr, "-w#: minimum word length is # letters\n");
652 (void) fprintf(stderr, "+: can reuse a cube, but not twice in succession\n");
653 (void) fprintf(stderr, "++: can reuse cubes arbitrarily\n");
654 (void) fprintf(stderr, "boardspec: the first board to use (use 'q' for 'qu')\n");
655 	exit(1);
656 }
657 
658