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