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