1/* $OpenBSD: bog.c,v 1.34 2021/10/23 11:22:48 mestre 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 49static void init(void); 50static void init_adjacencies(void); 51static int compar(const void *, const void *); 52 53struct dictindex dictindex[26]; 54 55static int **adjacency, **letter_map; 56 57char *board; 58int wordpath[MAXWORDLEN + 1]; 59int wordlen; /* Length of last word returned by nextword() */ 60int usedbits; 61int ncubes; 62int grid = 4; 63 64char **pword, *pwords, *pwordsp; 65int npwords, maxpwords = MAXPWORDS, maxpspace = MAXPSPACE; 66 67char **mword, *mwords, *mwordsp; 68int nmwords, maxmwords = MAXMWORDS, maxmspace = MAXMSPACE; 69 70int ngames = 0; 71int tnmwords = 0, tnpwords = 0; 72 73jmp_buf env; 74 75time_t start_t; 76 77static FILE *dictfp; 78 79int batch; 80int challenge; 81int debug; 82int minlength; 83int reuse; 84int selfuse; 85int tlimit; 86 87int 88main(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 (void) printf("%s\n", p); 161 return 0; 162 } 163 setup(); 164 165 if (pledge("stdio rpath tty", NULL) == -1) 166 err(1, "pledge"); 167 168 prompt("Loading the dictionary..."); 169 if ((dictfp = opendict(DICT)) == NULL) { 170 warn("%s", DICT); 171 cleanup(); 172 return 1; 173 } 174#ifdef LOADDICT 175 if (loaddict(dictfp) < 0) { 176 warnx("can't load %s", DICT); 177 cleanup(); 178 return 1; 179 } 180 (void)fclose(dictfp); 181 dictfp = NULL; 182#endif 183 if (loadindex(DICTINDEX) < 0) { 184 warnx("can't load %s", DICTINDEX); 185 cleanup(); 186 return 1; 187 } 188 189 prompt("Type <space> to begin..."); 190 while (inputch() != ' '); 191 192 for (done = 0; !done;) { 193 newgame(bspec); 194 bspec = NULL; /* reset for subsequent games */ 195 playgame(); 196 prompt("Type <space> to continue, any cap to quit..."); 197 delay(10); /* wait for user to quit typing */ 198 flushin(stdin); 199 for (;;) { 200 ch = inputch(); 201 if (ch == '\033') 202 findword(); 203 else if (ch == '\014' || ch == '\022') /* ^l or ^r */ 204 redraw(); 205 else { 206 if (isupper(ch)) { 207 done = 1; 208 break; 209 } 210 if (ch == ' ') 211 break; 212 } 213 } 214 } 215 cleanup(); 216 return 0; 217} 218 219/* 220 * Read a line from the given stream and check if it is legal 221 * Return a pointer to a legal word or a null pointer when EOF is reached 222 */ 223char * 224batchword(FILE *fp) 225{ 226 int *p, *q; 227 char *w; 228 229 q = &wordpath[MAXWORDLEN + 1]; 230 p = wordpath; 231 while (p < q) 232 *p++ = -1; 233 while ((w = nextword(fp)) != NULL) { 234 if (wordlen < minlength) 235 continue; 236 p = wordpath; 237 while (p < q && *p != -1) 238 *p++ = -1; 239 usedbits = 0; 240 if (checkword(w, -1, wordpath) != -1) 241 return (w); 242 } 243 return (NULL); 244} 245 246/* 247 * Play a single game 248 * Reset the word lists from last game 249 * Keep track of the running stats 250 */ 251void 252playgame(void) 253{ 254 int i, *p, *q; 255 time_t t; 256 char buf[MAXWORDLEN + 1]; 257 258 ngames++; 259 npwords = 0; 260 pwordsp = pwords; 261 nmwords = 0; 262 mwordsp = mwords; 263 264 time(&start_t); 265 266 q = &wordpath[MAXWORDLEN + 1]; 267 p = wordpath; 268 while (p < q) 269 *p++ = -1; 270 showboard(board); 271 startwords(); 272 if (setjmp(env)) { 273 badword(); 274 goto timesup; 275 } 276 277 while (1) { 278 if (get_line(buf) == NULL) { 279 if (feof(stdin)) 280 clearerr(stdin); 281 break; 282 } 283 time(&t); 284 if (t - start_t >= tlimit) { 285 badword(); 286 break; 287 } 288 if (buf[0] == '\0') { 289 int remaining; 290 291 remaining = tlimit - (int) (t - start_t); 292 (void)snprintf(buf, sizeof(buf), 293 "%d:%02d", remaining / 60, remaining % 60); 294 showstr(buf, 1); 295 continue; 296 } 297 if (strlen(buf) < (size_t)minlength) { 298 badword(); 299 continue; 300 } 301 302 p = wordpath; 303 while (p < q && *p != -1) 304 *p++ = -1; 305 usedbits = 0; 306 307 if (checkword(buf, -1, wordpath) < 0) 308 badword(); 309 else { 310 if (debug) { 311 (void) printf("["); 312 for (i = 0; wordpath[i] != -1; i++) 313 (void) printf(" %d", wordpath[i]); 314 (void) printf(" ]\n"); 315 } 316 for (i = 0; i < npwords; i++) { 317 if (strcmp(pword[i], buf) == 0) 318 break; 319 } 320 if (i != npwords) { /* already used the word */ 321 badword(); 322 showword(i); 323 } 324 else if (!validword(buf)) 325 badword(); 326 else { 327 int len; 328 329 if (npwords == maxpwords - 1) { 330 maxpwords += MAXPWORDS; 331 pword = reallocarray(pword, maxpwords, 332 sizeof(char *)); 333 if (pword == NULL) { 334 cleanup(); 335 errx(1, "%s", strerror(ENOMEM)); 336 } 337 } 338 len = strlen(buf) + 1; 339 if (pwordsp + len >= &pwords[maxpspace]) { 340 maxpspace += MAXPSPACE; 341 pwords = realloc(pwords, maxpspace); 342 if (pwords == NULL) { 343 cleanup(); 344 errx(1, "%s", strerror(ENOMEM)); 345 } 346 } 347 pword[npwords++] = pwordsp; 348 memcpy(pwordsp, buf, len); 349 pwordsp += len; 350 addword(buf); 351 } 352 } 353 } 354 355timesup: ; 356 357 /* 358 * Sort the player's words and terminate the list with a null 359 * entry to help out checkdict() 360 */ 361 qsort(pword, npwords, sizeof(pword[0]), compar); 362 pword[npwords] = NULL; 363 364 /* 365 * These words don't need to be sorted since the dictionary is sorted 366 */ 367 checkdict(); 368 369 tnmwords += nmwords; 370 tnpwords += npwords; 371 372 results(); 373} 374 375/* 376 * Check if the given word is present on the board, with the constraint 377 * that the first letter of the word is adjacent to square 'prev' 378 * Keep track of the current path of squares for the word 379 * A 'q' must be followed by a 'u' 380 * Words must end with a null 381 * Return 1 on success, -1 on failure 382 */ 383int 384checkword(char *word, int prev, int *path) 385{ 386 char *p, *q; 387 int i, *lm; 388 389 if (debug) { 390 (void) printf("checkword(%s, %d, [", word, prev); 391 for (i = 0; wordpath[i] != -1; i++) 392 (void) printf(" %d", wordpath[i]); 393 (void) printf(" ]\n"); 394 } 395 396 if (*word == '\0') 397 return (1); 398 399 lm = letter_map[*word - 'a']; 400 401 if (prev == -1) { 402 char subword[MAXWORDLEN + 1]; 403 404 /* 405 * Check for letters not appearing in the cube to eliminate some 406 * recursive calls 407 * Fold 'qu' into 'q' 408 */ 409 p = word; 410 q = subword; 411 while (*p != '\0') { 412 if (*letter_map[*p - 'a'] == -1) 413 return (-1); 414 *q++ = *p; 415 if (*p++ == 'q') { 416 if (*p++ != 'u') 417 return (-1); 418 } 419 } 420 *q = '\0'; 421 while (*lm != -1) { 422 *path = *lm; 423 usedbits |= (1 << *lm); 424 if (checkword(subword + 1, *lm, path + 1) > 0) 425 return (1); 426 usedbits &= ~(1 << *lm); 427 lm++; 428 } 429 return (-1); 430 } 431 432 /* 433 * A cube is only adjacent to itself in the adjacency matrix if selfuse 434 * was set, so a cube can't be used twice in succession if only the 435 * reuse flag is set 436 */ 437 for (i = 0; lm[i] != -1; i++) { 438 if (adjacency[prev][lm[i]]) { 439 int used; 440 441 used = 1 << lm[i]; 442 /* 443 * If necessary, check if the square has already 444 * been used. 445 */ 446 if (!reuse && !selfuse && (usedbits & used)) 447 continue; 448 *path = lm[i]; 449 usedbits |= used; 450 if (checkword(word + 1, lm[i], path + 1) > 0) 451 return (1); 452 usedbits &= ~used; 453 } 454 } 455 *path = -1; /* in case of a backtrack */ 456 return (-1); 457} 458 459/* 460 * A word is invalid if it is not in the dictionary 461 * At this point it is already known that the word can be formed from 462 * the current board 463 */ 464int 465validword(char *word) 466{ 467 int j; 468 char *q, *w; 469 470 j = word[0] - 'a'; 471 if (dictseek(dictfp, dictindex[j].start, SEEK_SET) < 0) { 472 cleanup(); 473 errx(1, "seek error in validword()"); 474 } 475 476 while ((w = nextword(dictfp)) != NULL) { 477 int ch; 478 479 if (*w != word[0]) /* end of words starting with word[0] */ 480 break; 481 q = word; 482 while ((ch = *w++) == *q++ && ch != '\0') 483 ; 484 if (*(w - 1) == '\0' && *(q - 1) == '\0') 485 return (1); 486 } 487 if (dictfp != NULL && feof(dictfp)) /* Special case for z's */ 488 clearerr(dictfp); 489 return (0); 490} 491 492/* 493 * Check each word in the dictionary against the board 494 * Delete words from the machine list that the player has found 495 * Assume both the dictionary and the player's words are already sorted 496 */ 497void 498checkdict(void) 499{ 500 char **pw, *w; 501 int i; 502 int prevch, previndex, *pi, *qi, st; 503 504 mwordsp = mwords; 505 nmwords = 0; 506 pw = pword; 507 prevch ='a'; 508 qi = &wordpath[MAXWORDLEN + 1]; 509 510 (void) dictseek(dictfp, 0L, SEEK_SET); 511 while ((w = nextword(dictfp)) != NULL) { 512 if (wordlen < minlength) 513 continue; 514 if (*w != prevch) { 515 /* 516 * If we've moved on to a word with a different first 517 * letter then we can speed things up by skipping all 518 * words starting with a letter that doesn't appear in 519 * the cube. 520 */ 521 i = (int) (*w - 'a'); 522 while (i < 26 && letter_map[i][0] == -1) 523 i++; 524 if (i == 26) 525 break; 526 previndex = prevch - 'a'; 527 prevch = i + 'a'; 528 /* 529 * Fall through if the word's first letter appears in 530 * the cube (i.e., if we can't skip ahead), otherwise 531 * seek to the beginning of words in the dictionary 532 * starting with the next letter (alphabetically) 533 * appearing in the cube and then read the first word. 534 */ 535 if (i != previndex + 1) { 536 if (dictseek(dictfp, 537 dictindex[i].start, SEEK_SET) < 0) { 538 cleanup(); 539 errx(1, "seek error in checkdict()"); 540 } 541 continue; 542 } 543 } 544 545 pi = wordpath; 546 while (pi < qi && *pi != -1) 547 *pi++ = -1; 548 usedbits = 0; 549 if (checkword(w, -1, wordpath) == -1) 550 continue; 551 552 st = 1; 553 while (*pw != NULL && (st = strcmp(*pw, w)) < 0) 554 pw++; 555 if (st == 0) /* found it */ 556 continue; 557 if (nmwords == maxmwords - 1) { 558 maxmwords += MAXMWORDS; 559 mword = reallocarray(mword, maxmwords, sizeof(char *)); 560 if (mword == NULL) { 561 cleanup(); 562 errx(1, "%s", strerror(ENOMEM)); 563 } 564 } 565 if (mwordsp + wordlen + 1 >= &mwords[maxmspace]) { 566 maxmspace += MAXMSPACE; 567 mwords = realloc(mwords, maxmspace); 568 if (mwords == NULL) { 569 cleanup(); 570 errx(1, "%s", strerror(ENOMEM)); 571 } 572 } 573 mword[nmwords++] = mwordsp; 574 memcpy(mwordsp, w, wordlen + 1); 575 mwordsp += wordlen + 1; 576 } 577} 578 579/* 580 * Crank up a new game 581 * If the argument is non-null then it is assumed to be a legal board spec 582 * in ascending cube order, oth. make a random board 583 */ 584void 585newgame(char *b) 586{ 587 int i, p, q; 588 char *tmp, **cubes; 589 int *lm[26]; 590 char chal_cube[] = "iklmqu"; /* challenge cube */ 591 static char *cubes4[] = { 592 "ednosw", "aaciot", "acelrs", "ehinps", 593 "eefhiy", "elpstu", "acdemp", "gilruw", 594 "egkluy", "ahmors", "abilty", "adenvz", 595 "bfiorx", "dknotu", "abjmoq", "egintv" 596 }; 597 static char *cubes5[] = { 598 "aaafrs", "aaeeee", "aafirs", "adennn", "aeeeem", 599 "aeegmu", "aegmnn", "afirsy", "bjkqxz", "ccnstw", 600 "ceiilt", "ceilpt", "ceipst", "ddlnor", "dhhlor", 601 "dhhnot", "dhlnor", "eiiitt", "emottt", "ensssu", 602 "fiprsy", "gorrvw", "hiprry", "nootuw", "ooottu" 603 }; 604 605 cubes = grid == 4 ? cubes4 : cubes5; 606 if (b == NULL) { 607 /* Shuffle the cubes using Fisher-Yates (aka Knuth P). */ 608 p = ncubes; 609 while (--p) { 610 q = (int)arc4random_uniform(p + 1); 611 tmp = cubes[p]; 612 cubes[p] = cubes[q]; 613 cubes[q] = tmp; 614 } 615 616 /* Build the board by rolling each cube. */ 617 for (i = 0; i < ncubes; i++) 618 board[i] = cubes[i][arc4random_uniform(6)]; 619 620 /* 621 * For challenge mode, roll chal_cube and replace a random 622 * cube with its value. Set the high bit to distinguish it. 623 */ 624 if (challenge) { 625 i = arc4random_uniform(ncubes); 626 board[i] = SETHI(chal_cube[arc4random_uniform(6)]); 627 } 628 } else { 629 for (i = 0; i < ncubes; i++) 630 board[i] = b[i]; 631 } 632 board[ncubes] = '\0'; 633 634 /* 635 * Set up the map from letter to location(s) 636 * Each list is terminated by a -1 entry 637 */ 638 for (i = 0; i < 26; i++) { 639 lm[i] = letter_map[i]; 640 *lm[i] = -1; 641 } 642 643 for (i = 0; i < ncubes; i++) { 644 int j; 645 646 j = (int) (SEVENBIT(board[i]) - 'a'); 647 *lm[j] = i; 648 *(++lm[j]) = -1; 649 } 650 651 if (debug) { 652 for (i = 0; i < 26; i++) { 653 int ch, j; 654 655 (void) printf("%c:", 'a' + i); 656 for (j = 0; (ch = letter_map[i][j]) != -1; j++) 657 (void) printf(" %d", ch); 658 (void) printf("\n"); 659 } 660 } 661 662} 663 664static int 665compar(const void *p, const void *q) 666{ 667 return (strcmp(*(char **)p, *(char **)q)); 668} 669 670/* 671 * Allocate and initialize data structures. 672 */ 673static void 674init(void) 675{ 676 int i; 677 678 if (minlength == -1) 679 minlength = grid - 1; 680 init_adjacencies(); 681 board = malloc(ncubes + 1); 682 if (board == NULL) 683 err(1, NULL); 684 letter_map = calloc(26, sizeof(int *)); 685 if (letter_map == NULL) 686 err(1, NULL); 687 for (i = 0; i < 26; i++) { 688 letter_map[i] = calloc(ncubes, sizeof(int)); 689 if (letter_map[i] == NULL) 690 err(1, NULL); 691 } 692 pword = calloc(maxpwords, sizeof(char *)); 693 if (pword == NULL) 694 err(1, NULL); 695 pwords = malloc(maxpspace); 696 if (pwords == NULL) 697 err(1, NULL); 698 mword = calloc(maxmwords, sizeof(char *)); 699 if (mword == NULL) 700 err(1, NULL); 701 mwords = malloc(maxmspace); 702 if (mwords == NULL) 703 err(1, NULL); 704} 705 706#define SET_ADJ(r) do { \ 707 if (col > 0) \ 708 adj[r - 1] = 1; \ 709 adj[r] = 1; \ 710 if (col + 1 < grid) \ 711 adj[r + 1] = 1; \ 712} while(0) 713 714/* 715 * Compute adjacency matrix for the grid 716 */ 717static void 718init_adjacencies(void) 719{ 720 int cube, row, col, *adj; 721 722 adjacency = calloc(ncubes, sizeof(int *)); 723 if (adjacency == NULL) 724 err(1, NULL); 725 726 /* 727 * Fill in adjacencies. This is an ncubes x ncubes matrix where 728 * the position X,Y is set to 1 if cubes X and Y are adjacent. 729 */ 730 for (cube = 0; cube < ncubes; cube++) { 731 adj = adjacency[cube] = calloc(ncubes, sizeof(int)); 732 if (adj == NULL) 733 err(1, NULL); 734 735 row = cube / grid; 736 col = cube % grid; 737 738 /* this row */ 739 SET_ADJ(cube); 740 if (!selfuse) 741 adj[cube] = 0; 742 743 /* prev row */ 744 if (row > 0) 745 SET_ADJ(cube - grid); 746 747 /* next row */ 748 if (row + 1 < grid) 749 SET_ADJ(cube + grid); 750 } 751} 752 753void 754usage(void) 755{ 756 extern char *__progname; 757 758 (void) fprintf(stderr, "usage: " 759 "%s [-Bbcd] [-t time] [-w length] [+[+]] [boardspec]\n", 760 __progname); 761 exit(1); 762} 763