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