/*
This is logically the same program as boggle.c, but I have updated
it as follows:
1) instead of checking each prefix and word with an external
procedure (which requires walking down the DAWG each time),
I walk the DAWG in parallel with doing the maze walk of the
boggle board. This makes it *far* more efficient.
2) I have made the code re-entrant, so that you can check
multiple boggle layouts within one run of the program. This
will make it easy to adapt the code to run inside Phil Goetz's
genetic algorithm boggle-board generator, *without* the overhead
of both loading an external program *and* an external wordlist
for every board evaluation.
3) results are recorded in an internal dynamic trie, rather than
just printed out as soon as they're found. This has two
benefits - the words are both unique, and sorted. This saves
having to pipe the output through sort|uniq.
*/
#include <stdio.h>
#include <stdlib.h>
#include "splib.h"
#ifndef TRUE
#define TRUE (0==0)
#define FALSE (!TRUE)
#endif
int printed = 0; /* total words */
int score = 0; /* total score */
NODE *dict; /* master word list */
NODE *results; /* words found */
INDEX nedges; /* size of wordlist */
char *die5[25] = {
"hiprry", "ceipst", "aafirs", "adennn", "ddlonr",
"ooottu", "aaafrs", "ceiilt", "ccnstw", "fiprsy",
"aeegmu", "dhlnor", "gorrvw", "dhhlor", "aaeeee",
"ensssu", "ceilpt", "emottt", "aeeeem", "eiiitt",
"afirsy", "dhhnot", "aegmnn", "nootuw","bjkQxz"
};
char *die4[16] = {
"eegnaa", "soiset", "abbooj", "ldexir",
"wrethv", "wtoota", "muQhni", "wegnhe",
"tstidy", "verldy", "ienues", "zhrlnn",
"fskfap", "rettyl", "iotmcu", "ahspoc"
};
void boggle_handle_word(char *word)
{
int len;
printed += 1;
fprintf(stdout, "%s\n", word);
/*
See http://www.centralconnector.com/GAMES/boggle.html
Calculate score in accordance with boggle rules:
1 point for 3- or 4-letter words, 2 points for 5-letter words,
3 points for 6, 5 for 7-letter words, and 11 points for 8 or more letters.
QU seems to count as 2 letters.
Note French boggle appears to be:
1 point for 4 letters, 2 for 5 letters, 3 for six letters,
5 for 7 letters, 11 for >= 8 letters
*/
len = strlen(word);
if (len <= 4) {
score += 1;
} else if (len == 5) {
score += 2;
} else if (len == 6) {
score += 3;
} else if (len == 7) {
score += 5;
} else {
score += 11;
}
}
static void dawg_walk(NODE *dawg, INDEX node, int len)
{
static char word[MAX_WORD_LEN];
NODE *edge;
for (edge = (NODE *)&dawg[node]; ; edge++) {
long c;
c = *edge; /* Don't rewrite this - its avoiding a MSC bug */
c = c >> V_LETTER;
c = c & M_LETTER;
word[len] = (char)c;
if ((*edge & M_END_OF_WORD) != 0) {
word[len+1] = '\0';
boggle_handle_word(word);
}
c = *edge & M_NODE_POINTER;
if ((*edge & M_NODE_POINTER) != 0)
dawg_walk(dawg, c, len + 1);
if ((*edge & M_END_OF_NODE) != 0) break; /* End of node */
}
}
void boggle(int bogsize, int x, int y, char *stem, int stemlen,
int board[5][5], int used[5][5], NODE *hnode, NODE *rootdawg)
{
int dx, dy, len;
/* pruning illegal moves would be more efficient outside the procedure call,
but not as elegant */
if (x < 0 || x >= bogsize) return;
if (y < 0 || y >= bogsize) return;
if (used[x][y]) return;
if (board[x][y] == 'Q') {
/* Hack for 'qu' tile */
/* Note it wouldn't be much of a hack to *also* invoke the
next step to search for those words with 'q' which *aren't*
followed by a 'u'. However I don't think they're allowed
in boggle... */
stem[stemlen] = 'q';
for (;;) { /* is the first letter of our string valid? */
if ((char)(((*hnode) >> V_LETTER) & M_LETTER) == 'q') {
/* Yes, this letter is valid here! */
break;
}
if (((*hnode) & M_END_OF_NODE) != 0) {
/* we've checked every letter that can be allowed here. */
return; /* PRUNE SEARCH */
}
hnode++;
}
if (((*hnode) & M_NODE_POINTER) == 0) return;
hnode = rootdawg+((*hnode) & M_NODE_POINTER);
stem[stemlen+1] = 'u';
for (;;) { /* is the first letter of our string valid? */
if ((char)(((*hnode) >> V_LETTER) & M_LETTER) == 'u') {
/* Yes, this letter is valid here! */
break;
}
if (((*hnode) & M_END_OF_NODE) != 0) {
/* we've checked every letter that can be allowed here. */
return; /* PRUNE SEARCH */
}
hnode++;
}
if (((*hnode) & M_NODE_POINTER) == 0) return;
hnode = rootdawg+((*hnode) & M_NODE_POINTER);
/* It's a hack, but we'll just assume that no words END in 'qu'.
- I'm lazy. */
len = 2;
} else {
int ch = board[x][y];
stem[stemlen] = ch;
len = 1;
for (;;) { /* is the first letter of our string valid? */
if (ch == (char)(((*hnode) >> V_LETTER) & M_LETTER)) {
/* Yes, this letter is valid here! */
break;
}
if (((*hnode) & M_END_OF_NODE) != 0) {
/* we've checked every letter that can be allowed here. */
return; /* PRUNE SEARCH */
}
hnode++;
}
stem[stemlen+len] = '\0';
if (((*hnode) & M_END_OF_WORD) != 0) { /* Got one */
if (stemlen+len >= 3) trie_add(&results, stem);
}
if (((*hnode) & M_NODE_POINTER) == 0) return;
hnode = rootdawg+((*hnode) & M_NODE_POINTER);
}
used[x][y] = TRUE;
for (dy = -1; dy <= 1; dy++) {
for (dx = -1; dx <= 1; dx++) {
/* The 'if' is optional - would be trimmed inside by used[][]==TRUE */
if (dx != 0 || dy != 0) {
boggle(bogsize, x+dx, y+dy, stem, stemlen+len, board, used,
hnode, rootdawg);
}
}
}
stem[stemlen] = '\0'; /* Backtrack */
used[x][y] = FALSE;
return;
}
int skip_spaces(void)
{
int c;
for (;;) {
c = fgetc(stdin);
if (c != ' ') return(c);
}
}
int get_tile(void)
{
int c = skip_spaces();
if (c == 'q') {
c = fgetc(stdin);
if (c != 'u') {
fprintf(stderr, "Data file error: 'q' not followed by 'u'\n");
exit(2);
}
return('Q');
} else return(c);
}
void drain_line(void)
{
int c = skip_spaces();
if (c == '\n') return;
fprintf(stderr, "Data file error: spurious character '%c'\n", c);
exit(3);
}
int irand(int max)
{
/* return an integer between 0 and i-1 */
int i = rand();
if (i < 0) i = -i;
i = i % max;
if (i >= max) i = 0;
return(i);
}
int main(int argc, char **argv) {
#define swap(a, b, c) {c = a; a = b; b = c;}
int juggle[25];
int board[5][5];
int used[5][5];
char word[51];
int bogsize = 4;
int x, y, i, tmp;
int use_stdin = FALSE;
int use_argv4 = FALSE;
if (!dawg_init("words", &dict, &nedges)) {
fprintf(stderr, "Cannot open words.dwg\n");
exit(1);
}
if (argc >= 2) {
if (strcmp(argv[1], "-5") == 0) {
bogsize = 5;
argv += 1; argc -= 1;
}
}
if (argc == 2) {
/* filename param */
if (strcmp(argv[1], "-") == 0) {
/* Use stdin */
use_stdin = TRUE;
} else {
/* use file at argv[1] - not yet implemented */
}
} else if (argc == 5) {
/* four four-letter words on command line - use those instead of stdin */
use_argv4 = TRUE;
/* bsd compatibility mode, for use with ../gboggle */
}
for (i = 0; i < bogsize*bogsize; i++) {
juggle[i] = i;
}
srand(14); /* 14 gives us a Q for testing, on mine at least */
/* Standard card-shuffling algorithm */
for (i = 0; i < bogsize*bogsize; i++) {
if ((irand(2)&1) != 0) swap(juggle[i], juggle[bogsize*bogsize-1], tmp);
/* bugfix 16Jun00: had juggle[15] above */
}
for (y = 0; y < bogsize; y++) {
for (x = 0; x < bogsize; x++) {
if (bogsize == 4) {
board[x][y] = die4[juggle[y*bogsize+x]][irand(6)];
} else {
board[x][y] = die5[juggle[y*bogsize+x]][irand(6)];
}
used[x][y] = FALSE;
}
}
if (use_stdin) {
for (y = 0; y < bogsize; y++) {
for (x = 0; x < bogsize; x++) {
board[x][y] = get_tile();
}
drain_line();
}
} else if (use_argv4) {
int ap, c;
for (ap = 1; ap <= 4; ap++) {
for (x = 0; x < bogsize; x++) {
c = argv[ap][x];
if (c == 'q') c = 'Q';
board[x][4-ap] = c;
}
}
} else {
for (y = 0; y < bogsize; y++) {
for (x = 0; x < bogsize; x++) {
fprintf(stderr, " %c", board[x][y]);
}
fprintf(stderr, "\n");
}
}
word[0] = '\0';
if (!(trie_new(&results))) {
exit(1);
}
for (y = 0; y < bogsize; y++) {
for (x = 0; x < bogsize; x++) {
boggle(bogsize, x, y, word, 0, board, used, dict+ROOT_NODE, dict);
}
}
dawg_walk(results, ROOT_NODE, 0); /* sorted and unique */
if (use_argv4) {
fprintf(stderr, "gtboggle: %s %s %s %s %d %d\n",
argv[1], argv[2], argv[3], argv[4], printed, score);
} else {
fprintf(stderr, "Words: %d Score: %d\n", printed, score);
}
trie_free(&results); /* Must free results trie when finished with it */
#ifdef PERFORM_SECOND_TEST
/* example of calling code twice in one run */
fprintf(stdout, "---------- next ---------- \n");
/* If re-entering, must re-initialise these */
printed = 0; score = 0;
word[0] = '\0';
for (y = 0; y < bogsize; y++) {
for (x = 0; x < bogsize; x++) {
used[x][y] = FALSE;
}
}
/* Test code */
board[2][0] = 'e'; /* TESTING */
board[1][1] = 'Q'; /* TESTING */
for (y = 0; y < bogsize; y++) {
for (x = 0; x < bogsize; x++) {
fprintf(stderr, " %c", board[x][y]);
}
fprintf(stderr, "\n");
}
/* Re-create a new results trie */
if (!(trie_new(&results))) {
exit(1);
}
/* Second call - no dict load overhead */
for (y = 0; y < bogsize; y++) {
for (x = 0; x < bogsize; x++) {
boggle(bogsize, x, y, word, 0, board, used, dict+ROOT_NODE, dict);
}
}
dawg_walk(results, ROOT_NODE, 0); /* sorted and unique */
trie_free(&results); /* Must free results trie when finished with it */
if (use_argv4) fprintf(stderr, "gtboggle: %s %s %s %s %d\n",
argv[1], argv[2], argv[3], argv[4], printed);
#endif /* End of re-entrant call */
free(dict); /* no special procedure to free these. */
/* Must be done once only, at end of program */
exit(0);
}