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.
#!/usr/bin/python
# 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, ' ')
rv.append(key[spindex+1:])
key, value = wordlist.next()
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:
string[index],
words), ''))
if not possiblewordsexist(wordlist, prefix, size):
# prune early; this makes this program several times faster
# especially for impossible word squares
return None
prefixes.append(prefix)
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
else:
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:
try:
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'
sourcefileobj.close()
dbfileobj.sync()
except:
# if there's an exception, maybe we fucked up the file
# so blow it away
os.unlink(dbfile)
raise
return dbfileobj
def printwordsquare(words):
if words is None: print "No word square"
else:
for word in words:
for char in word:
print char,
print
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."
sys.exit(2)
printwordsquare(square)
if square is not None: return 0
return 1
if __name__ == "__main__": sys.exit(main(sys.argv[1:]))
|
|
