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).
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()