1/*	$NetBSD: bog.c,v 1.28 2012/10/13 20:12:18 dholland 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. Neither the name of the University nor the names of its contributors
19 *    may be used to endorse or promote products derived from this software
20 *    without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 */
34
35#include <sys/cdefs.h>
36#ifndef lint
37__COPYRIGHT("@(#) Copyright (c) 1993\
38 The Regents of the University of California.  All rights reserved.");
39#endif /* not lint */
40
41#ifndef lint
42#if 0
43static char sccsid[] = "@(#)bog.c	8.2 (Berkeley) 5/4/95";
44#else
45__RCSID("$NetBSD: bog.c,v 1.28 2012/10/13 20:12:18 dholland Exp $");
46#endif
47#endif /* not lint */
48
49#include <ctype.h>
50#include <err.h>
51#include <stdio.h>
52#include <stdlib.h>
53#include <string.h>
54#include <time.h>
55#include <unistd.h>
56#include <sys/tty.h>
57
58#include "bog.h"
59#include "extern.h"
60
61static char *batchword(FILE *);
62static void playgame(void);
63static int validword(const char *);
64static void checkdict(void);
65static void newgame(const char *);
66static int compar(const void *, const void *);
67static void clearwordpath(int full);
68static void usage(void) __dead;
69
70struct dictindex dictindex[26];
71
72/*
73 * Cube position numbering:
74 *
75 *	0 1 2 3
76 *	4 5 6 7
77 *	8 9 A B
78 *	C D E F
79 */
80static int adjacency[16][16] = {
81/*        0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F */
82	{ 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },		/* 0 */
83	{ 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },		/* 1 */
84	{ 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },		/* 2 */
85	{ 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },		/* 3 */
86	{ 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0 },		/* 4 */
87	{ 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0 },		/* 5 */
88	{ 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0 },		/* 6 */
89	{ 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0 },		/* 7 */
90	{ 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0 },		/* 8 */
91	{ 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0 },		/* 9 */
92	{ 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1 },		/* A */
93	{ 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1 },		/* B */
94	{ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0 },		/* C */
95	{ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0 },		/* D */
96	{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1 },		/* E */
97	{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0 }		/* F */
98};
99
100static int letter_map[26][16];
101
102char board[17];
103int wordpath[MAXWORDLEN + 1];
104int wordlen;		/* Length of last word returned by nextword() */
105int usedbits;
106
107const char *pword[MAXPWORDS];
108static char pwords[MAXPSPACE], *pwordsp;
109int npwords;
110
111const char *mword[MAXMWORDS];
112static char mwords[MAXMSPACE], *mwordsp;
113int nmwords;
114
115int ngames = 0;
116int tnmwords = 0, tnpwords = 0;
117
118#include <setjmp.h>
119jmp_buf env;
120
121time_t start_t;
122int debug;
123int tlimit;
124
125static FILE *dictfp;
126static int batch;
127static int minlength;
128static int reuse;
129
130int
131main(int argc, 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((unsigned char)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 == '\e')
252				findword();
253			else if (ch == CTRL('l') || ch == CTRL('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 == '\e')
265				findword();
266			else if (ch == CTRL('l') || ch == CTRL('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 */
287static char *
288batchword(FILE *fp)
289{
290	char *w;
291
292	clearwordpath(1);
293	while ((w = nextword(fp)) != NULL) {
294		if (wordlen < minlength)
295			continue;
296		clearwordpath(0);
297		usedbits = 0;
298		if (checkword(w, -1, wordpath) != -1)
299			return (w);
300	}
301	return (NULL);
302}
303
304/*
305 * Play a single game
306 * Reset the word lists from last game
307 * Keep track of the running stats
308 */
309static void
310playgame(void)
311{
312	int i;
313	time_t t;
314	char buf[MAXWORDLEN + 1];
315
316	ngames++;
317	npwords = 0;
318	pwordsp = pwords;
319	nmwords = 0;
320	mwordsp = mwords;
321
322	time(&start_t);
323
324	clearwordpath(1);
325	showboard(board);
326	startwords();
327	if (setjmp(env)) {
328		badword();
329		goto timesup;
330	}
331
332	while (1) {
333		if (get_line(buf) == NULL) {
334			if (feof(stdin))
335				clearerr(stdin);
336			break;
337		}
338		time(&t);
339		if (t - start_t >= tlimit) {
340			badword();
341			break;
342		}
343		if (buf[0] == '\0') {
344			int remaining;
345
346			remaining = tlimit - (int) (t - start_t);
347			(void)snprintf(buf, sizeof(buf),
348			    "%d:%02d", remaining / 60, remaining % 60);
349			showstr(buf, 1);
350			continue;
351		}
352		if (strlen(buf) < (size_t)minlength) {
353			badword();
354			continue;
355		}
356
357		clearwordpath(0);
358		usedbits = 0;
359
360		if (checkword(buf, -1, wordpath) < 0)
361			badword();
362		else {
363			if (debug) {
364				(void) printf("[");
365				for (i = 0; wordpath[i] != -1; i++)
366					(void) printf(" %d", wordpath[i]);
367				(void) printf(" ]\n");
368			}
369			for (i = 0; i < npwords; i++) {
370				if (strcmp(pword[i], buf) == 0)
371					break;
372			}
373			if (i != npwords) {	/* already used the word */
374				badword();
375				showword(i);
376			}
377			else if (!validword(buf))
378				badword();
379			else {
380				size_t len;
381
382				len = strlen(buf) + 1;
383				if (npwords == MAXPWORDS - 1 ||
384				    pwordsp + len >= &pwords[MAXPSPACE]) {
385					warnx("Too many words!");
386					cleanup();
387					exit(1);
388				}
389				pword[npwords++] = pwordsp;
390				(void) strcpy(pwordsp, buf);
391				pwordsp += len;
392				addword(buf);
393			}
394		}
395	}
396
397timesup: ;
398
399	/*
400	 * Sort the player's words and terminate the list with a null
401	 * entry to help out checkdict()
402	 */
403	qsort(pword, npwords, sizeof(pword[0]), compar);
404	pword[npwords] = NULL;
405
406	/*
407	 * These words don't need to be sorted since the dictionary is sorted
408	 */
409	checkdict();
410
411	tnmwords += nmwords;
412	tnpwords += npwords;
413
414	results();
415}
416
417/*
418 * Check if the given word is present on the board, with the constraint
419 * that the first letter of the word is adjacent to square 'prev'
420 * Keep track of the current path of squares for the word
421 * A 'q' must be followed by a 'u'
422 * Words must end with a null
423 * Return 1 on success, -1 on failure
424 */
425int
426checkword(const char *word, int prev, int *path)
427{
428	const char *p;
429	char *q;
430	int i, *lm;
431
432	if (debug) {
433		(void) printf("checkword(%s, %d, [", word, prev);
434			for (i = 0; wordpath[i] != -1; i++)
435				(void) printf(" %d", wordpath[i]);
436			(void) printf(" ]\n");
437	}
438
439	if (*word == '\0')
440		return (1);
441
442	lm = letter_map[*word - 'a'];
443
444	if (prev == -1) {
445		char subword[MAXWORDLEN + 1];
446
447		/*
448		 * Check for letters not appearing in the cube to eliminate some
449		 * recursive calls
450		 * Fold 'qu' into 'q'
451		 */
452		p = word;
453		q = subword;
454		while (*p != '\0') {
455			if (*letter_map[*p - 'a'] == -1)
456				return (-1);
457			*q++ = *p;
458			if (*p++ == 'q') {
459				if (*p++ != 'u')
460					return (-1);
461			}
462		}
463		*q = '\0';
464		while (*lm != -1) {
465			*path = *lm;
466			usedbits |= (1 << *lm);
467			if (checkword(subword + 1, *lm, path + 1) > 0)
468				return (1);
469			usedbits &= ~(1 << *lm);
470			lm++;
471		}
472		return (-1);
473	}
474
475	/*
476	 * A cube is only adjacent to itself in the adjacency matrix if selfuse
477	 * was set, so a cube can't be used twice in succession if only the
478	 * reuse flag is set
479	 */
480	for (i = 0; lm[i] != -1; i++) {
481		if (adjacency[prev][lm[i]]) {
482			int used;
483
484			used = 1 << lm[i];
485			/*
486			 * If necessary, check if the square has already
487			 * been used.
488			 */
489			if (!reuse && (usedbits & used))
490					continue;
491			*path = lm[i];
492			usedbits |= used;
493			if (checkword(word + 1, lm[i], path + 1) > 0)
494				return (1);
495			usedbits &= ~used;
496		}
497	}
498	*path = -1;		/* in case of a backtrack */
499	return (-1);
500}
501
502/*
503 * A word is invalid if it is not in the dictionary
504 * At this point it is already known that the word can be formed from
505 * the current board
506 */
507static int
508validword(const char *word)
509{
510	int j;
511	const char *q, *w;
512
513	j = word[0] - 'a';
514	if (dictseek(dictfp, dictindex[j].start, SEEK_SET) < 0) {
515		(void) fprintf(stderr, "Seek error\n");
516		cleanup();
517		exit(1);
518	}
519
520	while ((w = nextword(dictfp)) != NULL) {
521		int ch;
522
523		if (*w != word[0])	/* end of words starting with word[0] */
524			break;
525		q = word;
526		while ((ch = *w++) == *q++ && ch != '\0')
527			;
528		if (*(w - 1) == '\0' && *(q - 1) == '\0')
529			return (1);
530	}
531	if (dictfp != NULL && feof(dictfp))	/* Special case for z's */
532		clearerr(dictfp);
533	return (0);
534}
535
536/*
537 * Check each word in the dictionary against the board
538 * Delete words from the machine list that the player has found
539 * Assume both the dictionary and the player's words are already sorted
540 */
541static void
542checkdict(void)
543{
544	char *p, *w;
545	const char **pw;
546	int i;
547	int prevch, previndex, st;
548
549	mwordsp = mwords;
550	nmwords = 0;
551	pw = pword;
552	prevch ='a';
553
554	(void) dictseek(dictfp, 0L, SEEK_SET);
555	while ((w = nextword(dictfp)) != NULL) {
556		if (wordlen < minlength)
557			continue;
558		if (*w != prevch) {
559			/*
560			 * If we've moved on to a word with a different first
561			 * letter then we can speed things up by skipping all
562			 * words starting with a letter that doesn't appear in
563			 * the cube.
564			 */
565			i = (int) (*w - 'a');
566			while (i < 26 && letter_map[i][0] == -1)
567				i++;
568			if (i == 26)
569				break;
570			previndex = prevch - 'a';
571			prevch = i + 'a';
572			/*
573			 * Fall through if the word's first letter appears in
574			 * the cube (i.e., if we can't skip ahead), otherwise
575			 * seek to the beginning of words in the dictionary
576			 * starting with the next letter (alphabetically)
577			 * appearing in the cube and then read the first word.
578			 */
579			if (i != previndex + 1) {
580				if (dictseek(dictfp,
581				    dictindex[i].start, SEEK_SET) < 0) {
582					warnx("seek error in checkdict()");
583					cleanup();
584					exit(1);
585				}
586				continue;
587			}
588		}
589
590		clearwordpath(0);
591		usedbits = 0;
592		if (checkword(w, -1, wordpath) == -1)
593			continue;
594
595		st = 1;
596		while (*pw != NULL && (st = strcmp(*pw, w)) < 0)
597			pw++;
598		if (st == 0)			/* found it */
599			continue;
600		if (nmwords == MAXMWORDS ||
601		    mwordsp + wordlen + 1 >= &mwords[MAXMSPACE]) {
602			warnx("too many words!");
603			cleanup();
604			exit(1);
605		}
606		mword[nmwords++] = mwordsp;
607		p = w;
608		while ((*mwordsp++ = *p++) != '\0')
609		    	;
610	}
611}
612
613/*
614 * Crank up a new game
615 * If the argument is non-null then it is assumed to be a legal board spec
616 * in ascending cube order, oth. make a random board
617 */
618static void
619newgame(const char *b)
620{
621	int i, p, q;
622	const char *tmp;
623	int *lm[26];
624	static const char *cubes[16] = {
625		"ednosw", "aaciot", "acelrs", "ehinps",
626		"eefhiy", "elpstu", "acdemp", "gilruw",
627		"egkluy", "ahmors", "abilty", "adenvz",
628		"bfiorx", "dknotu", "abjmoq", "egintv"
629	};
630
631	if (b == NULL) {
632		/*
633		 * Shake the cubes and make the board
634		 */
635		i = 0;
636		while (i < 100) {
637			p = (int) (random() % 16);
638			q = (int) (random() % 16);
639			if (p != q) {
640				tmp = cubes[p];
641				cubes[p] = cubes[q];
642				cubes[q] = tmp;
643				i++;
644			}
645			/* else try again */
646		}
647
648		for (i = 0; i < 16; i++)
649			board[i] = cubes[i][random() % 6];
650	}
651	else {
652		for (i = 0; i < 16; i++)
653			board[i] = b[i];
654	}
655	board[16] = '\0';
656
657	/*
658	 * Set up the map from letter to location(s)
659	 * Each list is terminated by a -1 entry
660	 */
661	for (i = 0; i < 26; i++) {
662		lm[i] = letter_map[i];
663		*lm[i] = -1;
664	}
665
666	for (i = 0; i < 16; i++) {
667		int j;
668
669		j = (int) (board[i] - 'a');
670		*lm[j] = i;
671		*(++lm[j]) = -1;
672	}
673
674	if (debug) {
675		for (i = 0; i < 26; i++) {
676			int ch, j;
677
678			(void) printf("%c:", 'a' + i);
679			for (j = 0; (ch = letter_map[i][j]) != -1; j++)
680				(void) printf(" %d", ch);
681			(void) printf("\n");
682		}
683	}
684
685}
686
687/*
688 * Clear wordpath[].
689 */
690static void
691clearwordpath(int full)
692{
693	size_t pos;
694	const size_t max = MAXWORDLEN + 1;
695
696	for (pos = 0; pos < max && (full || wordpath[pos] != -1); pos++) {
697		wordpath[pos] = -1;
698	}
699}
700
701static int
702compar(const void *p, const void *q)
703{
704	return (strcmp(*(const char *const *)p, *(const char *const *)q));
705}
706
707static void
708usage(void)
709{
710	(void) fprintf(stderr,
711	    "usage: %s [-bd] [-s#] [-t#] [-w#] [+[+]] [boardspec]\n",
712	    getprogname());
713	exit(1);
714}
715