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