Project Euler Problem 67

Solution

Answer: 7273

1. Mathematical analysis

This problem is a classic dynamic programming problem on a triangle.

We are given a triangle of numbers and want the maximum sum path from top to bottom, where from each number we may move only to one of the two adjacent numbers directly below.

For the small example:

$$\begin{array}{cccc} 3\ 7 & 4\ 2 & 4 & 6\ 8 & 5 & 9 & 3 \end{array}$$

The best route is:

$$3 \to 7 \to 4 \to 9$$

giving:

$$3+7+4+9=23$$

Why brute force is impossible

A triangle with 100 rows has:

$$2^{99}$$

possible paths, because at each step (except the last row) there are 2 choices.

That is astronomically large:

$$2^{99}\approx 6.3\times 10^{29}$$

So exhaustive search is infeasible.

Key insight: work bottom-up

Suppose we know the best possible total from every position in a row to the bottom.

Then for any entry $x$, the best total starting there is:

$$x + \max(\text{left child}, \text{right child})$$

If an entry has children $a$ and $b$, then:

$$\text{best}(x) = x + \max(\text{best}(a), \text{best}(b))$$

So we can process the triangle from the bottom upward.

Example

Start from:

$$\begin{array}{cccc} 3\ 7 & 4\ 2 & 4 & 6\ 8 & 5 & 9 & 3 \end{array}$$

Bottom row stays:

$$8,\ 5,\ 9,\ 3$$

Move up:

$$2+\max(8,5)=10$$

$$4+\max(5,9)=13$$

$$6+\max(9,3)=15$$

New row:

$$10,\ 13,\ 15$$

Continue:

$$7+\max(10,13)=20$$

$$4+\max(13,15)=19$$

Finally:

$$3+\max(20,19)=23$$

This yields the correct answer for the sample.

The complexity is:

Time: $O(n^2)$
Memory: $O(1)$ extra if we modify the triangle in place

For 100 rows, this is extremely fast.

2. Python implementation

# Read the triangle from the file
with open("0067_triangle.txt") as f:
    triangle = [list(map(int, line.split())) for line in f]

# Work from the second-last row upward
for row in range(len(triangle) - 2, -1, -1):
    for col in range(len(triangle[row])):
        # Add the larger of the two children
        triangle[row][col] += max(
            triangle[row + 1][col],
            triangle[row + 1][col + 1]
        )

# The top element now contains the maximum total
print(triangle[0][0])

3. Code walkthrough

Read the triangle

triangle = [list(map(int, line.split())) for line in f]

Each line of the text file becomes a row of integers.

Example:

becomes:

[
    [3],
    [7, 4],
    [2, 4, 6],
    [8, 5, 9, 3]
]

Process bottom-up

for row in range(len(triangle) - 2, -1, -1):

We start from the second-last row, since the last row has no children.

Update each entry

triangle[row][col] += max(
    triangle[row + 1][col],
    triangle[row + 1][col + 1]
)

Each entry is replaced by:

$$\text{current value} + \max(\text{two children})$$

This stores the best possible total from that position downward.

Final result

After finishing, the triangle’s top element contains the maximum total:

triangle[0][0]

For the sample triangle this becomes:

which matches the problem statement.

4. Final verification

The method is mathematically optimal via dynamic programming.
Runtime is tiny for 100 rows ($\sim 5000$ operations).
This is the known efficient solution intended by the problem.
Evaluating the provided triangle.txt yields the exact maximum path sum:

$$7273$$

Answer: 7273