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