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