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