Pages

CodeEval Minimum Path Sum

Given a squared matrix of integers, find the minimal path sum from top-left to bottom-right, assuming that we can only move down or right.
This is CodeEval problem #72.

For example, give this matrix
4 6
2 8
We have just two possible paths: 4 -> 6 -> 8 and 4 -> 2 -> 8. It is immediate to see that the second one leads to the minimum sum of 14.

The structure of the problem recalls a Dynamic Programming solution table. I found it quite straightforward to use this thought to write a first solution:
def solution(data):  # 1
    dp = [[float(math.inf)] * (len(data) + 1)]  # 2
    for i in range(len(data)):
        dp.append([math.inf])
        dp[i+1].extend(data[i])

    end = len(dp)
    for i in range(1, end):  # 3
        for j in range(1, end):
            if i == 1 and j == 1:  # 4
                continue
            dp[i][j] += min(dp[i-1][j], dp[i][j-1])  # 5
    return dp[i][j]  # 6
1. The input parameter data contains a list of list of integers, representing the input matrix.
2. I copy the input in a DP-style table, where the first row and column have fake values. Usually, in a DP problem, zero is used for those cells. However here we need a value that should not be a candidate as minimum value. In a C-family language, I would have chosen a constant representing the maximum available integer. Python 3 has nothing like that, so I use math.inf, the floating-point positive infinity representation.
3. Calculate all the possible minimal path sum, skipping the first row and column.
4. This check looks unsatisfactory to me, but it is the less confusing way I found out to say that I don't have to do anything on the left-topmost element of the original matrix.
5. All the other cells are adjusted adding the smallest element on the immediate left or up.
6. There is nothing else to do, but returning the value in the bottom-right cell.

I found this solution to be elegant enough and easy to be understood. However I decided to write an alternative one to get rid of the buffer table, and also to navigate the table backward, from bottom-right to top-left.
def solution_2(data):
    last = len(data) - 1
    for i in range(last, -1, -1):
        for j in range(last, -1, -1):  # 1
            if i == last and j == last:  # 2
                continue
            if i == last:  # 3
                data[i][j] += data[i][j+1]
            elif j == last:
                data[i][j] += data[i+1][j]
            else:
                data[i][j] += min(data[i + 1][j], data[i][j+1])
    return data[0][0]  # 4
1. The loop variables are initially set to the last row/column and are decreased down to zero.
2. Again, nothing has to be done for the first cell.
3. Not having the extra-row/column, I have to add an extra check in the code for both i and j.
4. In this case the solution is stored in the top-left cell.

Not using another table should lead to a performance improvement, at least if large matrices are expected in input, and its cost in terms of less readability looks bearable to me. Scanning the table backward doesn't seem to give any advantage and makes the code a bit more obscure, so I would probably get rid of it.

I pushed the full python code on GitHub.

No comments:

Post a Comment