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