Mail Archive


<-- Chronological -->
<-- Thread -->

word squares

Solution of "word squares" was a popular amusement among word freaks
in the 1800s.  A word square is a square grid of letters that reads
the same horizontally and vertically; for example, 

B e a
e a r
a r c

Here's a program to produce word squares, given an initial seed word
or two.  It runs under Python 1.5.2 and 2.1.1 on my machine, and it
needs the bsddb module, which you'll probably have if your Python runs
on Linux.

I ran it on all the 45404 words from /usr/share/dict/words on my
system, which took 3 hours and found 5797 word squares (12.77% of the
words could start word squares).  This means that it took, on average,
about a quarter of a second to try a word, and about two seconds to
find a word square.  The largest ones were for two seven-letter words,
"prepare" and "mergers":

kragen@detached:devel/wordsquares2$ cat mergers.wsq 
m e r g e r s
e t e r n a l
r e g a t t a
g r a v i t y
e n t i t l e
r a t t l e r
s l a y e r s
kragen@detached:devel/wordsquares2$ cat prepare.wsq 
p r e p a r e
r e m o d e l
e m u l a t e
p o l e m i c
a d a m a n t
r e t i n u e
e l e c t e d

There were 40 two-letter words, 509 three-letter words, 1999
four-letter words, 2760 five-letter words, 487 six-letter words, and
the above two seven-letter words that formed word squares.

# known bugs:
# only produces the first word square.
# error messages kind of suck.

import bsddb, os, string, stat, errno, sys

def startswith(seq, prefix):
    """Returns true if seq starts with prefix.

    Like string.startswith in Python 2.x."""
    return seq[:len(prefix)] == prefix

def possiblewords(wordlist, s, length):
    """Return a list of words that start with 's' and have length 'length'.

    Gets the words from wordlist, which can be a bsddb object or
    something supporting a similar protocol.  Its keys are of the form
    '%d %s' % (len(word), word).

    s = '%d %s' % (length, s)
    # 'agonizing' used to provoke a KeyError here --- set_location
    # apparently raises KeyError for '9 zn', at least with my
    # /usr/share/dict/words.  Presumably that's because it's after the
    # last item in the db file.
    try: key, value = wordlist.set_location(s)
    except KeyError: return []
    rv = []
    while 1:
        if not startswith(key, s): return rv
        spindex = string.index(key, ' ')
        key, value =

def possiblewordsexist(wordlist, s, length):
    "Return true if there are words starting with 's' of length 'length'."
    s = '%d %s' % (length, s)
    try: key, value = wordlist.set_location(s)
    except KeyError: return 0
    return startswith(key, s)

def wordsquare(wordlist, words):
    assert len(words) > 0
    for word in words: assert len(word) == len(words[0])

    # before this check, 'rage dbed' produced a "word square"
    # even though "d" isn't the second letter of "rage"
    for ii in range(len(words)):
        for jj in range(len(words)):
            assert words[ii][jj] == words[jj][ii]
    return compute_wordsquare(wordlist, words)

def compute_wordsquare(wordlist, words):
    size = len(words[0])
    if len(words) == size: return words
    prefixes = []
    for index in range(len(words), size):
        prefix = (string.join(map(lambda string, index=index:
                                  words), ''))
        if not possiblewordsexist(wordlist, prefix, size):
            # prune early; this makes this program several times faster
            # especially for impossible word squares
            return None
    candidates = possiblewords(wordlist, prefixes[0], size)
    for word in candidates:
        rv = compute_wordsquare(wordlist, words + [word])
        if rv is not None: return rv

def filenametrans(pathname):
    "Turn a pathname into a filename in the current dir."
    filename = string.replace(pathname, os.sep, '_')
    while filename[0] == '_': filename = filename[1:]
    return filename

def mtime(filename):
    return os.stat(filename)[stat.ST_MTIME]

def uptodate(sourcefile, dependentfile):
    sourcefilemtime = mtime(sourcefile)
    try: dependentfilemtime = mtime(dependentfile)
    except OSError, val:
        code, str = val
        if code == errno.ENOENT:
            return 0  # nonexistent, so not up to date
            raise  # some other error
    return sourcefilemtime < dependentfilemtime

def worddb(sourcefile="/usr/share/dict/words"):
    dbfile = filenametrans(sourcefile) + '.db'
    mustupdate = not uptodate(sourcefile, dbfile)
    dbfileobj = bsddb.btopen(dbfile, 'c')
    if mustupdate:
            sourcefileobj = open(sourcefile)
            # doesn't exist: dbfileobj.clear()
            for word in dbfileobj.keys(): del dbfileobj[word]
            for word in sourcefileobj.xreadlines():
                while word[-1] in '\r\n': word = word[:-1]
                dbfileobj['%d %s' % (len(word), word)] = '1'
            # if there's an exception, maybe we fucked up the file
            # so blow it away
    return dbfileobj

def printwordsquare(words):
    if words is None: print "No word square"
        for word in words:
            for char in word:
                print char,

def main(words):
    wordlist = worddb()
    try: square = wordsquare(wordlist, words)
    except AssertionError:
        print "Must specify at least one word; all words must be same length."
    if square is not None: return 0
    return 1

if __name__ == "__main__": sys.exit(main(sys.argv[1:]))

<-- Chronological --> <-- Thread -->

Reply via email to