4.3BSD - /usr/src/games/boggle/boggle.c

   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: }

Defined functions

Defined variables

Defined struct's

Defined macros