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