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