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
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 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 (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 */
223 char *
batchword(FILE * fp)224 batchword(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 */
251 void
playgame(void)252 playgame(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
355 timesup: ;
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 */
383 int
checkword(char * word,int prev,int * path)384 checkword(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 */
464 int
validword(char * word)465 validword(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 */
497 void
checkdict(void)498 checkdict(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 */
584 void
newgame(char * b)585 newgame(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
664 static int
compar(const void * p,const void * q)665 compar(const void *p, const void *q)
666 {
667 return (strcmp(*(char **)p, *(char **)q));
668 }
669
670 /*
671 * Allocate and initialize data structures.
672 */
673 static void
init(void)674 init(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 */
717 static void
init_adjacencies(void)718 init_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
753 void
usage(void)754 usage(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