1 /* $OpenBSD: bog.c,v 1.33 2016/09/12 20:11:10 tb 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
49 static void init(void);
50 static void init_adjacencies(void);
51 static int compar(const void *, const void *);
52
53 struct dictindex dictindex[26];
54
55 static int **adjacency, **letter_map;
56
57 char *board;
58 int wordpath[MAXWORDLEN + 1];
59 int wordlen; /* Length of last word returned by nextword() */
60 int usedbits;
61 unsigned int ncubes;
62 int grid = 4;
63
64 char **pword, *pwords, *pwordsp;
65 int npwords, maxpwords = MAXPWORDS, maxpspace = MAXPSPACE;
66
67 char **mword, *mwords, *mwordsp;
68 int nmwords, maxmwords = MAXMWORDS, maxmspace = MAXMSPACE;
69
70 int ngames = 0;
71 int tnmwords = 0, tnpwords = 0;
72
73 jmp_buf env;
74
75 time_t start_t;
76
77 static FILE *dictfp;
78
79 int batch;
80 int challenge;
81 int debug;
82 int minlength;
83 int reuse;
84 int selfuse;
85 int tlimit;
86
87 int
main(int argc,char * argv[])88 main(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 printf("%s\n", p);
161 return 0;
162 }
163 setup();
164 prompt("Loading the dictionary...");
165 if ((dictfp = opendict(DICT)) == NULL) {
166 warn("%s", DICT);
167 cleanup();
168 return 1;
169 }
170 #ifdef LOADDICT
171 if (loaddict(dictfp) < 0) {
172 warnx("can't load %s", DICT);
173 cleanup();
174 return 1;
175 }
176 fclose(dictfp);
177 dictfp = NULL;
178 #endif
179 if (loadindex(DICTINDEX) < 0) {
180 warnx("can't load %s", DICTINDEX);
181 cleanup();
182 return 1;
183 }
184
185 prompt("Type <space> to begin...");
186 while (inputch() != ' ');
187
188 for (done = 0; !done;) {
189 newgame(bspec);
190 bspec = NULL; /* reset for subsequent games */
191 playgame();
192 prompt("Type <space> to continue, any cap to quit...");
193 delay(10); /* wait for user to quit typing */
194 flushin(stdin);
195 for (;;) {
196 ch = inputch();
197 if (ch == '\033')
198 findword();
199 else if (ch == '\014' || ch == '\022') /* ^l or ^r */
200 redraw();
201 else {
202 if (isupper(ch)) {
203 done = 1;
204 break;
205 }
206 if (ch == ' ')
207 break;
208 }
209 }
210 }
211 cleanup();
212 return 0;
213 }
214
215 /*
216 * Read a line from the given stream and check if it is legal
217 * Return a pointer to a legal word or a null pointer when EOF is reached
218 */
219 char *
batchword(FILE * fp)220 batchword(FILE *fp)
221 {
222 int *p, *q;
223 char *w;
224
225 q = &wordpath[MAXWORDLEN + 1];
226 p = wordpath;
227 while (p < q)
228 *p++ = -1;
229 while ((w = nextword(fp)) != NULL) {
230 if (wordlen < minlength)
231 continue;
232 p = wordpath;
233 while (p < q && *p != -1)
234 *p++ = -1;
235 usedbits = 0;
236 if (checkword(w, -1, wordpath) != -1)
237 return (w);
238 }
239 return (NULL);
240 }
241
242 /*
243 * Play a single game
244 * Reset the word lists from last game
245 * Keep track of the running stats
246 */
247 void
playgame(void)248 playgame(void)
249 {
250 int i, *p, *q;
251 time_t t;
252 char buf[MAXWORDLEN + 1];
253
254 ngames++;
255 npwords = 0;
256 pwordsp = pwords;
257 nmwords = 0;
258 mwordsp = mwords;
259
260 time(&start_t);
261
262 q = &wordpath[MAXWORDLEN + 1];
263 p = wordpath;
264 while (p < q)
265 *p++ = -1;
266 showboard(board);
267 startwords();
268 if (setjmp(env)) {
269 badword();
270 goto timesup;
271 }
272
273 while (1) {
274 if (get_line(buf) == NULL) {
275 if (feof(stdin))
276 clearerr(stdin);
277 break;
278 }
279 time(&t);
280 if (t - start_t >= tlimit) {
281 badword();
282 break;
283 }
284 if (buf[0] == '\0') {
285 int remaining;
286
287 remaining = tlimit - (int) (t - start_t);
288 snprintf(buf, sizeof(buf),
289 "%d:%02d", remaining / 60, remaining % 60);
290 showstr(buf, 1);
291 continue;
292 }
293 if (strlen(buf) < (size_t)minlength) {
294 badword();
295 continue;
296 }
297
298 p = wordpath;
299 while (p < q && *p != -1)
300 *p++ = -1;
301 usedbits = 0;
302
303 if (checkword(buf, -1, wordpath) < 0)
304 badword();
305 else {
306 if (debug) {
307 printf("[");
308 for (i = 0; wordpath[i] != -1; i++)
309 printf(" %d", wordpath[i]);
310 printf(" ]\n");
311 }
312 for (i = 0; i < npwords; i++) {
313 if (strcmp(pword[i], buf) == 0)
314 break;
315 }
316 if (i != npwords) { /* already used the word */
317 badword();
318 showword(i);
319 }
320 else if (!validword(buf))
321 badword();
322 else {
323 int len;
324
325 if (npwords == maxpwords - 1) {
326 maxpwords += MAXPWORDS;
327 pword = realloc(pword,
328 maxpwords * sizeof(char *));
329 if (pword == NULL) {
330 cleanup();
331 errx(1, "%s", strerror(ENOMEM));
332 }
333 }
334 len = strlen(buf) + 1;
335 if (pwordsp + len >= &pwords[maxpspace]) {
336 maxpspace += MAXPSPACE;
337 pwords = realloc(pwords, maxpspace);
338 if (pwords == NULL) {
339 cleanup();
340 errx(1, "%s", strerror(ENOMEM));
341 }
342 }
343 pword[npwords++] = pwordsp;
344 memcpy(pwordsp, buf, len);
345 pwordsp += len;
346 addword(buf);
347 }
348 }
349 }
350
351 timesup: ;
352
353 /*
354 * Sort the player's words and terminate the list with a null
355 * entry to help out checkdict()
356 */
357 qsort(pword, npwords, sizeof(pword[0]), compar);
358 pword[npwords] = NULL;
359
360 /*
361 * These words don't need to be sorted since the dictionary is sorted
362 */
363 checkdict();
364
365 tnmwords += nmwords;
366 tnpwords += npwords;
367
368 results();
369 }
370
371 /*
372 * Check if the given word is present on the board, with the constraint
373 * that the first letter of the word is adjacent to square 'prev'
374 * Keep track of the current path of squares for the word
375 * A 'q' must be followed by a 'u'
376 * Words must end with a null
377 * Return 1 on success, -1 on failure
378 */
379 int
checkword(char * word,int prev,int * path)380 checkword(char *word, int prev, int *path)
381 {
382 char *p, *q;
383 int i, *lm;
384
385 if (debug) {
386 printf("checkword(%s, %d, [", word, prev);
387 for (i = 0; wordpath[i] != -1; i++)
388 printf(" %d", wordpath[i]);
389 printf(" ]\n");
390 }
391
392 if (*word == '\0')
393 return (1);
394
395 lm = letter_map[*word - 'a'];
396
397 if (prev == -1) {
398 char subword[MAXWORDLEN + 1];
399
400 /*
401 * Check for letters not appearing in the cube to eliminate some
402 * recursive calls
403 * Fold 'qu' into 'q'
404 */
405 p = word;
406 q = subword;
407 while (*p != '\0') {
408 if (*letter_map[*p - 'a'] == -1)
409 return (-1);
410 *q++ = *p;
411 if (*p++ == 'q') {
412 if (*p++ != 'u')
413 return (-1);
414 }
415 }
416 *q = '\0';
417 while (*lm != -1) {
418 *path = *lm;
419 usedbits |= (1 << *lm);
420 if (checkword(subword + 1, *lm, path + 1) > 0)
421 return (1);
422 usedbits &= ~(1 << *lm);
423 lm++;
424 }
425 return (-1);
426 }
427
428 /*
429 * A cube is only adjacent to itself in the adjacency matrix if selfuse
430 * was set, so a cube can't be used twice in succession if only the
431 * reuse flag is set
432 */
433 for (i = 0; lm[i] != -1; i++) {
434 if (adjacency[prev][lm[i]]) {
435 int used;
436
437 used = 1 << lm[i];
438 /*
439 * If necessary, check if the square has already
440 * been used.
441 */
442 if (!reuse && !selfuse && (usedbits & used))
443 continue;
444 *path = lm[i];
445 usedbits |= used;
446 if (checkword(word + 1, lm[i], path + 1) > 0)
447 return (1);
448 usedbits &= ~used;
449 }
450 }
451 *path = -1; /* in case of a backtrack */
452 return (-1);
453 }
454
455 /*
456 * A word is invalid if it is not in the dictionary
457 * At this point it is already known that the word can be formed from
458 * the current board
459 */
460 int
validword(char * word)461 validword(char *word)
462 {
463 int j;
464 char *q, *w;
465
466 j = word[0] - 'a';
467 if (dictseek(dictfp, dictindex[j].start, SEEK_SET) < 0) {
468 cleanup();
469 errx(1, "seek error in validword()");
470 }
471
472 while ((w = nextword(dictfp)) != NULL) {
473 int ch;
474
475 if (*w != word[0]) /* end of words starting with word[0] */
476 break;
477 q = word;
478 while ((ch = *w++) == *q++ && ch != '\0')
479 ;
480 if (*(w - 1) == '\0' && *(q - 1) == '\0')
481 return (1);
482 }
483 if (dictfp != NULL && feof(dictfp)) /* Special case for z's */
484 clearerr(dictfp);
485 return (0);
486 }
487
488 /*
489 * Check each word in the dictionary against the board
490 * Delete words from the machine list that the player has found
491 * Assume both the dictionary and the player's words are already sorted
492 */
493 void
checkdict(void)494 checkdict(void)
495 {
496 char **pw, *w;
497 int i;
498 int prevch, previndex, *pi, *qi, st;
499
500 mwordsp = mwords;
501 nmwords = 0;
502 pw = pword;
503 prevch ='a';
504 qi = &wordpath[MAXWORDLEN + 1];
505
506 dictseek(dictfp, 0L, SEEK_SET);
507 while ((w = nextword(dictfp)) != NULL) {
508 if (wordlen < minlength)
509 continue;
510 if (*w != prevch) {
511 /*
512 * If we've moved on to a word with a different first
513 * letter then we can speed things up by skipping all
514 * words starting with a letter that doesn't appear in
515 * the cube.
516 */
517 i = (int) (*w - 'a');
518 while (i < 26 && letter_map[i][0] == -1)
519 i++;
520 if (i == 26)
521 break;
522 previndex = prevch - 'a';
523 prevch = i + 'a';
524 /*
525 * Fall through if the word's first letter appears in
526 * the cube (i.e., if we can't skip ahead), otherwise
527 * seek to the beginning of words in the dictionary
528 * starting with the next letter (alphabetically)
529 * appearing in the cube and then read the first word.
530 */
531 if (i != previndex + 1) {
532 if (dictseek(dictfp,
533 dictindex[i].start, SEEK_SET) < 0) {
534 cleanup();
535 errx(1, "seek error in checkdict()");
536 }
537 continue;
538 }
539 }
540
541 pi = wordpath;
542 while (pi < qi && *pi != -1)
543 *pi++ = -1;
544 usedbits = 0;
545 if (checkword(w, -1, wordpath) == -1)
546 continue;
547
548 st = 1;
549 while (*pw != NULL && (st = strcmp(*pw, w)) < 0)
550 pw++;
551 if (st == 0) /* found it */
552 continue;
553 if (nmwords == maxmwords - 1) {
554 maxmwords += MAXMWORDS;
555 mword = realloc(mword, maxmwords * sizeof(char *));
556 if (mword == NULL) {
557 cleanup();
558 errx(1, "%s", strerror(ENOMEM));
559 }
560 }
561 if (mwordsp + wordlen + 1 >= &mwords[maxmspace]) {
562 maxmspace += MAXMSPACE;
563 mwords = realloc(mwords, maxmspace);
564 if (mwords == NULL) {
565 cleanup();
566 errx(1, "%s", strerror(ENOMEM));
567 }
568 }
569 mword[nmwords++] = mwordsp;
570 memcpy(mwordsp, w, wordlen + 1);
571 mwordsp += wordlen + 1;
572 }
573 }
574
575 /*
576 * Crank up a new game
577 * If the argument is non-null then it is assumed to be a legal board spec
578 * in ascending cube order, oth. make a random board
579 */
580 void
newgame(char * b)581 newgame(char *b)
582 {
583 unsigned int i;
584 int p, q;
585 const char *tmp, **cubes;
586 int *lm[26];
587 const char chal_cube[] = "iklmqu"; /* challenge cube */
588 static const char *cubes4[] = {
589 "ednosw", "aaciot", "acelrs", "ehinps",
590 "eefhiy", "elpstu", "acdemp", "gilruw",
591 "egkluy", "ahmors", "abilty", "adenvz",
592 "bfiorx", "dknotu", "abjmoq", "egintv"
593 };
594 static const char *cubes5[] = {
595 "aaafrs", "aaeeee", "aafirs", "adennn", "aeeeem",
596 "aeegmu", "aegmnn", "afirsy", "bjkqxz", "ccnstw",
597 "ceiilt", "ceilpt", "ceipst", "ddlnor", "dhhlor",
598 "dhhnot", "dhlnor", "eiiitt", "emottt", "ensssu",
599 "fiprsy", "gorrvw", "hiprry", "nootuw", "ooottu"
600 };
601
602 cubes = grid == 4 ? cubes4 : cubes5;
603 if (b == NULL) {
604 /* Shuffle the cubes using Fisher-Yates (aka Knuth P). */
605 p = ncubes;
606 while (--p) {
607 q = (int)arc4random_uniform(p + 1);
608 tmp = cubes[p];
609 cubes[p] = cubes[q];
610 cubes[q] = tmp;
611 }
612
613 /* Build the board by rolling each cube. */
614 for (i = 0; i < ncubes; i++)
615 board[i] = cubes[i][arc4random_uniform(6)];
616
617 /*
618 * For challenge mode, roll chal_cube and replace a random
619 * cube with its value. Set the high bit to distinguish it.
620 */
621 if (challenge) {
622 i = arc4random_uniform(ncubes);
623 board[i] = SETHI(chal_cube[arc4random_uniform(6)]);
624 }
625 } else {
626 for (i = 0; i < ncubes; i++)
627 board[i] = b[i];
628 }
629 board[ncubes] = '\0';
630
631 /*
632 * Set up the map from letter to location(s)
633 * Each list is terminated by a -1 entry
634 */
635 for (i = 0; i < 26; i++) {
636 lm[i] = letter_map[i];
637 *lm[i] = -1;
638 }
639
640 for (i = 0; i < ncubes; i++) {
641 int j;
642
643 j = (int) (SEVENBIT(board[i]) - 'a');
644 *lm[j] = i;
645 *(++lm[j]) = -1;
646 }
647
648 if (debug) {
649 for (i = 0; i < 26; i++) {
650 int ch, j;
651
652 printf("%c:", 'a' + i);
653 for (j = 0; (ch = letter_map[i][j]) != -1; j++)
654 printf(" %d", ch);
655 printf("\n");
656 }
657 }
658
659 }
660
661 static int
compar(const void * p,const void * q)662 compar(const void *p, const void *q)
663 {
664 return (strcmp(*(const char *const*)p, *(const char *const*)q));
665 }
666
667 /*
668 * Allocate and initialize data structures.
669 */
670 static void
init(void)671 init(void)
672 {
673 int i;
674
675 if (minlength == -1)
676 minlength = grid - 1;
677 init_adjacencies();
678 board = malloc(ncubes + 1);
679 if (board == NULL)
680 err(1, NULL);
681 letter_map = calloc(26, sizeof(int *));
682 if (letter_map == NULL)
683 err(1, NULL);
684 for (i = 0; i < 26; i++) {
685 letter_map[i] = calloc(ncubes, sizeof(int));
686 if (letter_map[i] == NULL)
687 err(1, NULL);
688 }
689 pword = calloc(maxpwords, sizeof(char *));
690 if (pword == NULL)
691 err(1, NULL);
692 pwords = malloc(maxpspace);
693 if (pwords == NULL)
694 err(1, NULL);
695 mword = calloc(maxmwords, sizeof(char *));
696 if (mword == NULL)
697 err(1, NULL);
698 mwords = malloc(maxmspace);
699 if (mwords == NULL)
700 err(1, NULL);
701 }
702
703 #define SET_ADJ(r) do { \
704 if (col > 0) \
705 adj[r - 1] = 1; \
706 adj[r] = 1; \
707 if (col + 1 < grid) \
708 adj[r + 1] = 1; \
709 } while(0)
710
711 /*
712 * Compute adjacency matrix for the grid
713 */
714 static void
init_adjacencies(void)715 init_adjacencies(void)
716 {
717 unsigned int cube;
718 int row, col, *adj;
719
720 adjacency = calloc(ncubes, sizeof(int *));
721 if (adjacency == NULL)
722 err(1, NULL);
723
724 /*
725 * Fill in adjacencies. This is an ncubes x ncubes matrix where
726 * the position X,Y is set to 1 if cubes X and Y are adjacent.
727 */
728 for (cube = 0; cube < ncubes; cube++) {
729 adj = adjacency[cube] = calloc(ncubes, sizeof(int));
730 if (adj == NULL)
731 err(1, NULL);
732
733 row = cube / grid;
734 col = cube % grid;
735
736 /* this row */
737 SET_ADJ(cube);
738 if (!selfuse)
739 adj[cube] = 0;
740
741 /* prev row */
742 if (row > 0)
743 SET_ADJ(cube - grid);
744
745 /* next row */
746 if (row + 1 < grid)
747 SET_ADJ(cube + grid);
748 }
749 }
750
751 void
usage(void)752 usage(void)
753 {
754 fprintf(stderr, "usage: "
755 "%s [-Bbcd] [-t time] [-w length] [+[+]] [boardspec]\n",
756 getprogname());
757 exit(1);
758 }
759