Acrostic Squares

The Acrostic Square is a square which contains the same words across as down. The canonical example: 

 
SATOR
AREPO
TENET
OPERA
ROTAS

Recently in the news is the old problem of trying to come up with a 10x10 square, the discovery of which is said to grant one a "lifetime of immortality"[sic]. The news article is actually about the work of Ted Clarke from 1999. His solution: 

 
DISCUSSING
INCANTATOR
SCARLATINA
CARNITINES
UNLIKENESS
STATESWREN
SATINWEAVE
ITINERATES
NONESEVENT
GRASSNESTS

This solution, like other stabs at a 10 square, is a wee on the iffy side, seeing as how certain words (e.g. nonesevent, stateswren) are not, how shall we say, words. Be that as it may, I thought this looked like a perfect problem for a python script to strangle. Using a set of word lists and a python script, I can safely say that the 10 worder is outside of the bounds of most viable English. Even that 20,302 word long list contains no set of words that can form a viable square.

Using the wordox lists, I was able to calculate many thousands of 5x5 and 6x6 squares (I didn't count them all), 10,501 7x7 squares, and 5 8x8 squares. The 8x8's: 

 
c a r b o r a s
a p e r i e n t
r e c a l l e r
b r a s s i c a
o i l s e e d s
r e l i e v o s
a n e c d o t e
s t r a s s e s
------
c r a b w i s e
r a t l i n e s
a t l a n t e s
b l a s t e m a
w i n t e r l y
i n t e r t i e
s e e m l i e r
e s s a y e r s
------
n e r e i d e s
e n e r g i s e
r e s o n a t e
e r o t i z e d
i g n i t e r s
d i a z e p a m
e s t e r a s e
s e e d s m e n
------
n e r e i d e s
e t e r n i s e
r e l o c a t e
e r o t i z e d
i n c i t e r s
d i a z e p a m
e s t e r a s e
s e e d s m e n
------
n e r e i d e s
e t e r n i s e
r e n o v a t e
e r o t i z e d
i n v i t e r s
d i a z e p a m
e s t e r a s e
s e e d s m e n
------

These, admittedly, are not very satisfying, as their words are substantially odd. However, they are officially recognized words for both Scrabble and Wordox, so I stand by 'em. My script found that there were no larger squares possible in the available words.

Here is the script. To run it, simply save it to a file, and call it from the command line with a wordlist filename as the only argument. The wordlist file should have one word per line in like case (either all lower or all upper).

Toggle line numbers 
   1 
   2 class AcrosticSquare:
   3     def __init__(self, wordlistfile):
   4         self.wordlist = [word.strip() for word in open(wordlistfile).read().split('\n')]
   5         self.size = len(self.wordlist[0])
   6 
   7         # the number of unique letters in the acrostic square
   8         self.limit = (self.size * self.size + self.size) / 2
   9 
  10         """ The planned arrangement of data in self.letters (the numbers are the 'index'):
  11         0  1  2  3  4
  12         1  5  6  7  8
  13         2  6  9  10 11
  14         3  7  10 12 13
  15         4  8  11 13 14
  16         """
  17         self.letters = [ [ None for i in xrange(self.size) ] for i in xrange(self.size) ]
  18         self.options = [ [ None for i in xrange(self.size) ] for i in xrange(self.size) ]
  19         self.lettermap = {}
  20 
  21         self.index2coords = {}
  22 
  23         # Build a map for convenient getting of coordinates
  24         row = -1
  25         rowsum = 0
  26         for i in xrange(self.limit):
  27             if (i + rowsum) % self.size == 0:
  28                 row += 1
  29                 rowsum = sum(range(row + 1))
  30             col = (rowsum + i) % self.size
  31             self.index2coords[i] = (col, row)
  32 
  33         # Build the letter tree
  34         for word in self.wordlist:
  35             struct = self.lettermap
  36             for letter in word:
  37                 if letter not in struct:
  38                     struct[letter] = {}
  39                 struct = struct[letter]
  40 
  41     def report(self, answer):
  42         if answer != None:
  43             for x in answer:
  44                 for a in x:
  45                     print a,
  46                 print
  47             print "------"
  48 
  49     def run(self, index = 0):
  50         if index == self.limit:
  51             return self.letters
  52 
  53         col, row = self.index2coords[index]
  54 
  55         if col > 0:
  56             colChoices = self.options[col - 1][row][0]
  57         else:
  58             colChoices = self.lettermap
  59         if row > 0:
  60             rowChoices = self.options[col][row - 1][1]
  61         else:
  62             rowChoices = self.lettermap
  63 
  64         for letter in colChoices:
  65             if letter in rowChoices:
  66                 self.letters[col][row] = letter
  67                 self.letters[row][col] = letter
  68                 self.options[col][row] = [ colChoices[letter], rowChoices[letter] ]
  69                 self.options[row][col] = [ rowChoices[letter], colChoices[letter] ]
  70 
  71                 result = self.run( index + 1)
  72                 self.report(result)
  73 
  74         return None
  75 
  76 #----------------- runnit
  77 import sys
  78 try:
  79     file = sys.argv[1]
  80 except IndexError:
  81     print "Please specify a word list to use."
  82     sys.exit(1)
  83 
  84 a = AcrosticSquare(file)
  85 a.run()
© 2008