|
|
1.1 ! root 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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.