Welcome, guest! Login / Register - Why register?
[ Pastes: 81351 ] [ Members: 2143 ]

Paste

Short URL: N/A
Pasted as Python by eglyph on Monday, September 6th, 2010 1:39am ( 6 years ago )
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)
    

 

Revise this Paste

Your Name:
Code Language:

To minimise the influx of spam: you are required to register to post any code.