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