* The Regents of the University of California. All rights reserved.
* This code is derived from software contributed to Berkeley by
* %sccs.include.redist.c%
static char copyright
[] =
"@(#) Copyright (c) 1993\n\
The Regents of the University of California. All rights reserved.\n";
static char sccsid
[] = "@(#)bog.c 8.2 (Berkeley) %G%";
static int compar
__P((const void *, const void *));
struct dictindex dictindex
[26];
* Cube position numbering:
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];
int wordpath
[MAXWORDLEN
+ 1];
int wordlen
; /* Length of last word returned by nextword() */
char *pword
[MAXPWORDS
], pwords
[MAXPSPACE
], *pwordsp
;
char *mword
[MAXMWORDS
], mwords
[MAXMSPACE
], *mwordsp
;
int tnmwords
= 0, tnpwords
= 0;
int ch
, done
, i
, selfuse
, sflag
;
batch
= debug
= reuse
= selfuse
= sflag
= 0;
tlimit
= 180; /* 3 minutes is standard */
while ((ch
= getopt(argc
, argv
, "bds:t:w:")) != EOF
)
if ((tlimit
= atoi(optarg
)) < 1)
errx(1, "bad time limit");
if ((minlength
= atoi(optarg
)) < 3)
errx(1, "min word length must be > 2");
if (strcmp(argv
[0], "+") == 0)
else if (strcmp(argv
[0], "++") == 0)
else if (islower(argv
[0][0])) {
if (strlen(argv
[0]) != 16) {
/* This board is assumed to be valid... */
if (batch
&& bspec
== NULL
)
errx(1, "must give both -b and a board setup");
while ((p
= batchword(stdin
)) != NULL
)
(void) printf("%s\n", p
);
prompt("Loading the dictionary...");
if ((dictfp
= opendict(DICT
)) == NULL
) {
if (loaddict(dictfp
) < 0) {
warnx("can't load %s", DICT
);
if (loadindex(DICTINDEX
) < 0) {
warnx("can't load %s", DICTINDEX
);
prompt("Type <space> to begin...");
while (inputch() != ' ');
bspec
= NULL
; /* reset for subsequent games */
prompt("Type <space> to continue, any cap to quit...");
delay(50); /* wait for user to quit typing */
else if (ch
== '\014' || ch
== '\022') /* ^l or ^r */
* 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
q
= &wordpath
[MAXWORDLEN
+ 1];
while ((w
= nextword(fp
)) != NULL
) {
while (p
< q
&& *p
!= -1)
if (checkword(w
, -1, wordpath
) != -1)
* Reset the word lists from last game
* Keep track of the running stats
/* Can't use register variables if setjmp() is used! */
char buf
[MAXWORDLEN
+ 1];
q
= &wordpath
[MAXWORDLEN
+ 1];
if (getline(buf
) == NULL
) {
if (t
- start_t
>= tlimit
) {
remaining
= tlimit
- (int) (t
- start_t
);
(void)snprintf(buf
, sizeof(buf
),
"%d:%02d", remaining
/ 60, remaining
% 60);
if (strlen(buf
) < minlength
) {
while (p
< q
&& *p
!= -1)
if (checkword(buf
, -1, wordpath
) < 0)
for (i
= 0; wordpath
[i
] != -1; i
++)
(void) printf(" %d", wordpath
[i
]);
for (i
= 0; i
< npwords
; i
++) {
if (strcmp(pword
[i
], buf
) == 0)
if (i
!= npwords
) { /* already used the word */
else if (!validword(buf
))
if (npwords
== MAXPWORDS
- 1 ||
pwordsp
+ len
>= &pwords
[MAXPSPACE
]) {
warnx("Too many words!");
pword
[npwords
++] = pwordsp
;
(void) strcpy(pwordsp
, buf
);
* Sort the player's words and terminate the list with a null
* entry to help out checkdict()
qsort(pword
, npwords
, sizeof(pword
[0]), compar
);
* These words don't need to be sorted since the dictionary is sorted
* 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
checkword(word
, prev
, path
)
(void) printf("checkword(%s, %d, [", word
, prev
);
for (i
= 0; wordpath
[i
] != -1; i
++)
(void) printf(" %d", wordpath
[i
]);
lm
= letter_map
[*word
- 'a'];
char subword
[MAXWORDLEN
+ 1];
* Check for letters not appearing in the cube to eliminate some
if (*letter_map
[*p
- 'a'] == -1)
if (checkword(subword
+ 1, *lm
, path
+ 1) > 0)
* 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
for (i
= 0; lm
[i
] != -1; i
++) {
if (adjacency
[prev
][lm
[i
]]) {
* If necessary, check if the square has already
if (!reuse
&& (usedbits
& used
))
if (checkword(word
+ 1, lm
[i
], path
+ 1) > 0)
*path
= -1; /* in case of a backtrack */
* 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
if (dictseek(dictfp
, dictindex
[j
].start
, 0) < 0) {
(void) fprintf(stderr
, "Seek error\n");
while ((w
= nextword(dictfp
)) != NULL
) {
if (*w
!= word
[0]) /* end of words starting with word[0] */
while ((ch
= *w
++) == *q
++ && ch
!= '\0')
if (*(w
- 1) == '\0' && *(q
- 1) == '\0')
if (dictfp
!= NULL
&& feof(dictfp
)) /* Special case for z's */
* 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
register char *p
, **pw
, *w
;
int prevch
, previndex
, *pi
, *qi
, st
;
qi
= &wordpath
[MAXWORDLEN
+ 1];
(void) dictseek(dictfp
, 0L, 0);
while ((w
= nextword(dictfp
)) != NULL
) {
* 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
while (i
< 26 && letter_map
[i
][0] == -1)
previndex
= prevch
- '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) {
dictindex
[i
].start
, 0) < 0) {
warnx("seek error in checkdict()");
while (pi
< qi
&& *pi
!= -1)
if (checkword(w
, -1, wordpath
) == -1)
while (*pw
!= NULL
&& (st
= strcmp(*pw
, w
)) < 0)
if (st
== 0) /* found it */
if (nmwords
== MAXMWORDS
||
mwordsp
+ wordlen
+ 1 >= &mwords
[MAXMSPACE
]) {
warnx("too many words!");
mword
[nmwords
++] = mwordsp
;
while (*mwordsp
++ = *p
++);
* 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 char *cubes
[16] = {
"ednosw", "aaciot", "acelrs", "ehinps",
"eefhiy", "elpstu", "acdemp", "gilruw",
"egkluy", "ahmors", "abilty", "adenvz",
"bfiorx", "dknotu", "abjmoq", "egintv"
* Shake the cubes and make the board
p
= (int) (random() % 16);
q
= (int) (random() % 16);
board
[i
] = cubes
[i
][random() % 6];
* Set up the map from letter to location(s)
* Each list is terminated by a -1 entry
for (i
= 0; i
< 26; i
++) {
for (i
= 0; i
< 16; i
++) {
j
= (int) (board
[i
] - 'a');
for (i
= 0; i
< 26; i
++) {
(void) printf("%c:", 'a' + i
);
for (j
= 0; (ch
= letter_map
[i
][j
]) != -1; j
++)
(void) printf(" %d", ch
);
return (strcmp(*(char **)p
, *(char **)q
));
"usage: bog [-bd] [-s#] [-t#] [-w#] [+[+]] [boardspec]\n");