Hackbright Code Challenges

Max Path of Triangle

Max Path of Triangle

Whiteboard

Harder

Challenge

Medium

Concepts

Trees, Graphs

Download

maxpath.zip

Solution

Max Path of Triangle: Solution


In a tree, a node can have many children, but each node can have only one parent:

digraph nodes { 1 -> { 2, 3 } 2 -> { 4, 5 } 3 -> { 6, 7 } }

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:

digraph nodes2 { 2 -> {5, a4} 5 -> {3, b4} a4 -> {b4, 7} 3 -> {1, a6} b4 -> {a6, 9} 7 -> {9, b6} a4 [label=4] b4 [label=4] a6 [label=6] b6 [label=6] }

(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):

digraph nodes2 { 2 -> {5, a4} 5 -> {3, b4} a4 -> {b4, 7} 3 -> {1, a6} b4 -> {a6, 9} 7 -> {9, b6} a4 [label=4] b4 [label=4] a6 [label=6] b6 [label=6] 2 [style=filled fillcolor=pink] a4 [style=filled fillcolor=pink] 7 [style=filled fillcolor=pink] 9 [style=filled fillcolor=pink] }

The Code

We’ve created a Node class for you:

maxpath.py
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:

maxpath.py
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.