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