Construct a directed acyclic graph with the nodes 1,2,\dots,100. The graph should have exactly x different paths from the node 1 to the node 100. The graph can have at most 1000 edges, and each edge must be unique.
In a file paths2.py
, implement the function create_edges
the returns the graph as a list of the edges. For example, the list [(1, 2), (4, 5)]
represents a graph with the two edges 1 \rightarrow 2 and 4 \rightarrow 5.
You can assume that x is in the range 0 \dots 10^9 in all tests.
You can test your function using the class CountPaths
in the course material. In the code template below, the method count_paths
should return 123456789, when the graph is correctly constructed.
class CountPaths: # you can copy this class from the course material def create_edges(x): # TODO if __name__ == "__main__": edges = create_edges(123456789) counter = CountPaths(range(1, 100 + 1)) for edge in edges: counter.add_edge(edge[0], edge[1]) print(counter.count_paths(1, 100)) # 123456789