How can I change the index correct in a list? (Python)

Question

I wrote some code to calculate the maximum path in a triangle.

     75
   95 64
  17 47 82
 18 35 87 10
20 04 82 47 65

The maximum path sum is 75+95+82+87+82. I want that it calculates the maximum path from the adjecent numbers under the current layer. For example the maximum path sum must be: 75+95+47+87+82, because 47 'touches' 95 and 82doesn't. In the layer under this there is a choice between 35 and 87. So there is always a choice between two numbers. Does anyone how I can do this? This is my code:

lst = [[72], 
    [95,64], 
    [17,47,82], 
    [18,35,87,10],
    [20,4,82,47,65]]
something = 1
i = 0
mid = 0
while something != 0:
    for x in lst:
        new = max(lst[i])
        print(new)
        i += 1
        mid += new
    something = 0
print(mid)

Answer 1

For each row the choice should be between two values. If you always want to pick the maximum between those two values, the first solution works. If you want to maximize the sum by sometimes picking the lower value, the second solution works.

values = []

index = 0 # the index of the 'max' number in the first row

for row in lst:
    section = row[index:index+2] 
    value = max(section) 
    index = row.index(value) 
    values.append(value)

In this code we loop through each row, where the first row is just [75], the second row is [95, 64], etc.

For each row, we take the two numbers that are directly below our previous choice. For the first row, the choice must always be number in position 0, as it's the only number.

Then, we take the max of those two numbers. Then we take the index of that max number, which we will use to select the new two numbers on the next iteration.

Now all the values are stored in value. We can use sum(values) to get the sum.

Second solution

import itertools

# Create a new pyramid where each cell is the index of each number
index_lst = [[x for x in range(len(l))] for l in lst]

# Now index_lst looks like this:
# [[0], 
# [0, 1], 
# [0, 1, 2], 
# [0, 1, 2, 3], 
# [0, 1, 2, 3, 4]]

# get all possible paths, including those that are not valid such as [0, 0, 0, 0, 4]
all_possible_paths = itertools.product(*index_lst) 


def check_validity(path):
    # check the step size for each path.
    # A step it should always be less then 2
    # If the differene is too large, then it's not a valid path
    for x in range(0,len(path)-1):
        difference = abs(path[x] - path[x+1])
        if difference > 1:
            return False
    return True

# Filter out all the paths that are not valid
valid_path = []
for path in all_possible_paths:
    if check_validity(path):
        valid_path.append(path)
        

# For all the valid paths, get the path that returns the maximum value
# here the max funciton takes in the paths, and then converts the path to the sum of the values

optimal_path = max(valid_path, key = lambda e: sum([lst[row][index] for row, index in enumerate(e)]))

# Actually conver the optimal path to values
optimal_values = [lst[row][index] for row, index in enumerate(optimal_path)]


print(optimal_path)
print(optimal_values)
print(sum(optimal_values))

edit: Some extra details about this line

optimal_path = max(valid_path, key = lambda e: sum([lst[row][index] for row, index in enumerate(e)]))

First, the max function can take a key parameter. This just tells the max function how it should actually determine the max. For example, with input [[0,5],[1,0]] I can use the key parameter to tell max to use the second elements (i..e, 5 and 0) in each list to determine the max, instead of 0 and 1.

In this case, we give it a lambda function. This basically means we pass a function as the key parameter, without defining the function before hand. It is conceptually imilar to doing this

def fun(e):
   # do some stuff

optimal_path = max(valid_path, key = fun(e))

Next, I use a list comprehension. That's just a shorter way of writing a for loop.

[lst[row][index] for row, index in enumerate(e)]

Is the same thing as doing

 output = [] 
 for row, index in enumerate(e):
     output.append(lst[row][index])

The enumerate takes an iterable (like ['a','b','c']) and also gives the index for each element. Thus list(enumerate(a)) returns [(0, 'a'), (1, 'b'), (2, 'c')]. In the for loop I immediately assign them to row and index.

Answer 2

The "triangle" is an example of a graph (in the computer science sense, not the maths sense).

You will have to use recursion in order to solve this, or some kind of stochastic algorithm. Personally, I'd use the genetic algorithm since the problem is combinatorial.