|
|
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.1 (Berkeley) 5/30/85"; ! 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/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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.