/*      $NetBSD: bog.c,v 1.29 2014/03/22 23:39:04 dholland Exp $        */

/*-
 * Copyright (c) 1993
 *      The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Barry Brachman.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <sys/cdefs.h>
#ifndef lint
__COPYRIGHT("@(#) Copyright (c) 1993\
 The Regents of the University of California.  All rights reserved.");
#endif /* not lint */

#ifndef lint
#if 0
static char sccsid[] = "@(#)bog.c       8.2 (Berkeley) 5/4/95";
#else
__RCSID("$NetBSD: bog.c,v 1.29 2014/03/22 23:39:04 dholland Exp $");
#endif
#endif /* not lint */

#include <ctype.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <sys/tty.h>

#include "bog.h"
#include "extern.h"

static char *batchword(FILE *);
static void playgame(void);
static int validword(const char *);
static void checkdict(void);
static void newgame(const char *);
static int compar(const void *, const void *);
static void clearwordpath(int full);
static void usage(void) __dead;

struct dictindex dictindex[26];

/*
 * Cube position numbering:
 *
 *      0 1 2 3
 *      4 5 6 7
 *      8 9 A B
 *      C D E F
 */
static int adjacency[16][16] = {
/*        0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F */
        { 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },             /* 0 */
        { 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },             /* 1 */
        { 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },             /* 2 */
        { 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },             /* 3 */
        { 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0 },             /* 4 */
        { 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0 },             /* 5 */
        { 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0 },             /* 6 */
        { 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0 },             /* 7 */
        { 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0 },             /* 8 */
        { 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0 },             /* 9 */
        { 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1 },             /* A */
        { 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1 },             /* B */
        { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0 },             /* C */
        { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0 },             /* D */
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1 },             /* E */
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0 }              /* F */
};

static int letter_map[26][16];

char board[17];
int wordpath[MAXWORDLEN + 1];
int wordlen;            /* Length of last word returned by nextword() */
int usedbits;

const char *pword[MAXPWORDS];
static char pwords[MAXPSPACE], *pwordsp;
int npwords;

const char *mword[MAXMWORDS];
static char mwords[MAXMSPACE], *mwordsp;
int nmwords;

int ngames = 0;
int tnmwords = 0, tnpwords = 0;

#include <setjmp.h>
jmp_buf env;

time_t start_t;
int debug;
int tlimit;

static FILE *dictfp;
static int batch;
static int minlength;
static int reuse;

int
main(int argc, char *argv[])
{
        long seed;
        int ch, done, i, selfuse, sflag;
        char *bspec, *p;

        /* revoke setgid privileges */
        setgid(getgid());

        seed = 0;
        batch = debug = reuse = selfuse = sflag = 0;
        bspec = NULL;
        minlength = 3;
        tlimit = 180;           /* 3 minutes is standard */

        while ((ch = getopt(argc, argv, "bds:t:w:")) != -1)
                switch(ch) {
                case 'b':
                        batch = 1;
                        break;
                case 'd':
                        debug = 1;
                        break;
                case 's':
                        sflag = 1;
                        seed = atol(optarg);
                        break;
                case 't':
                        if ((tlimit = atoi(optarg)) < 1)
                                errx(1, "bad time limit");
                        break;
                case 'w':
                        if ((minlength = atoi(optarg)) < 3)
                                errx(1, "min word length must be > 2");
                        break;
                case '?':
                default:
                        usage();
                }
        argc -= optind;
        argv += optind;

        /* process final arguments */
        if (argc > 0) {
                if (strcmp(argv[0], "+") == 0)
                        reuse = 1;
                else if (strcmp(argv[0], "++") == 0)
                        selfuse = 1;
        }

        if (reuse || selfuse) {
                argc -= 1;
                argv += 1;
        }

        if (argc > 0) {
                if (islower((unsigned char)argv[0][0])) {
                        if (strlen(argv[0]) != 16) {
                                usage();
                        } else {
                                /* This board is assumed to be valid... */
                                bspec = argv[0];
                        }
                } else {
                        usage();
                }
        }

        if (batch && bspec == NULL)
                errx(1, "must give both -b and a board setup");

        if (selfuse)
                for (i = 0; i < 16; i++)
                        adjacency[i][i] = 1;

        if (batch) {
                newgame(bspec);
                while ((p = batchword(stdin)) != NULL)
                        (void) printf("%s\n", p);
                exit (0);
        }
        setup(sflag, seed);
        prompt("Loading the dictionary...");
        if ((dictfp = opendict(DICT)) == NULL) {
                warn("%s", DICT);
                cleanup();
                exit(1);
        }
#ifdef LOADDICT
        if (loaddict(dictfp) < 0) {
                warnx("can't load %s", DICT);
                cleanup();
                exit(1);
        }
        (void)fclose(dictfp);
        dictfp = NULL;
#endif
        if (loadindex(DICTINDEX) < 0) {
                warnx("can't load %s", DICTINDEX);
                cleanup();
                exit(1);
        }

        prompt("Type <space> to begin...");
        while (inputch() != ' ');

        for (done = 0; !done;) {
                newgame(bspec);
                bspec = NULL;   /* reset for subsequent games */
                playgame();
#ifdef NEW_STYLE
                prompt("Type <q>uit, <esc> locate, any other key to continue...");
#else
                prompt("Type <space> to continue, any cap to quit...");
#endif
                delay(50);      /* wait for user to quit typing */
                flushin(stdin);
                for (;;) {
                        ch = inputch();
#ifdef NEW_STYLE
                        if (ch == '\e')
                                findword();
                        else if (ch == CTRL('l') || ch == CTRL('r'))
                                redraw();
                        else {
                                if (ch == 'q') {
                                        done = 1;
                                        break;
                                } else {
                                        break;
                                }
                        }
#else
                        if (ch == '\e')
                                findword();
                        else if (ch == CTRL('l') || ch == CTRL('r'))
                                redraw();
                        else {
                                if (isupper(ch)) {
                                        done = 1;
                                        break;
                                }
                                if (ch == ' ')
                                        break;
                        }
#endif
                }
        }
        cleanup();
        exit (0);
}

/*
 * Read a line from the given stream and check if it is legal
 * Return a pointer to a legal word or a null pointer when EOF is reached
 */
static char *
batchword(FILE *fp)
{
        char *w;

        clearwordpath(1);
        while ((w = nextword(fp)) != NULL) {
                if (wordlen < minlength)
                        continue;
                clearwordpath(0);
                usedbits = 0;
                if (checkword(w, -1, wordpath) != -1)
                        return (w);
        }
        return (NULL);
}

/*
 * Play a single game
 * Reset the word lists from last game
 * Keep track of the running stats
 */
static void
playgame(void)
{
        int i;
        time_t t;
        char buf[MAXWORDLEN + 1];

        ngames++;
        npwords = 0;
        pwordsp = pwords;
        nmwords = 0;
        mwordsp = mwords;

        time(&start_t);

        clearwordpath(1);
        showboard(board);
        startwords();
        if (setjmp(env)) {
                badword();
                goto timesup;
        }

        while (1) {
                if (get_line(buf) == NULL) {
                        if (feof(stdin))
                                clearerr(stdin);
                        break;
                }
                time(&t);
                if (t - start_t >= tlimit) {
                        badword();
                        break;
                }
                if (buf[0] == '\0') {
                        int remaining;

                        remaining = tlimit - (int) (t - start_t);
                        (void)snprintf(buf, sizeof(buf),
                            "%d:%02d", remaining / 60, remaining % 60);
                        showstr(buf, 1);
                        continue;
                }
                if (strlen(buf) < (size_t)minlength) {
                        badword();
                        continue;
                }

                clearwordpath(0);
                usedbits = 0;

                if (checkword(buf, -1, wordpath) < 0)
                        badword();
                else {
                        if (debug) {
                                (void) printf("[");
                                for (i = 0; wordpath[i] != -1; i++)
                                        (void) printf(" %d", wordpath[i]);
                                (void) printf(" ]\n");
                        }
                        for (i = 0; i < npwords; i++) {
                                if (strcmp(pword[i], buf) == 0)
                                        break;
                        }
                        if (i != npwords) {     /* already used the word */
                                badword();
                                showword(i);
                        }
                        else if (!validword(buf))
                                badword();
                        else {
                                size_t len;

                                len = strlen(buf) + 1;
                                if (npwords == MAXPWORDS - 1 ||
                                    pwordsp + len >= &pwords[MAXPSPACE]) {
                                        warnx("Too many words!");
                                        cleanup();
                                        exit(1);
                                }
                                pword[npwords++] = pwordsp;
                                (void) strcpy(pwordsp, buf);
                                pwordsp += len;
                                addword(buf);
                        }
                }
        }

timesup: ;

        /*
         * Sort the player's words and terminate the list with a null
         * entry to help out checkdict()
         */
        qsort(pword, npwords, sizeof(pword[0]), compar);
        pword[npwords] = NULL;

        /*
         * These words don't need to be sorted since the dictionary is sorted
         */
        checkdict();

        tnmwords += nmwords;
        tnpwords += npwords;

        results();
}

/*
 * Check if the given word is present on the board, with the constraint
 * that the first letter of the word is adjacent to square 'prev'
 * Keep track of the current path of squares for the word
 * A 'q' must be followed by a 'u'
 * Words must end with a null
 * Return 1 on success, -1 on failure
 */
int
checkword(const char *word, int prev, int *path)
{
        const char *p;
        char *q;
        int i, *lm;

        if (debug) {
                (void) printf("checkword(%s, %d, [", word, prev);
                        for (i = 0; wordpath[i] != -1; i++)
                                (void) printf(" %d", wordpath[i]);
                        (void) printf(" ]\n");
        }

        if (*word == '\0')
                return (1);

        lm = letter_map[*word - 'a'];

        if (prev == -1) {
                char subword[MAXWORDLEN + 1];

                /*
                 * Check for letters not appearing in the cube to eliminate some
                 * recursive calls
                 * Fold 'qu' into 'q'
                 */
                p = word;
                q = subword;
                while (*p != '\0') {
                        if (*letter_map[*p - 'a'] == -1)
                                return (-1);
                        *q++ = *p;
                        if (*p++ == 'q') {
                                if (*p++ != 'u')
                                        return (-1);
                        }
                }
                *q = '\0';
                while (*lm != -1) {
                        *path = *lm;
                        usedbits |= (1 << *lm);
                        if (checkword(subword + 1, *lm, path + 1) > 0)
                                return (1);
                        usedbits &= ~(1 << *lm);
                        lm++;
                }
                return (-1);
        }

        /*
         * A cube is only adjacent to itself in the adjacency matrix if selfuse
         * was set, so a cube can't be used twice in succession if only the
         * reuse flag is set
         */
        for (i = 0; lm[i] != -1; i++) {
                if (adjacency[prev][lm[i]]) {
                        int used;

                        used = 1 << lm[i];
                        /*
                         * If necessary, check if the square has already
                         * been used.
                         */
                        if (!reuse && (usedbits & used))
                                        continue;
                        *path = lm[i];
                        usedbits |= used;
                        if (checkword(word + 1, lm[i], path + 1) > 0)
                                return (1);
                        usedbits &= ~used;
                }
        }
        *path = -1;             /* in case of a backtrack */
        return (-1);
}

/*
 * A word is invalid if it is not in the dictionary
 * At this point it is already known that the word can be formed from
 * the current board
 */
static int
validword(const char *word)
{
        int j;
        const char *q, *w;

        j = word[0] - 'a';
        if (dictseek(dictfp, dictindex[j].start, SEEK_SET) < 0) {
                (void) fprintf(stderr, "Seek error\n");
                cleanup();
                exit(1);
        }

        while ((w = nextword(dictfp)) != NULL) {
                int ch;

                if (*w != word[0])      /* end of words starting with word[0] */
                        break;
                q = word;
                while ((ch = *w++) == *q++ && ch != '\0')
                        ;
                if (*(w - 1) == '\0' && *(q - 1) == '\0')
                        return (1);
        }
        if (dictfp != NULL && feof(dictfp))     /* Special case for z's */
                clearerr(dictfp);
        return (0);
}

/*
 * Check each word in the dictionary against the board
 * Delete words from the machine list that the player has found
 * Assume both the dictionary and the player's words are already sorted
 */
static void
checkdict(void)
{
        char *p, *w;
        const char **pw;
        int i;
        int prevch, previndex, st;

        mwordsp = mwords;
        nmwords = 0;
        pw = pword;
        prevch ='a';

        (void) dictseek(dictfp, 0L, SEEK_SET);
        while ((w = nextword(dictfp)) != NULL) {
                if (wordlen < minlength)
                        continue;
                if (*w != prevch) {
                        /*
                         * If we've moved on to a word with a different first
                         * letter then we can speed things up by skipping all
                         * words starting with a letter that doesn't appear in
                         * the cube.
                         */
                        i = (int) (*w - 'a');
                        while (i < 26 && letter_map[i][0] == -1)
                                i++;
                        if (i == 26)
                                break;
                        previndex = prevch - 'a';
                        prevch = i + 'a';
                        /*
                         * Fall through if the word's first letter appears in
                         * the cube (i.e., if we can't skip ahead), otherwise
                         * seek to the beginning of words in the dictionary
                         * starting with the next letter (alphabetically)
                         * appearing in the cube and then read the first word.
                         */
                        if (i != previndex + 1) {
                                if (dictseek(dictfp,
                                    dictindex[i].start, SEEK_SET) < 0) {
                                        warnx("seek error in checkdict()");
                                        cleanup();
                                        exit(1);
                                }
                                continue;
                        }
                }

                clearwordpath(0);
                usedbits = 0;
                if (checkword(w, -1, wordpath) == -1)
                        continue;

                st = 1;
                while (*pw != NULL && (st = strcmp(*pw, w)) < 0)
                        pw++;
                if (st == 0)                    /* found it */
                        continue;
                if (nmwords == MAXMWORDS ||
                    mwordsp + wordlen + 1 >= &mwords[MAXMSPACE]) {
                        warnx("too many words!");
                        cleanup();
                        exit(1);
                }
                mword[nmwords++] = mwordsp;
                p = w;
                while ((*mwordsp++ = *p++) != '\0')
                        ;
        }
}

/*
 * Crank up a new game
 * If the argument is non-null then it is assumed to be a legal board spec
 * in ascending cube order, oth. make a random board
 */
static void
newgame(const char *b)
{
        int i, p, q;
        const char *tmp;
        int *lm[26];
        static const char *cubes[16] = {
                "ednosw", "aaciot", "acelrs", "ehinps",
                "eefhiy", "elpstu", "acdemp", "gilruw",
                "egkluy", "ahmors", "abilty", "adenvz",
                "bfiorx", "dknotu", "abjmoq", "egintv"
        };

        if (b == NULL) {
                /*
                 * Shake the cubes and make the board
                 */
                i = 0;
                while (i < 100) {
                        p = (int) (random() % 16);
                        q = (int) (random() % 16);
                        if (p != q) {
                                tmp = cubes[p];
                                cubes[p] = cubes[q];
                                cubes[q] = tmp;
                                i++;
                        }
                        /* else try again */
                }

                for (i = 0; i < 16; i++)
                        board[i] = cubes[i][random() % 6];
        }
        else {
                for (i = 0; i < 16; i++)
                        board[i] = b[i];
        }
        board[16] = '\0';

        /*
         * Set up the map from letter to location(s)
         * Each list is terminated by a -1 entry
         */
        for (i = 0; i < 26; i++) {
                lm[i] = letter_map[i];
                *lm[i] = -1;
        }

        for (i = 0; i < 16; i++) {
                int j;

                j = (int) (board[i] - 'a');
                *lm[j] = i;
                *(++lm[j]) = -1;
        }

        if (debug) {
                for (i = 0; i < 26; i++) {
                        int ch, j;

                        (void) printf("%c:", 'a' + i);
                        for (j = 0; (ch = letter_map[i][j]) != -1; j++)
                                (void) printf(" %d", ch);
                        (void) printf("\n");
                }
        }

}

/*
 * Clear wordpath[].
 */
static void
clearwordpath(int full)
{
        size_t pos;
        const size_t max = MAXWORDLEN + 1;

        for (pos = 0; pos < max && (full || wordpath[pos] != -1); pos++) {
                wordpath[pos] = -1;
        }
}

static int
compar(const void *p, const void *q)
{
        return (strcmp(*(const char *const *)p, *(const char *const *)q));
}

static void
usage(void)
{
        (void) fprintf(stderr,
            "usage: %s [-bd] [-s#] [-t#] [-w#] [+[+]] [boardspec]\n",
            getprogname());
        exit(1);
}