Pyramid Scheme python solver

pyramid-solver.py

# Solver for Buzfeed's "Pyramid Scheme" game
import networkx as nx

class PyramidSolver:
    """ Solves pyramid puzzles of base length 5 """

    def __init__(self,inputlist,filename_validwords):
        self.inputlist = inputlist
        self.letterlist = sum(inputlist, [])
        self.pyramid_size = 5
        self.validwords = self.get_validwords(filename_validwords)
        self.found_solutions = set()
        self.adjency_graph = nx.Graph({
            0 : [1,2],
            1 : [0,2,3,4],
            2 : [0,1,4,5],
            3 : [1,4,6,7],
            4 : [1,2,3,5,7,8],
            5 : [2,4,8,9],
            6 : [3,7,10,11],
            7 : [3,4,6,8,11,12],
            8 : [4,5,7,9,12,13],
            9 : [5,8,13,14],
            10 : [6,11],
            11 : [6,7,10,12],
            12 : [7,8,11,13],
            13 : [8,9,12,14],
            14 : [9,13]
        })

    def __repr__(self):
        """ Pretty printing for pyramid puzzle """
        out_string = "\n"
        rows = self.pyramid_size
        for i in range(rows):
            for _ in range(1, rows-i):
                out_string += " "
            for j in range(i+1):
                letter = self.inputlist[i][j]
                out_string += letter
                out_string += " "
            out_string += "\n"
        return out_string

    def get_validwords(self,filename):
        """ Loads the set of valid words from a file """
        with open(filename) as f:
            lines = f.readlines()
        validwords = set(map(lambda x: x.replace("\n",""), lines))
        return validwords
    
    def nodelist_to_string(self,nodelist):
        """ Converts nodes in the pyramid to a corresponding string """
        return ''.join(map(lambda i: self.letterlist[i], nodelist))
    
    def solve(self):
        """ Finds solutions to the pyramid puzzle """
        for nodes_solution in self.backtrack_graph(self.adjency_graph):
            wordset_solution = tuple(map(self.nodelist_to_string, nodes_solution))
            if wordset_solution not in self.found_solutions:
                self.found_solutions.add(wordset_solution)
                yield wordset_solution
    
    # Graph methods

    def backtrack_graph(self,graph,nodelist_set=set()):
        """ Search the letter graph for a valid word set, using backtracking """
        if self.reject_graph(graph):
            return None 
        if self.accept_graph(graph): 
            yield nodelist_set 
            return None # Backtrack previous solution
        for (new_graph, new_nodelist_set) in self.next_graph(graph,nodelist_set): 
            yield from self.backtrack_graph(new_graph,new_nodelist_set)

    def reject_graph(self,graph):
        """ Reject graphs with any components containing n nodes, 0 < n < 3 """
        graph_components = list(nx.connected_components(graph))
        if len(graph_components) == 0: # Graph is empty, will be accepted
            return False
        smallest_component = min(graph_components, key=len)
        return (len(smallest_component) < 3) 

    def accept_graph(self,graph):
        """ Valid solution if the remaining graph is empty """
        return (len(graph) == 0)

    def next_graph(self,graph,nodelist_set):
        """ Generate next graph by removing the nodes of valid words """
        for nodelist in self.backtrack_nodelist(graph): 
            new_graph = self.remove_pathnodes(graph,nodelist)
            new_nodelist_set = nodelist_set.copy()
            new_nodelist_set.add(nodelist)
            yield new_graph, new_nodelist_set

    def remove_pathnodes(self,graph,nodelist):
        """ Remove valid nodes from graph """
        new_graph = graph.copy()
        new_graph.remove_nodes_from(nodelist)
        return new_graph
    
    # Nodelist methods

    def backtrack_nodelist(self,graph,nodelist=[]):
        """ Search the letter graph for a valid word, using backtracking """
        if self.reject_nodelist(nodelist):
            return None 
        if self.accept_nodelist(nodelist): 
            yield tuple(nodelist) 
        for new_nodelist in self.next_nodelist(graph,nodelist):
            yield from self.backtrack_nodelist(graph,new_nodelist)

    def reject_nodelist(self,nodelist):
        """ Reject lists with repeated elements """
        return (len(nodelist) != len(set(nodelist)))

    def accept_nodelist(self,nodelist):
        """ Accept if the word is 3 letters or longer & in the word set """
        if len(nodelist) >= 3:
            return self.nodelist_to_string(nodelist) in self.validwords
        return False

    def next_nodelist(self,graph,nodelist):
        """ Generate next node list with +1 node """
        for node in self.new_nodes(graph,nodelist):
            yield nodelist + [node]

    def new_nodes(self,graph,nodelist):
        """ Enumerate first nodes, or next adjacent nodes """
        if (len(nodelist) == 0):
            return graph.nodes
        else:
            return graph.neighbors(nodelist[-1])
            

if __name__ == "__main__":
    
    # Initialize pyramid and list of valid words
    my_pyramid = PyramidSolver(
        [
                    ['p'],
                  ['i','r'],
                ['a','a','o'],
              ['n','t','i','b'],
            ['o','g','u','e','o'],
        ],
        "wordlist.txt"
    )
    print(my_pyramid)

    # Solve for valid configurations
    for solution in my_pyramid.solve():
        print(solution)