1 /*- 2 * Copyright (c) 1982 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * %sccs.include.proprietary.c% 6 */ 7 8 #ifndef lint 9 char copyright[] = 10 "@(#) Copyright (c) 1982 The Regents of the University of California.\n\ 11 All rights reserved.\n"; 12 #endif /* not lint */ 13 14 #ifndef lint 15 static char sccsid[] = "@(#)boggle.c 5.7 (Berkeley) 05/07/93"; 16 #endif /* not lint */ 17 18 #include <sys/types.h> 19 #include <sys/wait.h> 20 #include <ctype.h> 21 #include <errno.h> 22 #include <fcntl.h> 23 #include <setjmp.h> 24 #include <sgtty.h> 25 #include <signal.h> 26 #include <stdio.h> 27 #include <stdlib.h> 28 #include <string.h> 29 #include <time.h> 30 #include <unistd.h> 31 #include "pathnames.h" 32 33 /* basic parameters */ 34 #define N 4 35 #define SSIZE 200 36 #define MAXWORDS 1000 37 #define CWIDTH 10 38 #define LWIDTH 80 39 40 /* parameters defined in terms of above */ 41 #define BSIZE (N*N) 42 #define row(x) (x/N) 43 #define col(x) (x%N) 44 45 /* word being searched for */ 46 int wlength; 47 int numsame; 48 char wbuff [BSIZE+1]; 49 50 /* tty and process control */ 51 extern int errno; 52 int status; 53 int pipefd[2]; 54 int super = 0; 55 int delct = 1; 56 int zero = 0; 57 int master = 1; 58 int column; 59 int *timept; 60 int timeint[] = {60,60,50,7,1,1,1,0}; 61 time_t timein; 62 struct sgttyb origttyb, tempttyb; 63 int ctlecho = 0; 64 int lctlech = LCTLECH; 65 jmp_buf env; 66 67 /* monitoring variables */ 68 int games; 69 int logfile = -1; 70 off_t logloc; 71 char logbuff[100] = {"inst\t"}; 72 73 /* dictionary interface */ 74 FILE *dict; 75 76 /* structures for doing matching */ 77 struct frame { 78 struct frame *parent; 79 int place; 80 }; 81 struct frame stack[SSIZE]; 82 struct frame *level[BSIZE+1]; 83 84 /* the board and subsidiary structures */ 85 char present[BSIZE+1]; 86 char board[BSIZE]; 87 char olink[BSIZE]; 88 char adj[BSIZE+1][BSIZE]; 89 char occurs[26]; 90 91 /* the boggle cubes */ 92 char *cube[BSIZE] = { 93 "forixb", "moqabj", "gurilw", "setupl", 94 "cmpdae", "acitao", "slcrae", "romash", 95 "nodesw", "hefiye", "onudtk", "tevign", 96 "anedvz", "pinesh", "abilyt", "gkyleu" 97 }; 98 99 100 /* storage for words found */ 101 int ubotch, ustart, wcount; 102 char *word[MAXWORDS]; 103 char *freesp; 104 char space[10000]; 105 106 void aputuword __P((int)); 107 void aputword __P((int)); 108 void clearscreen __P((void)); 109 int compare __P((const void *, const void *)); 110 void endline __P((void)); 111 int evalboard __P((int (*)(void), void (*)(int))); 112 void genboard __P((void)); 113 int getdword __P((void)); 114 int getuword __P((void)); 115 __dead void goodbye __P((int)); 116 void interrupt __P((int)); 117 void makelists __P((void)); 118 int numways __P((struct frame *, struct frame *)); 119 void outword __P((char *)); 120 void printboard __P((void)); 121 void printdiff __P((void)); 122 void printinst __P((void)); 123 void setup __P((void)); 124 void timeout __P((int)); 125 void tputword __P((int)); 126 int wordcomp __P((char *, char *)); 127 128 129 void 130 endline() 131 { 132 if (column != 0) { 133 putchar('\n'); 134 column = 0; 135 } 136 } 137 138 void 139 timeout(sig) 140 int sig; 141 { 142 if (*timept > 0) { 143 signal(SIGALRM, timeout); 144 alarm(*timept++); 145 } 146 putchar('\007'); 147 } 148 149 void 150 interrupt(sig) 151 int sig; 152 { 153 154 signal(SIGINT, interrupt); 155 if (delct++ >= 1) 156 longjmp(env, 1); 157 timept = &zero; 158 } 159 160 __dead void 161 goodbye(stat) 162 int stat; 163 { 164 if (master != 0) { 165 wait(&status); 166 if (ctlecho & LCTLECH) 167 ioctl(fileno(stdin), TIOCLBIS, &lctlech); 168 stty(fileno(stdin), &origttyb); 169 } 170 exit(stat); 171 } 172 173 void 174 clearscreen() 175 { 176 stty(fileno(stdin), &tempttyb); 177 printf("\n\033\f\r"); 178 } 179 180 int 181 compare(a, b) 182 const void *a, *b; 183 { 184 185 return(wordcomp(*(char **)a, *(char **)b)); 186 } 187 188 int 189 wordcomp(p, q) 190 register char *p, *q; 191 { 192 if (*p=='0' && *q!='0') 193 return(-1); 194 if (*p!='0' && *q=='0') 195 return(1); 196 while (*++p == *++q && isalpha(*p)) ; 197 if (!isalpha(*p)) 198 return(-isalpha(*q)); 199 if (!isalpha(*q)) 200 return(1); 201 return(*p-*q); 202 } 203 204 void 205 printinst() 206 { 207 stty(fileno(stdin), &tempttyb); 208 printf("instructions?"); 209 if (getchar() == 'y') { 210 clearscreen(); 211 printf(" The object of Boggle (TM Parker Bros.) is to find, within 3\n"); 212 printf("minutes, as many words as possible in a 4 by 4 grid of letters. Words\n"); 213 printf("may be formed from any sequence of 3 or more adjacent letters in the\n"); 214 printf("grid. The letters may join horizontally, vertically, or diagonally.\n"); 215 printf("However, no position in the grid may be used more than once within any\n"); 216 printf("one word. In competitive play amongst humans, each player is given\n"); 217 printf("credit for those of his words which no other player has found.\n"); 218 printf(" This program is intended for people wishing to sharpen their\n"); 219 printf("skills at Boggle. If you invoke the program with 4 arguments of 4\n"); 220 printf("letters each, (e.g. \"boggle appl epie moth erhd\") the program forms the\n"); 221 printf("obvious Boggle grid and lists all the words from /usr/dict/words found\n"); 222 printf("therein. If you invoke the program without arguments, it will generate\n"); 223 printf("a board for you, let you enter words for 3 minutes, and then tell you\n"); 224 printf("how well you did relative to /usr/dict/words.\n"); 225 printf(" In interactive play, enter your words separated by spaces, tabs,\n"); 226 printf("or newlines. A bell will ring when there is 2:00, 1:00, 0:10, 0:02,\n"); 227 printf("0:01, and 0:00 time left. You may complete any word started before the\n"); 228 printf("expiration of time. You can surrender before time is up by hitting\n"); 229 printf("'break'. While entering words, your erase character is only effective\n"); 230 printf("within the current word and your line kill character is ignored.\n"); 231 printf(" Advanced players may wish to invoke the program with 1 or 2 +'s as\n"); 232 printf("the first argument. The first + removes the restriction that positions\n"); 233 printf("can only be used once in each word. The second + causes a position to\n"); 234 printf("be considered adjacent to itself as well as its (up to) 8 neighbors.\n"); 235 printf("Hit any key to begin.\n"); 236 stty(fileno(stdin), &tempttyb); 237 getchar(); 238 } 239 stty(fileno(stdin), &tempttyb); 240 } 241 242 void 243 setup() 244 { 245 register int i, j; 246 int rd, cd, k; 247 for (i=0; i<BSIZE; i++) { 248 adj[i][i] = super>=2 ? 1 : 0; 249 adj[BSIZE][i] = 1; 250 for (j=0; j<i; j++) { 251 rd = row(i)-row(j); 252 cd = col(i)-col(j); 253 k = 0; 254 switch (rd) { 255 case -1: 256 case 1: 257 if (-1<=cd && cd<=1) 258 k = 1; 259 break; 260 case 0: 261 if (cd==-1 || cd==1) 262 k = 1; 263 break; 264 } 265 adj[i][j] = adj[j][i] = k; 266 } 267 } 268 stack[0].parent = &stack[0]; 269 stack[0].place = BSIZE; 270 level[0] = &stack[0]; 271 level[1] = &stack[1]; 272 } 273 274 void 275 makelists() 276 { 277 register int i, c; 278 for (i=0; i<26; i++) 279 occurs[i] = BSIZE; 280 for (i=0; i<BSIZE; i++) { 281 c = board[i]; 282 olink[i] = occurs[c-'a']; 283 occurs[c-'a'] = i; 284 } 285 } 286 287 void 288 genboard() 289 { 290 register int i, j; 291 for (i=0; i<BSIZE; i++) 292 board[i] = 0; 293 for (i=0; i<BSIZE; i++) { 294 j = rand()%BSIZE; 295 while (board[j] != 0) 296 j = (j+1)%BSIZE; 297 board[j] = cube[i][rand()%6]; 298 } 299 } 300 301 void 302 printboard() 303 { 304 register int i, j; 305 for (i=0; i<N; i++) { 306 printf("\t\t\t\t\b\b"); 307 for (j=0; j<N; j++) { 308 putchar ((putchar(board[i*N+j]) == 'q') ? 'u' : ' '); 309 putchar(' '); 310 } 311 putchar('\n'); 312 } 313 putchar('\n'); 314 } 315 316 int 317 getdword() 318 { 319 /* input: numsame = # chars same as last word */ 320 /* output: numsame = # same chars for next word */ 321 /* word in wbuff[0]...wbuff[wlength-1] */ 322 register int c; 323 register char *p; 324 if (numsame == EOF) 325 return (0); 326 p = &wbuff[numsame]+1; 327 while ((*p++ = c = getc(dict)) != EOF && isalpha(c)) ; 328 numsame = c; 329 wlength = p - &wbuff[2]; 330 return (1); 331 } 332 333 int 334 getuword() 335 { 336 int c; 337 register char *p, *q, *r; 338 numsame = 0; 339 while (*timept>0 && (isspace(c=getchar()) || c==EOF)); 340 if (*timept == 0) 341 return(0); 342 word[wcount++] = freesp; 343 *freesp++ = '0'; 344 r = &wbuff[1]; 345 q = p = freesp; 346 *p++ = c; 347 while (!isspace(c = getchar())) { 348 if (c == EOF) 349 continue; 350 if (c == origttyb.sg_erase) { 351 if (p > q) 352 p--; 353 continue; 354 } 355 *p++ = c; 356 } 357 freesp = p; 358 for (p=q; p<freesp && r<&wbuff[BSIZE]; ) 359 if (islower(c = *p++) && (*r++ = *q++ = c) == 'q' && *p == 'u') 360 p++; 361 *(freesp = q) = '0'; 362 wlength = r-&wbuff[1]; 363 return(1); 364 } 365 366 void 367 aputuword(ways) 368 int ways; 369 { 370 *word[wcount-1] = ways>=10 ? '*' : '0'+ways; 371 } 372 373 void 374 aputword(ways) 375 int ways; 376 { 377 /* store (wbuff, ways) in next slot in space */ 378 register int i; 379 *freesp++ = ways>=10 ? '*' : '0'+ways; 380 for (i=1; i<= wlength; i++) 381 *freesp++ = wbuff[i]; 382 word[++wcount] = freesp; 383 } 384 385 void 386 tputword(ways) 387 int ways; 388 { 389 /* print (wbuff, ways) on terminal */ 390 wbuff[wlength+1] = '0'; 391 wbuff[0] = ways>=10 ? '*' : '0'+ways; 392 outword(&wbuff[0]); 393 } 394 395 void 396 outword(p) 397 register char *p; 398 { 399 register int newcol; 400 register char *q; 401 for (q=p+1; isalpha(*q); ) { 402 putchar(*q); 403 if (*q++ == 'q') { 404 putchar('u'); 405 column++; 406 } 407 } 408 column += q-p-1; 409 if (column > LWIDTH-CWIDTH) { 410 putchar('\n'); 411 column = 0; 412 return; 413 } 414 newcol = ((column+CWIDTH)/CWIDTH)*CWIDTH; 415 while (((column+8)/8)*8 <= newcol) { 416 putchar('\t'); 417 column = ((column+8)/8)*8; 418 } 419 while (column < newcol) { 420 putchar(' '); 421 column++; 422 } 423 } 424 425 void 426 printdiff() 427 { 428 register int c, d, u; 429 char both, donly, uonly; 430 word[wcount] = freesp; 431 *freesp = '0'; 432 both = donly = uonly = column = d = 0; 433 u = ustart; 434 while (d < ubotch) { 435 c = u<wcount ? wordcomp (word[d], word[u]) : -1; 436 if (c == 0) { 437 /* dict and user found same word */ 438 if (both == 0) { 439 both = 1; 440 printf("\t\t\t we both found:\n"); 441 } 442 outword(word[d]); 443 word[d++] = NULL; 444 word[u++] = NULL; 445 } else if (c < 0) { 446 /* dict found it, user didn't */ 447 donly = 1; 448 d++; 449 } else { 450 /* user found it, dict didn't */ 451 uonly = 1; 452 u++; 453 } 454 } 455 endline(); 456 if (donly) { 457 printf("\n\t\t\tI alone found these:\n"); 458 for (d=0; d<ubotch; d++) 459 if (word[d] != NULL) 460 outword(word[d]); 461 endline(); 462 } 463 if (uonly) { 464 printf("\n\t\t\tyou alone found these:\n"); 465 for (u=ustart; u<wcount; u++) 466 if (word[u] != NULL) 467 outword(word[u]); 468 endline(); 469 } 470 if (ubotch < ustart) { 471 printf("\n\t\t\t you botched these:\n"); 472 for (u=ubotch; u<ustart; u++) 473 outword(word[u]); 474 endline(); 475 } 476 } 477 478 int 479 numways(leaf, last) 480 register struct frame *leaf; 481 struct frame *last; 482 { 483 int count; 484 register char *p; 485 register struct frame *node; 486 if (super > 0) 487 return(last-leaf); 488 count = 0; 489 present[BSIZE] = 1; 490 while (leaf < last) { 491 for (p = &present[0]; p < &present[BSIZE]; *p++ = 0); 492 for (node = leaf; present[node->place]++ == 0; node = node->parent); 493 if (node == &stack[0]) 494 count++; 495 leaf++; 496 } 497 return(count); 498 } 499 500 int 501 evalboard (getword, putword) 502 int (*getword) __P((void)); 503 void (*putword) __P((int)); 504 { 505 register struct frame *top; 506 register int l, q; 507 int fo, found; 508 struct frame *parent, *lastparent; 509 char *padj; 510 511 numsame = found = 0; 512 makelists (); 513 514 while (1) { 515 l = numsame; 516 if (!(*getword) ()) 517 break; 518 top = level[l+1]; 519 520 while (1) { 521 level[l+1] = lastparent = top; 522 /* wbuff[1]...wbuff[l] have been matched */ 523 /* level[0],...,level[l] of tree built */ 524 if (l == wlength) { 525 if (wlength >= 3 && (q = numways(level[l], top)) != 0) { 526 (*putword) (q); 527 found++; 528 } 529 l = BSIZE+1; 530 break; 531 } 532 if ((fo = occurs[wbuff[++l]-'a']) == BSIZE) 533 break; 534 /* wbuff[1]...wbuff[l-1] have been matched */ 535 /* level[0],...,level[l-1] of tree built */ 536 for (parent=level[l-1]; parent<lastparent; parent++) { 537 padj = &adj[parent->place][0]; 538 for (q=fo; q!=BSIZE; q=olink[q]) 539 if (padj[q]) { 540 top->parent = parent; 541 top->place = q; 542 if (++top >= &stack[SSIZE]) { 543 printf("stack overflow\n"); 544 goodbye(1); 545 } 546 } 547 } 548 /* were any nodes added? */ 549 if (top == lastparent) 550 break; 551 } 552 553 /* advance until first l characters of next word are different */ 554 while (numsame >= l && (*getword)()) ; 555 } 556 return(found); 557 } 558 559 int 560 main(argc, argv) 561 int argc; 562 char **argv; 563 { 564 char *q; 565 register char *p; 566 register int i, c; 567 568 gtty(fileno(stdin), &origttyb); 569 setbuf(stdin, NULL); 570 tempttyb = origttyb; 571 if (setjmp(env) != 0) 572 goodbye(0); 573 signal(SIGINT, interrupt); 574 timein = time((time_t *)NULL); 575 if (argv[0][0] != 'a' && 576 (logfile = open(_PATH_BOGLOG, O_WRONLY, 0)) >= 0) { 577 p = &logbuff[5]; 578 q = getlogin(); 579 while ((*p++ = *q++) != 0); 580 p[-1] = '\t'; 581 q = ctime(&timein); 582 while ((*p++ = *q++) != 0); 583 logloc = lseek(logfile, 0L, 2); 584 write(logfile, &logbuff[0], p-&logbuff[1]); 585 } 586 if ((dict = fopen(_PATH_DICTIONARY, "r")) == NULL) { 587 printf("can't open %s\n", _PATH_DICTIONARY); 588 goodbye (2); 589 } 590 while ( argc > 1 && ( argv[1][0] == '+' || argv[1][0] == '-' ) ) { 591 if (argv[1][0]=='+') { 592 while(*(argv[1]++) == '+') 593 super++; 594 argc--; 595 argv++; 596 } 597 if ( argv[1][0] == '-' ) { 598 timeint[0] = 60 * ( atol( &argv[1][1] ) - 2 ); 599 if ( timeint[0] <= 0 ) { 600 timeint[0] = 60; 601 } 602 argc--; 603 argv++; 604 } 605 } 606 setup (); 607 switch (argc) { 608 default: punt: 609 printf("usage: boggle [+[+]] [row1 row2 row3 row4]\n"); 610 goodbye (3); 611 case 5: 612 for (i=0; i<BSIZE; i++) { 613 board[i] = c = argv[row(i)+1][col(i)]; 614 if (!islower(c)) { 615 printf("bad board\n"); 616 goto punt; 617 } 618 } 619 printboard(); 620 column = 0; 621 evalboard(getdword, tputword); 622 endline(); 623 if (logfile >= 0) { 624 strncpy(&logbuff[0], "eval", 4); 625 lseek(logfile, logloc, 0); 626 write(logfile, &logbuff[0], 4); 627 } 628 goodbye(0); 629 case 1: 630 tempttyb.sg_flags |= CBREAK; 631 if ( ioctl( fileno(stdin), TIOCLGET, &ctlecho ) == 0 ) { 632 if ( ctlecho & LCTLECH ) { 633 ioctl( fileno(stdin), TIOCLBIC, &lctlech ); 634 } 635 } 636 printinst(); 637 srand((int) timein); 638 while (setjmp(env) == 0) { 639 errno = 0; 640 if (pipe(&pipefd[0]) != 0) { 641 printf("can't create pipe\n"); 642 goodbye(4); 643 } 644 genboard(); 645 delct = wcount = 0; 646 word[0] = freesp = &space[0]; 647 if ((master = fork()) == 0) { 648 close(pipefd[0]); 649 clearscreen(); 650 printboard(); 651 signal(SIGALRM, timeout); 652 timept = &timeint[0]; 653 alarm(*timept++); 654 evalboard(getuword, aputuword); 655 clearscreen(); 656 qsort(&word[0], wcount, sizeof(int), compare); 657 for (i=0; i<wcount; i++) 658 if (i==0 || wordcomp(word[i], word[i-1])!=0) { 659 p = word[i]; 660 while (isalpha(*++p)) ; 661 write (pipefd[1], word[i], p-word[i]); 662 } 663 close(pipefd[1]); 664 goodbye(0); 665 } 666 close(pipefd[1]); 667 rewind(dict); 668 getc(dict); 669 evalboard(getdword, aputword); 670 p = freesp; 671 while ((i = read(pipefd[0], freesp, 512)) != 0) { 672 if (i < 0) 673 if (errno != EINTR) 674 break; 675 else 676 i = 0; 677 freesp += i; 678 } 679 close(pipefd[0]); 680 ustart = ubotch = wcount; 681 while (p < freesp) { 682 word[wcount++] = p; 683 if (*p == '0') 684 ustart = wcount; 685 while (isalpha(*++p)); 686 } 687 wait(&status); 688 if (status != 0) 689 goodbye (5); 690 delct = 1; 691 printdiff(); 692 printboard(); 693 games++; 694 if (logfile >= 0) { 695 (void)sprintf(&logbuff[0], "%4d", games); 696 lseek(logfile, logloc, 0); 697 write(logfile, &logbuff[0], 4); 698 } 699 stty (fileno(stdin), &tempttyb); 700 printf("\nanother game?"); 701 if (getchar() != 'y') { 702 putchar('\n'); 703 break; 704 } 705 stty (fileno(stdin), &tempttyb); 706 } 707 goodbye(0); 708 } 709 } 710