1 /* $NetBSD: bog.c,v 1.29 2014/03/22 23:39:04 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
43 static char sccsid[] = "@(#)bog.c 8.2 (Berkeley) 5/4/95";
44 #else
45 __RCSID("$NetBSD: bog.c,v 1.29 2014/03/22 23:39:04 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
61 static char *batchword(FILE *);
62 static void playgame(void);
63 static int validword(const char *);
64 static void checkdict(void);
65 static void newgame(const char *);
66 static int compar(const void *, const void *);
67 static void clearwordpath(int full);
68 static void usage(void) __dead;
69
70 struct 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 */
80 static 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
100 static int letter_map[26][16];
101
102 char board[17];
103 int wordpath[MAXWORDLEN + 1];
104 int wordlen; /* Length of last word returned by nextword() */
105 int usedbits;
106
107 const char *pword[MAXPWORDS];
108 static char pwords[MAXPSPACE], *pwordsp;
109 int npwords;
110
111 const char *mword[MAXMWORDS];
112 static char mwords[MAXMSPACE], *mwordsp;
113 int nmwords;
114
115 int ngames = 0;
116 int tnmwords = 0, tnpwords = 0;
117
118 #include <setjmp.h>
119 jmp_buf env;
120
121 time_t start_t;
122 int debug;
123 int tlimit;
124
125 static FILE *dictfp;
126 static int batch;
127 static int minlength;
128 static int reuse;
129
130 int
main(int argc,char * argv[])131 main(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 */
287 static char *
batchword(FILE * fp)288 batchword(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 */
309 static void
playgame(void)310 playgame(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
397 timesup: ;
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 */
425 int
checkword(const char * word,int prev,int * path)426 checkword(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 */
507 static int
validword(const char * word)508 validword(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 */
541 static void
checkdict(void)542 checkdict(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 */
618 static void
newgame(const char * b)619 newgame(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 */
690 static void
clearwordpath(int full)691 clearwordpath(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
701 static int
compar(const void * p,const void * q)702 compar(const void *p, const void *q)
703 {
704 return (strcmp(*(const char *const *)p, *(const char *const *)q));
705 }
706
707 static void
usage(void)708 usage(void)
709 {
710 (void) fprintf(stderr,
711 "usage: %s [-bd] [-s#] [-t#] [-w#] [+[+]] [boardspec]\n",
712 getprogname());
713 exit(1);
714 }
715