Return to boggle.c CVS log

Up to [Research Unix] / researchv10no / games / boggle

Annotation of researchv10no/games/boggle/boggle.c, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.