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

Defined functions

Defined variables

Defined struct's

Defined macros