Project Euler #79: Passcode derivation

  • + 0 comments

    This is perfect python code : 100%

    class DirectedGraph:
        def __init__(self):
            self.graph = {}
    
        def add_node(self, node):
            """Add a node to the graph."""
            if node not in self.graph:
                self.graph[node] = []
    
        def add_edge(self, from_node, to_node):
            """Add a directed edge from 'from_node' to 'to_node'."""
            if from_node not in self.graph:
                self.add_node(from_node)
            if to_node not in self.graph:
                self.add_node(to_node)
            self.graph[from_node].append(to_node)
    
        def get_neighbors(self, node):
            """Return a list of neighbors (outgoing edges) for a given node."""
            if node not in self.graph:
                return []
            return self.graph[node]
    
        def get_no_incoming_nodes(self):
            """Return a list of nodes with no incoming edges."""
            all_nodes = set(self.graph.keys())
            nodes_with_incoming = set()
            
            for neighbors in self.graph.values():
                for neighbor in neighbors:
                    nodes_with_incoming.add(neighbor)
            
            return sorted(list(all_nodes - nodes_with_incoming))
    
        def remove_node(self, node):
            """Remove a node and all edges connected to it (both incoming and outgoing)."""
            if node in self.graph:
                del self.graph[node]
            
            for key in list(self.graph.keys()):
                if node in self.graph[key]:
                    self.graph[key].remove(node)
    
        def remove_edge(self, from_node, to_node):
            """Remove a directed edge from 'from_node' to 'to_node'."""
            if from_node in self.graph and to_node in self.graph[from_node]:
                self.graph[from_node].remove(to_node)
    
        def num_nodes(self):
            """Return the number of nodes in the graph."""
            return len(self.graph)
    
        def display(self):
            """Display the graph in an easy-to-read format."""
            for node, neighbors in self.graph.items():
                print(f"{node} -> {neighbors}")
    
    
    
    # Example usage
    if __name__ == "__main__":
        T = int(input())
        graph = []
        for i in range(T):
            chain = input()
            graph.append(chain)
    
    g = DirectedGraph()
    for chain in graph:
        g.add_node(chain[0])
        g.add_node(chain[1])
        g.add_edge(chain[0], chain[1])
        g.add_node(chain[2])
        g.add_edge(chain[1], chain[2])
    
    try:
        output = ''
        while g.num_nodes() > 0:
            output += g.get_no_incoming_nodes()[0]
            g.remove_node(g.get_no_incoming_nodes()[0])
            # print(g.get_no_incoming_nodes())
            # g.display()
            # print()
        print(output)
    except:
        print('SMTH WRONG')