Tricky Triangularization

Computer Science Level 5

A root path is a path in a triangular lattice which contains exactly one vertex in each row.

What is the maximum sum of the numbers on the vertices of a root path in this lattice of 500 rows?

Details and Assumptions

For eg, in the following lattice, the vertex $\color{#3D99F6}{5}$ can only be connected to the $\color{#D61F06}{\text{red}}$ vertices in a root path.
$1\\\color{#D61F06}{2}\quad\color{#D61F06}{3}\\4\quad\color{#3D99F6} {5}\quad6\\7\quad\color{#D61F06}{8}\quad\color{#D61F06}{9}\quad 1$
All neighbouring vertices must be connected with an edge.
Explicit example of maximum sum root path, highlighted in red:

$\color{#D61F06}{3}\\ \color{#D61F06}{7}\quad 4\\ 2\quad \color{#D61F06}{4}\quad 6\\ 8\quad 5\quad \color{#D61F06}{9}\quad 3$
Bruteforce is not the best idea because $2^{499}$ paths exist. An efficient solution can find the answer well under a second.

Note: This problem is inspired by a Project Euler problem

The answer is 3714855.

1 solution

Arulx Z
Dec 15, 2015

An efficient way would be to iterate bottom up.

n = []

index = 499
tempMax = [0] * index

while index > 0:
    for x, count in zip(n[index - 1], xrange(index)):
        tempMax[count] = max(n[index][count], n[index][count + 1]) + x
    del n[-1]
    n[index - 1] = tempMax
    index -= 1
    tempMax = [0] * index

print n[0][0]

In my solution, I start from the bottom, find the maximum value of the adjacent cell and then add it up to the cell on the top.

Here's an example. Consider this lattice -

$1\\ 2\quad 3\\ 4\quad 5\quad 6\\ 7\quad 8\quad 9\quad 10$

Let's start working with the lowest row and try to eliminate it. From 4, you can go to 7 or 8. Since 8 is better, we eliminate 7. Since 8 is to largest option, we replace value of 4 with $8+4=12$ . From 5, you can do to 8 or 9. Since 9 is better, we eliminate 8 and replace 5 with $9+5=14$ . From 6, you can do to 9 or 10. Since 10 is better, we eliminate 9 and replace 6 with $10+6=16$ .

Now we have got a triangle with a smaller height -

$1\\ 2\quad 3\\ 12\quad 14\quad 16$

We can continue this process until only 1 row remains.

Moderator note:

Standard solution, but the writeup needs work. This solution is easily understood by someone who has already solved the problem using the same approach, but is not easily understood by someone who hasn't. Consider explaining the strategy that underlies your algorithm design.

Be careful with your definitions, and avoid common terms with accepted meaning. For example, a path is a sequence of edges between distinct vertices. You could define it as a "root path" instead.

Calvin Lin Staff - 5 years, 5 months ago

I have modified the question. Please recheck it.

Arulx Z - 5 years, 5 months ago

K, I've made further edits to improve the problem.

Calvin Lin Staff - 5 years, 5 months ago

@Calvin Lin – Thanks a lot!

Arulx Z - 5 years, 5 months ago

@Calvin Lin , looking at my answer again, I highly doubt if someone who has solved the problem will understand my solution either :p

I have modified the answer and explained my strategy.

Arulx Z - 5 years, 5 months ago

I think your approach is unnecessarily complicated. It is much easier to work top down instead. Using the example, we have:

$3 \quad 4 \\ 4 \quad 5 \quad 6 \\ 7 \quad 8 \quad 9 \quad 10$

and then:

$7 \quad 9 \quad 10 \\ 7 \quad 8 \quad 9 \quad 10$

and then:

$14 \quad 17 \quad 19 \quad 20$

This way, the number of calculations is about $Cn^2$ .

Calvin Lin Staff - 5 years, 5 months ago

I think that both approaches are a bit complicated. I took the bottom-up approach because in case of top down approach, an array of 500 elements is left. Since I need to find the largest element among them, the process is slower. The calculations required are about the same too for each approach.

Arulx Z - 5 years, 5 months ago

Tricky Triangularization

Note: This problem is inspired by a Project Euler problem

The answer is 3714855.

1 solution

Moderator note:

0 pending reports