Trees, Graphs
In a tree, a node can have many children, but each node can have only one parent:
A slightly-less-rigid structure is a “directed acyclic graph” (often called a “DAG”). This is a little more flexible than a tree, in that a node can have multiple parents. It’s still “directed”, meaning the arrows go in a particular direction, and “acyclic”, meaning there are no loops in it (it’s impossible to return to the same node a second time).
Here’s an example of a DAG:
(We’ll call this particular type of DAG a “triangle” in this challenge).
Imagine starting at the root node, 2. You can go down either to 5 or 4, and so on.
In this challenge, you want to find the highest-scoring path to walk the DAG. (In this example, this would be 2, 4, 7, 9 = 22):
We’ve created a Node class for you:
class Node(object):
"""Basic node class that keeps track fo parents and children.
This allows for multiple parents---so this isn't for trees, where
nodes can only have one children. It is for "directed graphs".
"""
def __init__(self, value):
self.value = value
self.children = []
self.parents = []
def __repr__(self):
return str(self.value)
We’ve also created a make_triangle function. This takes a list of node-level-data, and returns a list of nodes (where each node has the proper parents and children attributes).
For example, to make the triangle above:
>>> triangle = make_triangle([[2], [5, 4], [3, 4, 7], [1, 6, 9, 6]])
Now triangle is a list of those nodes.
In this challenge, you should write a maxpath function that takes that list of nodes, and returns the value of the best path:
>>> maxpath(triangle)
22
The data values in the triangle will always be positive, whole integers.
We’ve provided a stub function for you:
def maxpath(nodes):
"""Given list of nodes in triangle, return high-scoring path."""
Think of Good Runtime!
You could do this by exhaustively trying all of the possible paths — but for a large tree, this would be inefficient.
Can you think of a better way to solve this? There’s a O(n) solution to this problem.