[unix-history] / usr / src / old / boggle / boggle.c

#ifndef lint
static char sccsid[] = "@(#)boggle.c	4.2 %G%";
#endif

#include <ctype.h>
#include <errno.h>
#include <setjmp.h>
#include <sgtty.h>
#include <signal.h>
#include <stdio.h>

/* basic parameters */
#define N 4
#define SSIZE 200
#define MAXWORDS 1000
#define CWIDTH 10
#define LWIDTH 80

/* parameters defined in terms of above */
#define BSIZE (N*N)
#define row(x) (x/N)
#define col(x) (x%N)

/* word being searched for */
int wlength;
int numsame;
char wbuff [BSIZE+1];

/* tty and process control */
extern int errno;
int status;
int pipefd[2];
int super = 0;
int delct = 1;
int zero = 0;
int master = 1;
int column;
int *timept;
int timeint[] = {60,60,50,7,1,1,1,0};
long timein;
extern long int time();
struct sgttyb origttyb, tempttyb;
int ctlecho = 0;
int lctlech = LCTLECH;
jmp_buf env;

/* monitoring variables */
int games;
int logfile = -1;
long logloc;
char logbuff[100] = {"inst\t"};
extern char *ctime(), *getlogin();
extern long lseek();

/* dictionary interface */
char defname[] = "/usr/games/bogdict";
char *dictname = &defname[0];
FILE *dict;

/* structures for doing matching */
struct frame {
	struct frame *parent;
	int place;
};
struct frame stack [SSIZE];
struct frame *level [BSIZE+1];

/* the board and subsidiary structures */
char present [BSIZE+1];
char board [BSIZE];
char olink [BSIZE];
char adj [BSIZE+1][BSIZE];
char occurs [26];

/* the boggle cubes */
char *cube [BSIZE] = {
	"forixb", "moqabj", "gurilw", "setupl",
	"cmpdae", "acitao", "slcrae", "romash",
	"nodesw", "hefiye", "onudtk", "tevign",
	"anedvz", "pinesh", "abilyt", "gkyleu"
};


/* storage for words found */
int ubotch, ustart, wcount;
char *word [MAXWORDS];
char *freesp;
char space[10000];

endline ()
{
	if (column != 0) {
		putchar('\n');
		column = 0;
	}
}

timeout ()
{
	if (*timept > 0) {
		signal (SIGALRM, timeout);
		alarm(*timept++);
	}
	putchar('\007');
}

interrupt ()
{
	signal(SIGINT, interrupt);
	if (delct++ >= 1)
		longjmp(env, 1);
	timept = &zero;
}

goodbye (stat)
int stat;
{
	if (master != 0) {
		wait(&status);
		if ( ctlecho & LCTLECH ) {
			ioctl( fileno(stdin), TIOCLBIS, &lctlech );
		}
		stty(fileno(stdin), &origttyb);
	}
	exit(stat);
}

clearscreen ()
{
	stty (fileno(stdin), &tempttyb);
	printf("\n\033\f\r");
}

compare (a, b)
char **a, **b;
{
	return(wordcomp(*a, *b));
}

wordcomp (p, q)
register char *p, *q;
{
	if (*p=='0' && *q!='0')
		return(-1);
	if (*p!='0' && *q=='0')
		return(1);
	while (*++p == *++q && isalpha(*p)) ;
	if (!isalpha(*p))
		return(-isalpha(*q));
	if (!isalpha(*q))
		return(1);
	return(*p-*q);
}

printinst ()
{
	stty (fileno(stdin), &tempttyb);
	printf("instructions?");
	if (getchar() == 'y') {
		clearscreen();
		printf("     The object of Boggle (TM  Parker  Bros.)  is  to  find,  within  3\n");
		printf("minutes,  as many words as possible in a 4 by 4 grid of letters.  Words\n");
		printf("may be formed from any sequence of 3 or more adjacent  letters  in  the\n");
		printf("grid.   The  letters  may join horizontally, vertically, or diagonally.\n");
		printf("However, no position in the grid may be used more than once within  any\n");
		printf("one  word.   In  competitive  play amongst humans, each player is given\n");
		printf("credit for those of his words which no other player has found.\n");
		printf("     This program is intended  for  people  wishing  to  sharpen  their\n");
		printf("skills  at  Boggle.   If  you  invoke the program with 4 arguments of 4\n");
		printf("letters each, (e.g. \"boggle appl epie moth erhd\") the program forms the\n");
		printf("obvious  Boggle grid and lists all the words from /usr/dict/words found\n");
		printf("therein.  If you invoke the program without arguments, it will generate\n");
		printf("a  board  for you, let you enter words for 3 minutes, and then tell you\n");
		printf("how well you did relative to /usr/dict/words.\n");
		printf("     In interactive play, enter your words separated by  spaces,  tabs,\n");
		printf("or  newlines.   A  bell will ring when there is 2:00, 1:00, 0:10, 0:02,\n");
		printf("0:01, and 0:00 time left.  You may complete any word started before the\n");
		printf("expiration  of  time.   You  can surrender before time is up by hitting\n");
		printf("'break'.  While entering words, your erase character is only  effective\n");
		printf("within the current word and your line kill character is ignored.\n");
		printf("     Advanced players may wish to invoke the program with 1 or 2 +'s as\n");
		printf("the  first argument.  The first + removes the restriction that positions\n");
		printf("can only be used once in each word.  The second + causes a position  to\n");
		printf("be  considered  adjacent  to itself as well as its (up to) 8 neighbors.\n");
		printf("Hit any key to begin.\n");
		stty (fileno(stdin), &tempttyb);
		getchar();
	}
	stty (fileno(stdin), &tempttyb);
}

setup ()
{
	register int i, j;
	int rd, cd, k;
	for (i=0; i<BSIZE; i++) {
		adj[i][i] = super>=2 ? 1 : 0;
		adj[BSIZE][i] = 1;
		for (j=0; j<i; j++) {
			rd = row(i)-row(j);
			cd = col(i)-col(j);
			k = 0;
			switch (rd) {
			case -1:
			case 1:
				if (-1<=cd && cd<=1)
					k = 1;
				break;
			case 0:
				if (cd==-1 || cd==1)
					k = 1;
				break;
			}
			adj[i][j] = adj[j][i] = k;
		}
	}
	stack[0].parent = &stack[0];
	stack[0].place = BSIZE;
	level[0] = &stack[0];
	level[1] = &stack[1];
}

makelists ()
{
	register int i, c;
	for (i=0; i<26; i++)
		occurs[i] = BSIZE;
	for (i=0; i<BSIZE; i++) {
		c = board[i];
		olink[i] = occurs[c-'a'];
		occurs[c-'a'] = i;
	}
}

genboard ()
{
	register int i, j;
	for (i=0; i<BSIZE; i++)
		board[i] = 0;
	for (i=0; i<BSIZE; i++) {
		j = rand()%BSIZE;
		while (board[j] != 0)
			j = (j+1)%BSIZE;
		board[j] = cube[i][rand()%6];
	}
}

printboard ()
{
	register int i, j;
	for (i=0; i<N; i++) {
		printf("\t\t\t\t\b\b");
		for (j=0; j<N; j++) {
			putchar ((putchar(board[i*N+j]) == 'q') ? 'u' : ' ');
			putchar(' ');
		}
		putchar('\n');
	}
	putchar('\n');
}

getdword ()
{
	/* input:  numsame = # chars same as last word   */
	/* output: numsame = # same chars for next word  */
	/*        word in wbuff[0]...wbuff[wlength-1]    */
	register int c;
	register char *p;
	if (numsame == EOF)
		return (0);
	p = &wbuff[numsame]+1;
	while ((*p++ = c = getc(dict)) != EOF && isalpha(c)) ;
	numsame = c;
	wlength = p - &wbuff[2];
	return (1);
}

getuword ()
{
	int c;
	register char *p, *q, *r;
	numsame = 0;
	while (*timept>0 && (isspace(c=getchar()) || c==EOF));
	if (*timept == 0)
		return(0);
	word[wcount++] = freesp;
	*freesp++ = '0';
	r = &wbuff[1];
	q = p = freesp;
	*p++ = c;
	while (!isspace(c = getchar())) {
		if (c == EOF)
			continue;
		if (c == origttyb.sg_erase) {
			if (p > q)
				p--;
			continue;
		}
		*p++ = c;
	}
	freesp = p;
	for (p=q; p<freesp && r<&wbuff[BSIZE]; )
		if (islower(c = *p++) && (*r++ = *q++ = c) == 'q' && *p == 'u')
			p++;
	*(freesp = q) = '0';
	wlength = r-&wbuff[1];
	return(1);
}

aputuword (ways)
int ways;
{
	*word[wcount-1] = ways>=10 ? '*' : '0'+ways;
}

aputword (ways)
int ways;
{
	/* store (wbuff, ways) in next slot in space */
	register int i;
	*freesp++ = ways>=10 ? '*' : '0'+ways;
	for (i=1; i<= wlength; i++)
		*freesp++ = wbuff[i];
	word[++wcount] = freesp;
}

tputword (ways)
int ways;
{
	/* print (wbuff, ways) on terminal */
	wbuff[wlength+1] = '0';
	wbuff[0] = ways>=10 ? '*' : '0'+ways;
	outword(&wbuff[0]);
}

outword (p)
register char *p;
{
	register int newcol;
	register char *q;
	for (q=p+1; isalpha(*q); ) {
		putchar(*q);
		if (*q++ == 'q') {
			putchar('u');
			column++;
		}
	}
	column += q-p-1;
	if (column > LWIDTH-CWIDTH) {
		putchar('\n');
		column = 0;
		return;
	}
	newcol = ((column+CWIDTH)/CWIDTH)*CWIDTH;
	while (((column+8)/8)*8 <= newcol) {
		putchar('\t');
		column = ((column+8)/8)*8;
	}
	while (column < newcol) {
		putchar(' ');
		column++;
	}
}

printdiff ()
{
	register int c, d, u;
	char both, donly, uonly;
	word[wcount] = freesp;
	*freesp = '0';
	both = donly = uonly = column = d = 0;
	u = ustart;
	while (d < ubotch) {
		c = u<wcount ? wordcomp (word[d], word[u]) : -1;
		if (c == 0) {
			/* dict and user found same word */
			if (both == 0) {
				both = 1;
				printf("\t\t\t   we both found:\n");
			}
			outword(word[d]);
			word[d++] = NULL;
			word[u++] = NULL;
		} else if (c < 0) {
			/* dict found it, user didn't */
			donly = 1;
			d++;
		} else {
			/* user found it, dict didn't */
			uonly = 1;
			u++;
		}
	}
	endline();
	if (donly) {
		printf("\n\t\t\tI alone found these:\n");
		for (d=0; d<ubotch; d++)
			if (word[d] != NULL)
				outword(word[d]);
		endline();
	}
	if (uonly) {
		printf("\n\t\t\tyou alone found these:\n");
		for (u=ustart; u<wcount; u++)
			if (word[u] != NULL)
				outword(word[u]);
		endline();
	}
	if (ubotch < ustart) {
		printf("\n\t\t\t  you botched these:\n");
		for (u=ubotch; u<ustart; u++)
			outword(word[u]);
		endline();
	}
}

numways (leaf, last)
register struct frame *leaf;
struct frame *last;
{
	int count;
	register char *p;
	register struct frame *node;
	if (super > 0)
		return(last-leaf);
	count = 0;
	present[BSIZE] = 1;
	while (leaf < last) {
		for (p = &present[0]; p < &present[BSIZE]; *p++ = 0);
		for (node = leaf; present[node->place]++ == 0; node = node->parent);
		if (node == &stack[0])
			count++;
		leaf++;
	}
	return(count);
}

evalboard (getword, putword)
int (*getword)(), (*putword)();
{
	register struct frame *top;
	register int l, q;
	int fo, found;
	struct frame *parent, *lastparent;
	char *padj;

	numsame = found = 0;
	makelists ();

	while (1) {
		l = numsame;
		if (!(*getword) ())
			break;
		top = level[l+1];
	
		while (1) {
			level[l+1] = lastparent = top;
			/* wbuff[1]...wbuff[l] have been matched */
			/* level[0],...,level[l] of tree built */
			if (l == wlength) {
				if (wlength >= 3 && (q = numways(level[l], top)) != 0) {
					(*putword) (q);
					found++;
				}
				l = BSIZE+1;
				break;
			}
			if ((fo = occurs[wbuff[++l]-'a']) == BSIZE)
				break;
			/* wbuff[1]...wbuff[l-1] have been matched */
			/* level[0],...,level[l-1] of tree built */
			for (parent=level[l-1]; parent<lastparent; parent++) {
				padj = &adj[parent->place][0];
				for (q=fo; q!=BSIZE; q=olink[q])
					if (padj[q]) {
						top->parent = parent;
						top->place = q;
						if (++top >= &stack[SSIZE]) {
							printf("stack overflow\n");
							goodbye(1);
						}
					}
			}
			/* were any nodes added? */
			if (top == lastparent)
				break;
		}

		/* advance until first l characters of next word are different */
		while (numsame >= l && (*getword)()) ;
	}
	return(found);
}

main (argc, argv)
int argc;
char **argv;
{
	char *q;
	register char *p;
	register int i, c;

	gtty (fileno(stdin), &origttyb);
	setbuf(stdin, NULL);
	tempttyb = origttyb;
	if (setjmp(env) != 0)
		goodbye(0);
	signal (SIGINT, interrupt);
	timein = time(0L);
	if (argv[0][0] != 'a' && (logfile = open("/usr/games/boglog", 1)) >= 0) {
		p = &logbuff[5];
		q = getlogin();
		while (*p++ = *q++);
		p[-1] = '\t';
		q = ctime(&timein);
		while (*p++ = *q++);
		logloc = lseek(logfile, 0L, 2);
		write(logfile, &logbuff[0], p-&logbuff[1]);
	}
	if ((dict = fopen(dictname, "r")) == NULL) {
		printf("can't open %s\n", dictname);
		goodbye (2);
	}
	while ( argc > 1 && ( argv[1][0] == '+' || argv[1][0] == '-' ) ) {
		if (argv[1][0]=='+') {
			while(*(argv[1]++) == '+')
				super++;
			argc--;
			argv++;
		}
		if ( argv[1][0] == '-' ) {
			timeint[0] = 60 * ( atol( &argv[1][1] ) - 2 );
			if ( timeint[0] <= 0 ) {
				timeint[0] = 60;
			}
			argc--;
			argv++;
		}
	}
	setup ();
	switch (argc) {
	default:  punt:
		printf("usage: boggle [+[+]] [row1 row2 row3 row4]\n");
		goodbye (3);
	case 5:
		for (i=0; i<BSIZE; i++) {
			board[i] = c = argv[row(i)+1][col(i)];
			if (!islower(c)) {
				printf("bad board\n");
				goto punt;
			}
		}
		printboard();
		column = 0;
		evalboard(getdword, tputword);
		endline();
		if (logfile >= 0) {
			strncpy(&logbuff[0], "eval", 4);
			lseek(logfile, logloc, 0);
			write(logfile, &logbuff[0], 4);
		}
		goodbye(0);
	case 1:
		tempttyb.sg_flags |= CBREAK;
		if ( ioctl( fileno(stdin), TIOCLGET, &ctlecho ) == 0 ) {
			if ( ctlecho & LCTLECH ) {
				ioctl( fileno(stdin), TIOCLBIC, &lctlech );
			}
		}
		printinst();
		srand((int) timein);
		while (setjmp(env) == 0) {
			errno = 0;
			if (pipe(&pipefd[0]) != 0) {
				printf("can't create pipe\n");
				goodbye(4);
			}
			genboard();
			delct = wcount = 0;
			word[0] = freesp = &space[0];
			if ((master = fork()) == 0) {
				close(pipefd[0]);
				clearscreen();
				printboard();
				signal(SIGALRM, timeout);
				timept = &timeint[0];
				alarm(*timept++);
				evalboard(getuword, aputuword);
				clearscreen();
				qsort(&word[0], wcount, sizeof (int), compare);
				for (i=0; i<wcount; i++)
					if (i==0 || wordcomp(word[i], word[i-1])!=0) {
						p = word[i];
						while (isalpha(*++p)) ;
						write (pipefd[1], word[i], p-word[i]);
					}
				close(pipefd[1]);
				goodbye(0);
			}
			close(pipefd[1]);
			rewind(dict);
			getc(dict);
			evalboard(getdword, aputword);
			p = freesp;
			while ((i = read(pipefd[0], freesp, 512)) != 0) {
				if (i < 0)
					if (errno != EINTR)
						break;
					else
						i = 0;
				freesp += i;
			}
			close(pipefd[0]);
			ustart = ubotch = wcount;
			while (p < freesp) {
				word[wcount++] = p;
				if (*p == '0')
					ustart = wcount;
				while (isalpha(*++p));
			}
			wait(&status);
			if (status != 0)
				goodbye (5);
			delct = 1;
			printdiff();
			printboard();
			games++;
			if (logfile >= 0) {
				sprintf(&logbuff[0], "%4d", games);
				lseek(logfile, logloc, 0);
				write(logfile, &logbuff[0], 4);
			}
			stty (fileno(stdin), &tempttyb);
			printf("\nanother game?");
			if (getchar() != 'y') {
				putchar('\n');
				break;
			}
			stty (fileno(stdin), &tempttyb);
		}
		goodbye(0);
	}
}
Commit	Line	Data
4dba9a68	1	#ifndef lint
a9e5f6cf	2	static char sccsid[] = "@(#)boggle.c 4.2 %G%";
4dba9a68 SL	3	#endif
	4
	5	#include <ctype.h>
	6	#include <errno.h>
	7	#include <setjmp.h>
	8	#include <sgtty.h>
	9	#include <signal.h>
	10	#include <stdio.h>
	11
	12	/* basic parameters */
	13	#define N 4
	14	#define SSIZE 200
	15	#define MAXWORDS 1000
	16	#define CWIDTH 10
	17	#define LWIDTH 80
	18
	19	/* parameters defined in terms of above */
	20	#define BSIZE (N*N)
	21	#define row(x) (x/N)
	22	#define col(x) (x%N)
	23
	24	/* word being searched for */
	25	int wlength;
	26	int numsame;
	27	char wbuff [BSIZE+1];
	28
	29	/* tty and process control */
	30	extern int errno;
	31	int status;
	32	int pipefd[2];
	33	int super = 0;
	34	int delct = 1;
	35	int zero = 0;
	36	int master = 1;
	37	int column;
	38	int *timept;
	39	int timeint[] = {60,60,50,7,1,1,1,0};
	40	long timein;
	41	extern long int time();
	42	struct sgttyb origttyb, tempttyb;
	43	int ctlecho = 0;
	44	int lctlech = LCTLECH;
	45	jmp_buf env;
	46
	47	/* monitoring variables */
	48	int games;
	49	int logfile = -1;
	50	long logloc;
	51	char logbuff[100] = {"inst\t"};
	52	extern char ctime(), getlogin();
	53	extern long lseek();
	54
	55	/* dictionary interface */
	56	char defname[] = "/usr/games/bogdict";
	57	char *dictname = &defname[0];
	58	FILE *dict;
	59
	60	/* structures for doing matching */
	61	struct frame {
	62	struct frame *parent;
	63	int place;
	64	};
	65	struct frame stack [SSIZE];
	66	struct frame *level [BSIZE+1];
67
68	/* the board and subsidiary structures */
69	char present [BSIZE+1];
70	char board [BSIZE];
71	char olink [BSIZE];
72	char adj [BSIZE+1][BSIZE];
73	char occurs [26];
74
75	/* the boggle cubes */
76	char *cube [BSIZE] = {
77	"forixb", "moqabj", "gurilw", "setupl",
78	"cmpdae", "acitao", "slcrae", "romash",
79	"nodesw", "hefiye", "onudtk", "tevign",
80	"anedvz", "pinesh", "abilyt", "gkyleu"
81	};
82
83
84	/* storage for words found */
85	int ubotch, ustart, wcount;
86	char *word [MAXWORDS];
87	char *freesp;
88	char space[10000];
89
90	endline ()
91	{
92	if (column != 0) {
93	putchar('\n');
94	column = 0;
95	}
96	}
97
98	timeout ()
99	{
100	if (*timept > 0) {
101	signal (SIGALRM, timeout);
102	alarm(*timept++);
103	}
104	putchar('\007');
105	}
106
107	interrupt ()
108	{
109	signal(SIGINT, interrupt);
110	if (delct++ >= 1)
111	longjmp(env, 1);
112	timept = &zero;
113	}
114
115	goodbye (stat)
116	int stat;
117	{
118	if (master != 0) {
119	wait(&status);
120	if ( ctlecho & LCTLECH ) {
121	ioctl( fileno(stdin), TIOCLBIS, &lctlech );
122	}
123	stty(fileno(stdin), &origttyb);
124	}
125	exit(stat);
126	}
127
128	clearscreen ()
129	{
130	stty (fileno(stdin), &tempttyb);
131	printf("\n\033\f\r");
132	}
133
134	compare (a, b)
135	char a, b;
136	{
137	return(wordcomp(a, b));
138	}
139
140	wordcomp (p, q)
141	register char p, q;
142	{
143	if (p=='0' && q!='0')
144	return(-1);
145	if (p!='0' && q=='0')
146	return(1);
147	while (++p == ++q && isalpha(*p)) ;
148	if (!isalpha(*p))
149	return(-isalpha(*q));
150	if (!isalpha(*q))
151	return(1);
152	return(p-q);
153	}
154
155	printinst ()
156	{
157	stty (fileno(stdin), &tempttyb);
158	printf("instructions?");
159	if (getchar() == 'y') {
160	clearscreen();
161	printf(" The object of Boggle (TM Parker Bros.) is to find, within 3\n");
162	printf("minutes, as many words as possible in a 4 by 4 grid of letters. Words\n");
163	printf("may be formed from any sequence of 3 or more adjacent letters in the\n");
164	printf("grid. The letters may join horizontally, vertically, or diagonally.\n");
165	printf("However, no position in the grid may be used more than once within any\n");
166	printf("one word. In competitive play amongst humans, each player is given\n");
167	printf("credit for those of his words which no other player has found.\n");
168	printf(" This program is intended for people wishing to sharpen their\n");
169	printf("skills at Boggle. If you invoke the program with 4 arguments of 4\n");
170	printf("letters each, (e.g. \"boggle appl epie moth erhd\") the program forms the\n");
171	printf("obvious Boggle grid and lists all the words from /usr/dict/words found\n");
172	printf("therein. If you invoke the program without arguments, it will generate\n");
173	printf("a board for you, let you enter words for 3 minutes, and then tell you\n");
174	printf("how well you did relative to /usr/dict/words.\n");
175	printf(" In interactive play, enter your words separated by spaces, tabs,\n");
176	printf("or newlines. A bell will ring when there is 2:00, 1:00, 0:10, 0:02,\n");
177	printf("0:01, and 0:00 time left. You may complete any word started before the\n");
178	printf("expiration of time. You can surrender before time is up by hitting\n");
179	printf("'break'. While entering words, your erase character is only effective\n");
180	printf("within the current word and your line kill character is ignored.\n");
181	printf(" Advanced players may wish to invoke the program with 1 or 2 +'s as\n");
a9e5f6cf	182	printf("the first argument. The first + removes the restriction that positions\n");
4dba9a68 SL	183	printf("can only be used once in each word. The second + causes a position to\n");
	184	printf("be considered adjacent to itself as well as its (up to) 8 neighbors.\n");
	185	printf("Hit any key to begin.\n");
	186	stty (fileno(stdin), &tempttyb);
	187	getchar();
	188	}
	189	stty (fileno(stdin), &tempttyb);
	190	}
	191
	192	setup ()
	193	{
	194	register int i, j;
	195	int rd, cd, k;
	196	for (i=0; i<BSIZE; i++) {
	197	adj[i][i] = super>=2 ? 1 : 0;
	198	adj[BSIZE][i] = 1;
	199	for (j=0; j<i; j++) {
	200	rd = row(i)-row(j);
	201	cd = col(i)-col(j);
	202	k = 0;
	203	switch (rd) {
	204	case -1:
	205	case 1:
	206	if (-1<=cd && cd<=1)
	207	k = 1;
	208	break;
	209	case 0:
	210	if (cd==-1 \|\| cd==1)
	211	k = 1;
	212	break;
	213	}
	214	adj[i][j] = adj[j][i] = k;
	215	}
	216	}
	217	stack[0].parent = &stack[0];
	218	stack[0].place = BSIZE;
	219	level[0] = &stack[0];
	220	level[1] = &stack[1];
	221	}
	222
	223	makelists ()
	224	{
	225	register int i, c;
	226	for (i=0; i<26; i++)
	227	occurs[i] = BSIZE;
	228	for (i=0; i<BSIZE; i++) {
	229	c = board[i];
	230	olink[i] = occurs[c-'a'];
	231	occurs[c-'a'] = i;
	232	}
	233	}
	234
	235	genboard ()
	236	{
	237	register int i, j;
	238	for (i=0; i<BSIZE; i++)
	239	board[i] = 0;
	240	for (i=0; i<BSIZE; i++) {
	241	j = rand()%BSIZE;
	242	while (board[j] != 0)
	243	j = (j+1)%BSIZE;
	244	board[j] = cube[i][rand()%6];
	245	}
	246	}
247
248	printboard ()
249	{
250	register int i, j;
251	for (i=0; i<N; i++) {
252	printf("\t\t\t\t\b\b");
253	for (j=0; j<N; j++) {
254	putchar ((putchar(board[i*N+j]) == 'q') ? 'u' : ' ');
255	putchar(' ');
256	}
257	putchar('\n');
258	}
259	putchar('\n');
260	}
261
262	getdword ()
263	{
264	/* input: numsame = # chars same as last word */
265	/* output: numsame = # same chars for next word */
266	/* word in wbuff[0]...wbuff[wlength-1] */
267	register int c;
268	register char *p;
269	if (numsame == EOF)
270	return (0);
271	p = &wbuff[numsame]+1;
272	while ((*p++ = c = getc(dict)) != EOF && isalpha(c)) ;
273	numsame = c;
274	wlength = p - &wbuff[2];
275	return (1);
276	}
277
278	getuword ()
279	{
280	int c;
281	register char p, q, *r;
282	numsame = 0;
283	while (*timept>0 && (isspace(c=getchar()) \|\| c==EOF));
284	if (*timept == 0)
285	return(0);
286	word[wcount++] = freesp;
287	*freesp++ = '0';
288	r = &wbuff[1];
289	q = p = freesp;
290	*p++ = c;
291	while (!isspace(c = getchar())) {
292	if (c == EOF)
293	continue;
294	if (c == origttyb.sg_erase) {
295	if (p > q)
296	p--;
297	continue;
298	}
299	*p++ = c;
300	}
301	freesp = p;
302	for (p=q; p<freesp && r<&wbuff[BSIZE]; )
303	if (islower(c = p++) && (r++ = q++ = c) == 'q' && p == 'u')
304	p++;
305	*(freesp = q) = '0';
306	wlength = r-&wbuff[1];
307	return(1);
308	}
309
310	aputuword (ways)
311	int ways;
312	{
313	word[wcount-1] = ways>=10 ? '' : '0'+ways;
314	}
315
316	aputword (ways)
317	int ways;
318	{
319	/* store (wbuff, ways) in next slot in space */
320	register int i;
321	freesp++ = ways>=10 ? '' : '0'+ways;
322	for (i=1; i<= wlength; i++)
323	*freesp++ = wbuff[i];
324	word[++wcount] = freesp;
325	}
326
327	tputword (ways)
328	int ways;
329	{
330	/* print (wbuff, ways) on terminal */
331	wbuff[wlength+1] = '0';
332	wbuff[0] = ways>=10 ? '*' : '0'+ways;
333	outword(&wbuff[0]);
334	}
335
336	outword (p)
337	register char *p;
338	{
339	register int newcol;
340	register char *q;
341	for (q=p+1; isalpha(*q); ) {
342	putchar(*q);
343	if (*q++ == 'q') {
344	putchar('u');
345	column++;
346	}
347	}
348	column += q-p-1;
349	if (column > LWIDTH-CWIDTH) {
350	putchar('\n');
351	column = 0;
352	return;
353	}
354	newcol = ((column+CWIDTH)/CWIDTH)*CWIDTH;
355	while (((column+8)/8)*8 <= newcol) {
356	putchar('\t');
357	column = ((column+8)/8)*8;
358	}
359	while (column < newcol) {
360	putchar(' ');
361	column++;
362	}
363	}
364
365	printdiff ()
366	{
367	register int c, d, u;
368	char both, donly, uonly;
369	word[wcount] = freesp;
370	*freesp = '0';
371	both = donly = uonly = column = d = 0;
372	u = ustart;
373	while (d < ubotch) {
374	c = u<wcount ? wordcomp (word[d], word[u]) : -1;
375	if (c == 0) {
376	/* dict and user found same word */
377	if (both == 0) {
378	both = 1;
379	printf("\t\t\t we both found:\n");
380	}
381	outword(word[d]);
382	word[d++] = NULL;
383	word[u++] = NULL;
384	} else if (c < 0) {
385	/* dict found it, user didn't */
386	donly = 1;
387	d++;
388	} else {
389	/* user found it, dict didn't */
390	uonly = 1;
391	u++;
392	}
393	}
394	endline();
395	if (donly) {
396	printf("\n\t\t\tI alone found these:\n");
397	for (d=0; d<ubotch; d++)
398	if (word[d] != NULL)
399	outword(word[d]);
400	endline();
401	}
402	if (uonly) {
403	printf("\n\t\t\tyou alone found these:\n");
404	for (u=ustart; u<wcount; u++)
405	if (word[u] != NULL)
406	outword(word[u]);
407	endline();
408	}
409	if (ubotch < ustart) {
410	printf("\n\t\t\t you botched these:\n");
411	for (u=ubotch; u<ustart; u++)
412	outword(word[u]);
413	endline();
414	}
415	}
416
417	numways (leaf, last)
418	register struct frame *leaf;
419	struct frame *last;
420	{
421	int count;
422	register char *p;
423	register struct frame *node;
424	if (super > 0)
425	return(last-leaf);
426	count = 0;
427	present[BSIZE] = 1;
428	while (leaf < last) {
429	for (p = &present[0]; p < &present[BSIZE]; *p++ = 0);
430	for (node = leaf; present[node->place]++ == 0; node = node->parent);
431	if (node == &stack[0])
432	count++;
433	leaf++;
434	}
435	return(count);
436	}
437
438	evalboard (getword, putword)
439	int (getword)(), (putword)();
440	{
441	register struct frame *top;
442	register int l, q;
443	int fo, found;
444	struct frame parent, lastparent;
445	char *padj;
446
447	numsame = found = 0;
448	makelists ();
449
450	while (1) {
451	l = numsame;
452	if (!(*getword) ())
453	break;
454	top = level[l+1];
455
456	while (1) {
457	level[l+1] = lastparent = top;
458	/* wbuff[1]...wbuff[l] have been matched */
459	/* level[0],...,level[l] of tree built */
460	if (l == wlength) {
461	if (wlength >= 3 && (q = numways(level[l], top)) != 0) {
462	(*putword) (q);
463	found++;
464	}
465	l = BSIZE+1;
466	break;
467	}
468	if ((fo = occurs[wbuff[++l]-'a']) == BSIZE)
469	break;
470	/* wbuff[1]...wbuff[l-1] have been matched */
471	/* level[0],...,level[l-1] of tree built */
472	for (parent=level[l-1]; parent<lastparent; parent++) {
473	padj = &adj[parent->place][0];
474	for (q=fo; q!=BSIZE; q=olink[q])
475	if (padj[q]) {
476	top->parent = parent;
477	top->place = q;
478	if (++top >= &stack[SSIZE]) {
479	printf("stack overflow\n");
480	goodbye(1);
481	}
482	}
483	}
484	/* were any nodes added? */
485	if (top == lastparent)
486	break;
487	}
488
489	/* advance until first l characters of next word are different */
490	while (numsame >= l && (*getword)()) ;
491	}
492	return(found);
493	}
494
495	main (argc, argv)
496	int argc;
497	char **argv;
498	{
499	char *q;
500	register char *p;
501	register int i, c;
502
503	gtty (fileno(stdin), &origttyb);
504	setbuf(stdin, NULL);
505	tempttyb = origttyb;
506	if (setjmp(env) != 0)
507	goodbye(0);
508	signal (SIGINT, interrupt);
509	timein = time(0L);
510	if (argv[0][0] != 'a' && (logfile = open("/usr/games/boglog", 1)) >= 0) {
511	p = &logbuff[5];
512	q = getlogin();
513	while (p++ = q++);
514	p[-1] = '\t';
515	q = ctime(&timein);
516	while (p++ = q++);
517	logloc = lseek(logfile, 0L, 2);
518	write(logfile, &logbuff[0], p-&logbuff[1]);
519	}
520	if ((dict = fopen(dictname, "r")) == NULL) {
521	printf("can't open %s\n", dictname);
522	goodbye (2);
523	}
524	while ( argc > 1 && ( argv[1][0] == '+' \|\| argv[1][0] == '-' ) ) {
525	if (argv[1][0]=='+') {
526	while(*(argv[1]++) == '+')
527	super++;
528	argc--;
529	argv++;
530	}
531	if ( argv[1][0] == '-' ) {
532	timeint[0] = 60 * ( atol( &argv[1][1] ) - 2 );
533	if ( timeint[0] <= 0 ) {
534	timeint[0] = 60;
535	}
536	argc--;
537	argv++;
538	}
539	}
540	setup ();
541	switch (argc) {
542	default: punt:
543	printf("usage: boggle [+[+]] [row1 row2 row3 row4]\n");
544	goodbye (3);
545	case 5:
546	for (i=0; i<BSIZE; i++) {
547	board[i] = c = argv[row(i)+1][col(i)];
548	if (!islower(c)) {
549	printf("bad board\n");
550	goto punt;
551	}
552	}
553	printboard();
554	column = 0;
555	evalboard(getdword, tputword);
556	endline();
557	if (logfile >= 0) {
558	strncpy(&logbuff[0], "eval", 4);
559	lseek(logfile, logloc, 0);
560	write(logfile, &logbuff[0], 4);
561	}
562	goodbye(0);
563	case 1:
564	tempttyb.sg_flags \|= CBREAK;
565	if ( ioctl( fileno(stdin), TIOCLGET, &ctlecho ) == 0 ) {
566	if ( ctlecho & LCTLECH ) {
567	ioctl( fileno(stdin), TIOCLBIC, &lctlech );
568	}
569	}
570	printinst();
571	srand((int) timein);
572	while (setjmp(env) == 0) {
573	errno = 0;
574	if (pipe(&pipefd[0]) != 0) {
575	printf("can't create pipe\n");
576	goodbye(4);
577	}
578	genboard();
579	delct = wcount = 0;
580	word[0] = freesp = &space[0];
581	if ((master = fork()) == 0) {
582	close(pipefd[0]);
583	clearscreen();
584	printboard();
585	signal(SIGALRM, timeout);
586	timept = &timeint[0];
587	alarm(*timept++);
588	evalboard(getuword, aputuword);
589	clearscreen();
590	qsort(&word[0], wcount, sizeof (int), compare);
591	for (i=0; i<wcount; i++)
592	if (i==0 \|\| wordcomp(word[i], word[i-1])!=0) {
593	p = word[i];
594	while (isalpha(*++p)) ;
595	write (pipefd[1], word[i], p-word[i]);
596	}
597	close(pipefd[1]);
598	goodbye(0);
599	}
600	close(pipefd[1]);
601	rewind(dict);
602	getc(dict);
603	evalboard(getdword, aputword);
604	p = freesp;
605	while ((i = read(pipefd[0], freesp, 512)) != 0) {
606	if (i < 0)
607	if (errno != EINTR)
608	break;
609	else
610	i = 0;
611	freesp += i;
612	}
613	close(pipefd[0]);
614	ustart = ubotch = wcount;
615	while (p < freesp) {
616	word[wcount++] = p;
617	if (*p == '0')
618	ustart = wcount;
619	while (isalpha(*++p));
620	}
621	wait(&status);
622	if (status != 0)
623	goodbye (5);
624	delct = 1;
625	printdiff();
626	printboard();
627	games++;
628	if (logfile >= 0) {
629	sprintf(&logbuff[0], "%4d", games);
630	lseek(logfile, logloc, 0);
631	write(logfile, &logbuff[0], 4);
632	}
633	stty (fileno(stdin), &tempttyb);
634	printf("\nanother game?");
635	if (getchar() != 'y') {
636	putchar('\n');
637	break;
638	}
639	stty (fileno(stdin), &tempttyb);
640	}
641	goodbye(0);
642	}
643	}