Matthew’s Blog - Highest path through a Number Pyramid

A number pyramid looks like this:

          1          
         2 7         
        1 3 8        
       3 8 4 3       
      8 6 8 4 2      
     8 6 5 4 8 3     
    8 0 3 1 3 5 0    
   7 6 3 4 3 3 7 4   
  0 8 7 8 3 7 0 4 2  
 0 2 7 0 3 6 7 1 6 4

What we want to do is to find the path through this pyramid that maximizes the score. A number is connected to the two numbers above it (and below it) visually. We have to traverse the entire pyramid.

A brute force approach would be to enumerate the pyramid fully. Since there are two connections for each number this means that the number of paths doubles for each additional row. That means we would have to generate and evaluate \(2^{rows-1}\) paths.

Code

import numpy as np

def make_pyramid(rows: int) -> np.ndarray:
    return np.array([
        np.random.randint(low=0, high=9, size=length+1)
        for length in range(rows)
    ], dtype=object)

Code

import numpy as np

def show_pyramid(pyramid: np.ndarray) -> str:
    rows = [
        " ".join(map(str, row))
        for row in pyramid
    ]
    max_length = len(rows[-1])
    return "\n".join(map(f" {{:^{max_length}}} ".format, rows))

Code

pyramid = make_pyramid(3)

print(show_pyramid(pyramid))

   7   
  2 5  
 1 6 6

The algorithm that I am going to take involves these mental steps:

A pyramid of one row has one path and thus that path is optimal
A pyramid of two rows can be mapped to a pyramid of one row by choosing the maximal value on the second row as the path (tie breaking method is irrelevant to outcome)
A pyramid of N rows can be mapped to a pyramid of N-1 rows by applying rule 2 to the last two rows

If we repeat this until we reach a single row pyramid we will have the maximum path score. If we track the path as we perform this we will arrive at the best path.

This should involve evaluating each value in the pyramid approximately twice. So the exponential brute force algorithm becomes linear.

Code

def solve(pyramid: np.ndarray) -> (np.ndarray, int):
    last_row = pyramid[-1]
    paths = [tuple() for _ in last_row]

    for row in pyramid[-2::-1]:
        # make the 1d row into a 2d array of shape (row-1, 2)
        # each sub-array is the pair of consecutive values
        # from the previously calculated row
        pairs = np.concatenate([
            last_row[:-1, None],
            last_row[1:, None],
        ], axis=1)

        # the argmax is the index of the maximum value
        # this makes the 2d pairs array into a 1d list of 0 or 1
        # 0 means go left, 1 means go right
        choices = pairs.argmax(axis=1)

        # the paths is a list of the individual choices at each step
        paths = [
            (choice,) + paths[index+choice]
            for index, choice in enumerate(choices)
        ]

        # recalculate the last row by adding the maximum pair value to the current row
        last_row = row + pairs.max(axis=1)

    # at this point there is only a single path left
    # add the 0 for the very first row (there is no choice)
    # and we can use cumulative sum (cumsum) to calculate the
    # position at each row.
    path = (0,) + paths[0]
    return np.array(path).cumsum(), last_row[0]

Code

import numpy as np

def show_solution(pyramid: np.ndarray, path: np.ndarray) -> str:
    rows = [
        " ".join(
            str(value) if index == point else "x"
            for index, value in enumerate(row)
        )
        for row, point in zip(pyramid, path)
    ]
    max_length = len(rows[-1])
    return "\n".join(map(f" {{:^{max_length}}} ".format, rows))

Code

pyramid = make_pyramid(10)
path, score = solve(pyramid)

print("pyramid:")
print(show_pyramid(pyramid))
print()
print("best path:")
print(show_solution(pyramid, path))
print()
print(f"best path has score: {score}")

pyramid:
          5          
         1 1         
        5 0 5        
       0 8 6 7       
      3 5 0 0 2      
     3 0 7 8 3 6     
    4 2 1 0 1 5 8    
   1 1 2 2 8 4 7 5   
  0 8 7 8 6 6 4 2 4  
 4 0 0 6 8 1 5 7 7 0 

best path:
          5          
         1 x         
        5 x x        
       x 8 x x       
      x 5 x x x      
     x x 7 x x x     
    x x x 0 x x x    
   x x x x 8 x x x   
  x x x x 6 x x x x  
 x x x x 8 x x x x x 

best path has score: 53

That was fun.