1 /* $NetBSD: bog.c,v 1.9 1998/08/30 09:19:36 veego 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. All advertising materials mentioning features or use of this software 19 * must display the following acknowledgement: 20 * This product includes software developed by the University of 21 * California, Berkeley and its contributors. 22 * 4. Neither the name of the University nor the names of its contributors 23 * may be used to endorse or promote products derived from this software 24 * without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 29 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36 * SUCH DAMAGE. 37 */ 38 39 #include <sys/cdefs.h> 40 #ifndef lint 41 __COPYRIGHT("@(#) Copyright (c) 1993\n\ 42 The Regents of the University of California. All rights reserved.\n"); 43 #endif /* not lint */ 44 45 #ifndef lint 46 #if 0 47 static char sccsid[] = "@(#)bog.c 8.2 (Berkeley) 5/4/95"; 48 #else 49 __RCSID("$NetBSD: bog.c,v 1.9 1998/08/30 09:19:36 veego Exp $"); 50 #endif 51 #endif /* not lint */ 52 53 #include <ctype.h> 54 #include <err.h> 55 #include <stdio.h> 56 #include <stdlib.h> 57 #include <string.h> 58 #include <time.h> 59 #include <unistd.h> 60 61 #include "bog.h" 62 #include "extern.h" 63 64 static int compar __P((const void *, const void *)); 65 int main __P((int, char *[])); 66 67 struct dictindex dictindex[26]; 68 69 /* 70 * Cube position numbering: 71 * 72 * 0 1 2 3 73 * 4 5 6 7 74 * 8 9 A B 75 * C D E F 76 */ 77 static int adjacency[16][16] = { 78 /* 0 1 2 3 4 5 6 7 8 9 A B C D E F */ 79 { 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, /* 0 */ 80 { 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, /* 1 */ 81 { 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 }, /* 2 */ 82 { 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 }, /* 3 */ 83 { 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0 }, /* 4 */ 84 { 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0 }, /* 5 */ 85 { 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0 }, /* 6 */ 86 { 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0 }, /* 7 */ 87 { 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0 }, /* 8 */ 88 { 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0 }, /* 9 */ 89 { 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1 }, /* A */ 90 { 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1 }, /* B */ 91 { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0 }, /* C */ 92 { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0 }, /* D */ 93 { 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1 }, /* E */ 94 { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0 } /* F */ 95 }; 96 97 static int letter_map[26][16]; 98 99 char board[17]; 100 int wordpath[MAXWORDLEN + 1]; 101 int wordlen; /* Length of last word returned by nextword() */ 102 int usedbits; 103 104 char *pword[MAXPWORDS], pwords[MAXPSPACE], *pwordsp; 105 int npwords; 106 107 char *mword[MAXMWORDS], mwords[MAXMSPACE], *mwordsp; 108 int nmwords; 109 110 int ngames = 0; 111 int tnmwords = 0, tnpwords = 0; 112 113 #include <setjmp.h> 114 jmp_buf env; 115 116 time_t start_t; 117 118 static FILE *dictfp; 119 120 int batch; 121 int debug; 122 int minlength; 123 int reuse; 124 int tlimit; 125 126 int 127 main(argc, argv) 128 int argc; 129 char *argv[]; 130 { 131 long seed; 132 int ch, done, i, selfuse, sflag; 133 char *bspec, *p; 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(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 prompt("Type <space> to continue, any cap to quit..."); 237 delay(50); /* wait for user to quit typing */ 238 flushin(stdin); 239 for (;;) { 240 ch = inputch(); 241 if (ch == '\033') 242 findword(); 243 else if (ch == '\014' || ch == '\022') /* ^l or ^r */ 244 redraw(); 245 else { 246 if (isupper(ch)) { 247 done = 1; 248 break; 249 } 250 if (ch == ' ') 251 break; 252 } 253 } 254 } 255 cleanup(); 256 exit (0); 257 } 258 259 /* 260 * Read a line from the given stream and check if it is legal 261 * Return a pointer to a legal word or a null pointer when EOF is reached 262 */ 263 char * 264 batchword(fp) 265 FILE *fp; 266 { 267 int *p, *q; 268 char *w; 269 270 q = &wordpath[MAXWORDLEN + 1]; 271 p = wordpath; 272 while (p < q) 273 *p++ = -1; 274 while ((w = nextword(fp)) != NULL) { 275 if (wordlen < minlength) 276 continue; 277 p = wordpath; 278 while (p < q && *p != -1) 279 *p++ = -1; 280 usedbits = 0; 281 if (checkword(w, -1, wordpath) != -1) 282 return (w); 283 } 284 return (NULL); 285 } 286 287 /* 288 * Play a single game 289 * Reset the word lists from last game 290 * Keep track of the running stats 291 */ 292 void 293 playgame() 294 { 295 int i, *p, *q; 296 time_t t; 297 char buf[MAXWORDLEN + 1]; 298 299 ngames++; 300 npwords = 0; 301 pwordsp = pwords; 302 nmwords = 0; 303 mwordsp = mwords; 304 305 time(&start_t); 306 307 q = &wordpath[MAXWORDLEN + 1]; 308 p = wordpath; 309 while (p < q) 310 *p++ = -1; 311 showboard(board); 312 startwords(); 313 if (setjmp(env)) { 314 badword(); 315 goto timesup; 316 } 317 318 while (1) { 319 if (getline(buf) == NULL) { 320 if (feof(stdin)) 321 clearerr(stdin); 322 break; 323 } 324 time(&t); 325 if (t - start_t >= tlimit) { 326 badword(); 327 break; 328 } 329 if (buf[0] == '\0') { 330 int remaining; 331 332 remaining = tlimit - (int) (t - start_t); 333 (void)snprintf(buf, sizeof(buf), 334 "%d:%02d", remaining / 60, remaining % 60); 335 showstr(buf, 1); 336 continue; 337 } 338 if (strlen(buf) < minlength) { 339 badword(); 340 continue; 341 } 342 343 p = wordpath; 344 while (p < q && *p != -1) 345 *p++ = -1; 346 usedbits = 0; 347 348 if (checkword(buf, -1, wordpath) < 0) 349 badword(); 350 else { 351 if (debug) { 352 (void) printf("["); 353 for (i = 0; wordpath[i] != -1; i++) 354 (void) printf(" %d", wordpath[i]); 355 (void) printf(" ]\n"); 356 } 357 for (i = 0; i < npwords; i++) { 358 if (strcmp(pword[i], buf) == 0) 359 break; 360 } 361 if (i != npwords) { /* already used the word */ 362 badword(); 363 showword(i); 364 } 365 else if (!validword(buf)) 366 badword(); 367 else { 368 int len; 369 370 len = strlen(buf) + 1; 371 if (npwords == MAXPWORDS - 1 || 372 pwordsp + len >= &pwords[MAXPSPACE]) { 373 warnx("Too many words!"); 374 cleanup(); 375 exit(1); 376 } 377 pword[npwords++] = pwordsp; 378 (void) strcpy(pwordsp, buf); 379 pwordsp += len; 380 addword(buf); 381 } 382 } 383 } 384 385 timesup: ; 386 387 /* 388 * Sort the player's words and terminate the list with a null 389 * entry to help out checkdict() 390 */ 391 qsort(pword, npwords, sizeof(pword[0]), compar); 392 pword[npwords] = NULL; 393 394 /* 395 * These words don't need to be sorted since the dictionary is sorted 396 */ 397 checkdict(); 398 399 tnmwords += nmwords; 400 tnpwords += npwords; 401 402 results(); 403 } 404 405 /* 406 * Check if the given word is present on the board, with the constraint 407 * that the first letter of the word is adjacent to square 'prev' 408 * Keep track of the current path of squares for the word 409 * A 'q' must be followed by a 'u' 410 * Words must end with a null 411 * Return 1 on success, -1 on failure 412 */ 413 int 414 checkword(word, prev, path) 415 char *word; 416 int prev, *path; 417 { 418 char *p, *q; 419 int i, *lm; 420 421 if (debug) { 422 (void) printf("checkword(%s, %d, [", word, prev); 423 for (i = 0; wordpath[i] != -1; i++) 424 (void) printf(" %d", wordpath[i]); 425 (void) printf(" ]\n"); 426 } 427 428 if (*word == '\0') 429 return (1); 430 431 lm = letter_map[*word - 'a']; 432 433 if (prev == -1) { 434 char subword[MAXWORDLEN + 1]; 435 436 /* 437 * Check for letters not appearing in the cube to eliminate some 438 * recursive calls 439 * Fold 'qu' into 'q' 440 */ 441 p = word; 442 q = subword; 443 while (*p != '\0') { 444 if (*letter_map[*p - 'a'] == -1) 445 return (-1); 446 *q++ = *p; 447 if (*p++ == 'q') { 448 if (*p++ != 'u') 449 return (-1); 450 } 451 } 452 *q = '\0'; 453 while (*lm != -1) { 454 *path = *lm; 455 usedbits |= (1 << *lm); 456 if (checkword(subword + 1, *lm, path + 1) > 0) 457 return (1); 458 usedbits &= ~(1 << *lm); 459 lm++; 460 } 461 return (-1); 462 } 463 464 /* 465 * A cube is only adjacent to itself in the adjacency matrix if selfuse 466 * was set, so a cube can't be used twice in succession if only the 467 * reuse flag is set 468 */ 469 for (i = 0; lm[i] != -1; i++) { 470 if (adjacency[prev][lm[i]]) { 471 int used; 472 473 used = 1 << lm[i]; 474 /* 475 * If necessary, check if the square has already 476 * been used. 477 */ 478 if (!reuse && (usedbits & used)) 479 continue; 480 *path = lm[i]; 481 usedbits |= used; 482 if (checkword(word + 1, lm[i], path + 1) > 0) 483 return (1); 484 usedbits &= ~used; 485 } 486 } 487 *path = -1; /* in case of a backtrack */ 488 return (-1); 489 } 490 491 /* 492 * A word is invalid if it is not in the dictionary 493 * At this point it is already known that the word can be formed from 494 * the current board 495 */ 496 int 497 validword(word) 498 char *word; 499 { 500 int j; 501 char *q, *w; 502 503 j = word[0] - 'a'; 504 if (dictseek(dictfp, dictindex[j].start, 0) < 0) { 505 (void) fprintf(stderr, "Seek error\n"); 506 cleanup(); 507 exit(1); 508 } 509 510 while ((w = nextword(dictfp)) != NULL) { 511 int ch; 512 513 if (*w != word[0]) /* end of words starting with word[0] */ 514 break; 515 q = word; 516 while ((ch = *w++) == *q++ && ch != '\0') 517 ; 518 if (*(w - 1) == '\0' && *(q - 1) == '\0') 519 return (1); 520 } 521 if (dictfp != NULL && feof(dictfp)) /* Special case for z's */ 522 clearerr(dictfp); 523 return (0); 524 } 525 526 /* 527 * Check each word in the dictionary against the board 528 * Delete words from the machine list that the player has found 529 * Assume both the dictionary and the player's words are already sorted 530 */ 531 void 532 checkdict() 533 { 534 char *p, **pw, *w; 535 int i; 536 int prevch, previndex, *pi, *qi, st; 537 538 mwordsp = mwords; 539 nmwords = 0; 540 pw = pword; 541 prevch ='a'; 542 qi = &wordpath[MAXWORDLEN + 1]; 543 544 (void) dictseek(dictfp, 0L, 0); 545 while ((w = nextword(dictfp)) != NULL) { 546 if (wordlen < minlength) 547 continue; 548 if (*w != prevch) { 549 /* 550 * If we've moved on to a word with a different first 551 * letter then we can speed things up by skipping all 552 * words starting with a letter that doesn't appear in 553 * the cube. 554 */ 555 i = (int) (*w - 'a'); 556 while (i < 26 && letter_map[i][0] == -1) 557 i++; 558 if (i == 26) 559 break; 560 previndex = prevch - 'a'; 561 prevch = i + 'a'; 562 /* 563 * Fall through if the word's first letter appears in 564 * the cube (i.e., if we can't skip ahead), otherwise 565 * seek to the beginning of words in the dictionary 566 * starting with the next letter (alphabetically) 567 * appearing in the cube and then read the first word. 568 */ 569 if (i != previndex + 1) { 570 if (dictseek(dictfp, 571 dictindex[i].start, 0) < 0) { 572 warnx("seek error in checkdict()"); 573 cleanup(); 574 exit(1); 575 } 576 continue; 577 } 578 } 579 580 pi = wordpath; 581 while (pi < qi && *pi != -1) 582 *pi++ = -1; 583 usedbits = 0; 584 if (checkword(w, -1, wordpath) == -1) 585 continue; 586 587 st = 1; 588 while (*pw != NULL && (st = strcmp(*pw, w)) < 0) 589 pw++; 590 if (st == 0) /* found it */ 591 continue; 592 if (nmwords == MAXMWORDS || 593 mwordsp + wordlen + 1 >= &mwords[MAXMSPACE]) { 594 warnx("too many words!"); 595 cleanup(); 596 exit(1); 597 } 598 mword[nmwords++] = mwordsp; 599 p = w; 600 while ((*mwordsp++ = *p++) != NULL) 601 ; 602 } 603 } 604 605 /* 606 * Crank up a new game 607 * If the argument is non-null then it is assumed to be a legal board spec 608 * in ascending cube order, oth. make a random board 609 */ 610 void 611 newgame(b) 612 char *b; 613 { 614 int i, p, q; 615 char *tmp; 616 int *lm[26]; 617 static char *cubes[16] = { 618 "ednosw", "aaciot", "acelrs", "ehinps", 619 "eefhiy", "elpstu", "acdemp", "gilruw", 620 "egkluy", "ahmors", "abilty", "adenvz", 621 "bfiorx", "dknotu", "abjmoq", "egintv" 622 }; 623 624 if (b == NULL) { 625 /* 626 * Shake the cubes and make the board 627 */ 628 i = 0; 629 while (i < 100) { 630 p = (int) (random() % 16); 631 q = (int) (random() % 16); 632 if (p != q) { 633 tmp = cubes[p]; 634 cubes[p] = cubes[q]; 635 cubes[q] = tmp; 636 i++; 637 } 638 /* else try again */ 639 } 640 641 for (i = 0; i < 16; i++) 642 board[i] = cubes[i][random() % 6]; 643 } 644 else { 645 for (i = 0; i < 16; i++) 646 board[i] = b[i]; 647 } 648 board[16] = '\0'; 649 650 /* 651 * Set up the map from letter to location(s) 652 * Each list is terminated by a -1 entry 653 */ 654 for (i = 0; i < 26; i++) { 655 lm[i] = letter_map[i]; 656 *lm[i] = -1; 657 } 658 659 for (i = 0; i < 16; i++) { 660 int j; 661 662 j = (int) (board[i] - 'a'); 663 *lm[j] = i; 664 *(++lm[j]) = -1; 665 } 666 667 if (debug) { 668 for (i = 0; i < 26; i++) { 669 int ch, j; 670 671 (void) printf("%c:", 'a' + i); 672 for (j = 0; (ch = letter_map[i][j]) != -1; j++) 673 (void) printf(" %d", ch); 674 (void) printf("\n"); 675 } 676 } 677 678 } 679 680 int 681 compar(p, q) 682 const void *p, *q; 683 { 684 return (strcmp(*(char **)p, *(char **)q)); 685 } 686 687 void 688 usage() 689 { 690 (void) fprintf(stderr, 691 "usage: bog [-bd] [-s#] [-t#] [-w#] [+[+]] [boardspec]\n"); 692 exit(1); 693 } 694