> I'd suggest googling for 'trie'. Tries are method of
> indexing sets of strings by prefix.
Ah, will look it up.
> As I recall, English words are more similar at the
> front, so once you have an indexing scheme you'll
> probably to do even less work if you index and search
> from the back of the words towards the front.
I'll have to consider that. In the meantime, my current version is
much improved - it caches rejects, so that if one word starting with
'ab' fails, it doesn't bother testing any further words starting with
'ab'. Also I started using psyco on it.
Alan
import psyco
psyco.full()
sixwords = open('sixwords.txt', 'r')
words = sixwords.readlines()
sixwords.close()
words = [x.strip() for x in words]
worddict = {}
for w in words:
for x in range(1,7):
y = w[0:x]
try:
worddict[y].append(w)
except KeyError:
worddict[y] = [w]
def isviable(big):
v = 0
while v<6:
if not big[v::6] in worddict:
return v
v += 1
return 7
counter = 0
joincounter = 0
def solve(currentwords, depth):
global counter, joincounter
counter += 1
if len(currentwords) == 6:
s = open('success.txt', 'a')
print >>s, depth, counter, joincounter, currentwords
for q in currentwords:
print >>s, q
print >>s, "\n\n"
s.close()
return True
else:
print "currentwords", currentwords, counter, joincounter
big = ''.join(currentwords)
prefixes = big[0::6]
nextletterset = list( set( [x[len(currentwords)] for x in
worddict[prefixes]] ) )
for letter in nextletterset:
rejects = {}
for maybefuture in worddict[letter]:
rejectmatches = False
rcount = 0
while rcount<6:
if maybefuture[:rcount+1] in rejects:
rejectmatches = True
break
rcount += 1
if rejectmatches:
continue
joincounter += 1
matches = isviable(big + maybefuture)
if matches == 7:
solve( currentwords + [maybefuture], depth + 1 )
else:
rejects[ maybefuture[:matches+1] ] = 0
seed=['enigma']
#seed = ['stoned','arseno','lemurs','abomas']
import cProfile
cProfile.run('print solve(seed, 1)')
_______________________________________________
Tutor maillist - [email protected]
http://mail.python.org/mailman/listinfo/tutor
