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