Pages

CodeEval Pass Triangle

We are given as input a sequence of integers that we should think representing a triangle. We should return the maximum value we can get adding all values from the top vertex of the triangle down to the bottom, chosing a path moving always downwards between adjacent elements. This is CodeEval problem #89.

For example, if this is the triangle we get as input:
5
  9 6
 4 6 8
0 7 1 5
The expected solution is 5 + 9 + 6 + 7 = 27

I started thinking in the Dynamic Programming direction. Seeing that for a minimal triangle the result comes out comparing the two lower elements and then adding the bigger one to the higher one, I simply applied this rule to all the elements, starting from the bottom line up to the second from top.

Here is my python code:
def solution(data):  # 1
    for i in range(len(data) - 1, 0, -1):  # 2
        for j in range(len(data[i])-1):  # 3
            data[i-1][j] += max(data[i][j], data[i][j+1])  # 4
    return data[0][0]  # 5
1. The solution function is called passing as input parameter a list of list of integers. The first list contains just a value, the triangle top element. As usual, we can assume that the data we receive is as expected. No check is required.
2. The loop variable in this for-loop goes from the last line (3, in the example case) down to 1. This is the line from which I'm reading the values, I'm going to write in the line above.
3. Here the loop variable of the for-loop represents the index of the first element I'm comparing.
4. Calling max() I see which one is the selected value, and I add it to the element in the line above.
5. Finally I just have to return the top element, that now contains the result.

Notice that my code is destructive, since I use the input data as working area. This is usually considered not a problem, or even good, in this context (less code, cheaper and faster). Not so if the user of the function would like to do something else with its data!

The complete python script is on GitHub.

No comments:

Post a Comment