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