Hackbright Code Challenges

Max Path of Triangle: Solution

Max Path of Triangle: Solution

Problem

Max Path of Triangle

Whiteboard

Harder

Challenge

Medium

Concepts

Trees, Graphs

Download

maxpath-solution.zip


A good realization is that if a node at has two parents, it can look at the parents to decide which parent would have been more valuable to have traveled through.

We can keep track of, on each node, the “best score to have reached this node”, always choosing the better-parent and using it’s best score, plus that parent’s own data. Then, we just need to additionally keep track of the best score we found by the end of the list.

digraph nodes2 { 2 -> {5, a4} 5 -> {3, b4} a4 -> {b4, 7} 3 -> {1, a6} b4 -> {a6, 9} 7 -> {9, b6} a4 [label="4\nbest=6"] b4 [label="4\nbest=10"] a6 [label=6 label="6\nbest=17"] b6 [label=6 label="6\nbest=19"] 2 [style=filled fillcolor=pink label="2\nbest=2"] 5 [label="5\nbest=7"] 3 [label="3\nbest=10"] a4 [style=filled fillcolor=pink] 7 [style=filled fillcolor=pink label="7\nbest=13"] 9 [style=filled fillcolor=pink label="9\nbest=22"] 1 [label="1\nbest=11"] }

We can do this without having to traverse multiple paths, but just by visiting each node, and looking at it’s parent’s nodes.

maxpath.py
def maxpath(nodes):
    """Given list of nodes in triangle, return high-scoring path."""

    # START SOLUTION

    # Best score we've seen so far
    best = 0

    for n in nodes:

        if not n.parents:
            # For the root, it has no best-path
            n.best = n.value

        else:
            # Take best score of your higher parent and add this value
            n.best = n.value + max(p.best for p in n.parents)

        # Update best-we've-seen
        best = max(n.best, best)

    return best