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