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