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