class Node(object):
def __init__(self, words, depth = 0):
self.children = []
self.words = words
self.depth = depth
self.predicates = [lambda w: self.words[0][2] == w[0],
lambda w: self.words[1][2] == w[2],
lambda w: self.words[0][0] == w[0] and self.words[2][0] == w[2]
]
def __repr__ (self):
return u"<Node: depth = %d, %s>" % (self.depth, self.words)
def fits(self, word):
return self.predicates[self.depth](word)
def solve(self, vocabulary):
if self.depth < 3: # search isn't finised
for word in vocabulary: # check all words
if self.fits(word) and word not in self.words: # this word wasn't used yet
child = Node(self.words + [word], self.depth + 1) # make a new Node
self.children.append(child)
child.solve(vocabulary) # recurse
def get_words(fname = 'words.txt'):
return open(fname, 'rU').read().split()
def get_solutions(node): # hard-coded approach: all the solutions have depth == 3
solutions = []
for child in node.children:
for gchild in child.children:
for ggchild in gchild.children:
if ggchild.words: solutions.append(ggchild.words) # skip empty nodes
return solutions
if __name__ == '__main__':
root = Node(['CAT'])
print "Solving"
root.solve(get_words())
print get_solutions(root)
Add a code snippet to your website: www.paste.org