/*
Squaring Words
by John Walker -- January 1998
http://www.fourmilab.ch/
This program is in the public domain.
This program searches for solutions to the "squaring words" puzzle
posed in the conclusion of Chapter XVIII, "Picking Locks and
Deciphering", of Charles Babbage's autobiography, "Passages from
the Life of a Philosopher". For example, squaring the word
"dean" is to fill in the missing letters in the grid:
d e a n
e . . .
a . . .
n . . .
so that the tableau reads the same across and down. One
solution for "dean" is the following, given by Babbage.
d e a n
e a s e
a s k s
n e s t
This program, used in conjunction with a spelling checker
dictionary consisting of an ASCII text file with one word
per line (like a Unix /usr/dict/words file), searches for
ways to square the word given as its sole command line
argument, printing all solutions on standard output. If
your system doesn't have a suitable dictionary, you can
download the Moby Words dictionary from:
http://www.clres.com/dict.html
or by FTP from:
ftp://ftp.dcs.shef.ac.uk/share/ilash/Moby/
Get the Moby Words file, mwords.tar.Z (many of the other
files in this directory are also interesting), uncompress
and un-tar, and consult the readme.txt file for a description
of the contents. The list of 354,984 single words is an
excellent one to use with this program. If you are looking
for more common words in the square, try the list of 113,809
words from the Scrabble[tm] dictionary, or the list of
74,550 common dictionary words.
*/
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#define DICT "moby.txt" /* Dictionary file */
#define NW 5000 /* Maximum candidate words per initial letter */
#define MAXWORD 128 /* Longest target word */
#define IX(x) ((x) - 'a') /* Map lcased initial letter to array index */
#define FALSE 0
#define TRUE 1
static char *words[IX('z') + 1][NW];
static int nwl[IX('z') + 1];
static char *target;
static int ltarget;
static char *cand[128];
/* LCASE -- Translate a string in place to all lower case.
If the string contains any non-alphabetic character
FALSE is returned, otherwise TRUE. */
static int lcase(char *cp) {
int allalpha = TRUE;
while (*cp) {
if (!isalpha(*cp)) {
allalpha = FALSE;
}
if (isupper(*cp)) {
*cp = tolower(*cp);
}
cp++;
}
return allalpha;
}
/* ISSOL -- Test whether the words assembled so far constitute
a valid solution. */
static int issol(int n) {
int i, j;
for (i = 1; i <= n; i++) {
for (j = 1; j < n; j++) {
if (cand[i][j] != cand[j][i]) {
return FALSE;
}
}
}
return TRUE;
}
/* TESTSOL -- Test for a solution for a given letter. Upon
finding a solution at that level, this function plugs
the candidate word into the cand[] array and calls
itself recursively to search for solutions for the
next letter. If a solution is found for the last
letter, print the complete square and return. */
static void testsol(int letter) {
int k, l, m;
for (k = 0; k < nwl[IX(target[letter])]; k++) {
char *w = words[IX(target[letter])][k];
/* printf("L = %d w = %s cand = %s\n", letter, cand[letter - 1], w); /* Show candidate tests */
if (cand[letter - 1][letter] == w[letter - 1]) {
cand[letter] = w;
if (letter == (ltarget - 1)) {
if (issol(letter)) {
printf("Solution:\n");
for (l = 0; l <= letter; l++) {
printf(" ");
for (m = 0; m < (int) strlen(cand[l]); m++) {
printf(" %c", cand[l][m]);
}
printf("\n");
}
}
} else {
if (issol(letter)) {
testsol(letter + 1);
}
}
}
}
}
/* Main program */
int main(int argc, char *argv[])
{
FILE *fp;
char s[132];
if (argc == 2) {
target = argv[1];
} else {
fprintf(stderr, "usage: %s word\n", argv[0]);
return 2;
}
/* Validate and prepare target word. */
if (!lcase(target)) {
fprintf(stderr, "%s: cannot square word with non-alphabetic character.\n", argv[0]);
return 2;
}
ltarget = strlen(target);
if (ltarget > MAXWORD) {
fprintf(stderr, "Length of target word (%d) exceeds the maximum of %d.\n",
ltarget, MAXWORD);
return 2;
}
/* Load the portion of dictionary that we need into memory. */
memset(nwl, 0, sizeof nwl);
fp = fopen(DICT, "r");
if (fp == NULL) {
fprintf(stderr, "Cannot open dictionary file: %s\n", DICT);
}
while (fgets(s, sizeof s, fp)) {
/* Chop EOL this way because some dictionaries have
MS-DOS CR/LF sequences. */
while (isspace(s[strlen(s) - 1])) {
s[strlen(s) - 1] = 0;
}
/* Discard any dictionary entry with a non-alphabetic character
in it. This isn't strictly necessary, but the problem was
posed as a crossword puzzle, and the chance of finding
solutions for words with non-alphabetic characters
(for example, "we're") is vanishingly small. Note:
if you're thinking of loosening this restriction, note
that the indexing of the radix sort by first letter
assumes only characters between 'a' and 'z'. If you
permit other initial characters, you'll have to expand the
words[] and nwl[] arrays and modify the IX() macro accordingly. */
if (lcase(s)) {
/* Filter for words which begin with letters of the target
and are short enough to be candidates. */
if (strchr(target + 1, s[0]) != NULL && strlen(s) == ltarget) {
int x = IX(s[0]);
if (nwl[x] >= NW) {
fprintf(stderr, "Boom!!! More than %d words starting with \"%c\".\n",
NW, s[0]);
fprintf(stderr, " Rebuild with a larger setting for #define NW\n");
exit(1);
}
words[x][nwl[x]++] = strdup(s);
/*printf("%s\n", s); /* Print candidate words from dictionary */
}
}
}
fclose(fp);
#ifdef DIAGNOSTICS
/* Print summary of candidate words. */
for (i = 'a'; i <= 'z'; i++) {
if (nwl[IX(i)] > 0) {
fprintf(stderr, "%c %5d\n", i, nwl[IX(i)]);
}
}
#endif
/* Search for solutions. */
cand[0] = target; /* Set first level candidate as target word */
testsol(1); /* Invoke first level solution seeker */
return 0;
}