Profile
Pastes: 71890
Members: 1383

Paste

Plain view | Edit code: here. | Add this to your website. | Report abuse.

Short URL: N/A

Pasted as Python by eglyph on Monday, September 6th, 2010 1:39am ( 4 years ago )

  1. class Node(object):
  2.     def __init__(self, words, depth = 0):
  3.         self.children = []
  4.         self.words = words
  5.         self.depth = depth      
  6.         self.predicates = [lambda w: self.words[0][2] == w[0],                              
  7.                            lambda w: self.words[1][2] == w[2],
  8.                            lambda w: self.words[0][0] == w[0] and self.words[2][0] == w[2]  
  9.                            ]
  10.  
  11.     def __repr__ (self):
  12.         return u"<Node: depth = %d, %s>" % (self.depth, self.words)
  13.  
  14.     def fits(self, word):
  15.         return self.predicates[self.depth](word)
  16.  
  17.     def solve(self, vocabulary):
  18.         if self.depth < 3:           # search isn't finised
  19.             for word in vocabulary:  # check all words
  20.                 if self.fits(word) and word not in self.words:        # this word wasn't used yet
  21.                     child = Node(self.words + [word], self.depth + 1) # make a new Node
  22.                     self.children.append(child)        
  23.                     child.solve(vocabulary)                           # recurse
  24.  
  25. def get_words(fname = 'words.txt'):
  26.     return open(fname, 'rU').read().split()
  27.  
  28. def get_solutions(node): # hard-coded approach: all the solutions have depth == 3
  29.     solutions = []
  30.     for child in node.children:
  31.         for gchild in child.children:
  32.             for ggchild in gchild.children:
  33.                 if ggchild.words: solutions.append(ggchild.words) # skip empty nodes
  34.  
  35.     return solutions
  36.            
  37. if __name__ == '__main__':
  38.     root = Node(['CAT'])
  39.     print "Solving"
  40.     root.solve(get_words())
  41.     print get_solutions(root)
  42.    
  43.  

Revise this Paste
Your Name:
Code Language:
 
Security Image:
Text seen in Image:
Comments

Nothing has been added as yet. Post a comment.