Path sum: two ways

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

$$ \begin{pmatrix} \color{red}{131} & 673 & 234 & 103 & 18\\ \color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & 150\\ 630 & 803 & \color{red}{746} & \color{red}{422} & 111\\ 537 & 699 & 497 & \color{red}{121} & 956\\ 805 & 732 & 524 & \color{red}{37} & \color{red}{331} \end{pmatrix} $$

Find the minimal path sum, in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

Idea

A recursive problem. Could be solved by split into smaller matrix: bottom left part, top right part, horizontal inner part and vertical inner part.

Use DP to record computed smaller matrix result.

In [1]:
from urllib.request import urlopen
In [2]:
with urlopen('https://projecteuler.net/project/resources/p081_matrix.txt') as f:
    resp = f.read().decode('utf-8')
In [3]:
matrix = [list(map(int, line.split(','))) for line in resp.splitlines()]
In [4]:
len(matrix), len(matrix[0])
Out[4]:
(80, 80)
In [5]:
example_matrix = [
    [131, 673, 234, 103, 18],
    [201, 96, 342, 965, 150],
    [630, 803, 746, 422, 111],
    [537, 699, 497, 121, 956],
    [805, 732, 524, 37, 331]
]
In [6]:
def get_smaller_matrix(original_coordinate, part):
    tuple_add = lambda t1, t2: (t1[0]+t2[0], t1[1]+t2[1])
    original_top_left, original_bottom_right = original_coordinate
    if part == 'bl':
        return tuple_add(original_top_left, (1, 0)), tuple_add(original_bottom_right, (0, -1))
    elif part == 'tr':
        return tuple_add(original_top_left, (0, 1)), tuple_add(original_bottom_right, (-1, 0))
    elif part == 'hi':
        return tuple_add(original_top_left, (1, 0)), tuple_add(original_bottom_right, (-1, 0))
    elif part == 'vi':
        return tuple_add(original_top_left, (0, 1)), tuple_add(original_bottom_right, (0, -1))
    else:
        raise ValueError('parameter part must be "bl"(for bottom left) or "tr"(for top right)"', 
                         'or "hi"(for horizontal inner) or "vi"(for vertical inner)')
In [7]:
get_smaller_matrix(((0, 0), (4, 4)), 'bl'), get_smaller_matrix(((0, 0), (4, 4)), 'tr')
Out[7]:
(((1, 0), (4, 3)), ((0, 1), (3, 4)))
In [8]:
def solve(matrix):
    record = {}
    def get_min(coordinate):
        if coordinate not in record:
            record[coordinate] = min_path_sum(coordinate)
        return record[coordinate]
        
    def min_path_sum(coordinate):
        top_left, bottom_right = coordinate
        if top_left == bottom_right:
            return matrix[top_left[0]][top_left[1]]
        elif top_left[0] == bottom_right[0]:
            return sum(matrix[top_left[0]][top_left[1]:bottom_right[1]+1])
        elif top_left[1] == bottom_right[1]:
            return sum([matrix[r][top_left[1]] for r in range(top_left[0], bottom_right[0]+1)])
        
        top_left_v, bottom_right_v = matrix[top_left[0]][top_left[1]], matrix[bottom_right[0]][bottom_right[1]]
        
        
        candidate_min = []
        bottom_left_coordinate = get_smaller_matrix(coordinate, 'bl')
        candidate_min.append(get_min(bottom_left_coordinate))
        top_right_coordinate = get_smaller_matrix(coordinate, 'tr')
        candidate_min.append(get_min(top_right_coordinate))
        if bottom_right[0] - top_left[0] != 1:
            horizontal_inner_coordinate = get_smaller_matrix(coordinate, 'hi')
            candidate_min.append(get_min(horizontal_inner_coordinate))
        if bottom_right[1] - top_left[1] != 1:
            vertical_inner_coordinate = get_smaller_matrix(coordinate, 'vi')
            candidate_min.append(get_min(vertical_inner_coordinate))
            
        return min(candidate_min) + top_left_v + bottom_right_v
    
    return min_path_sum(((0, 0), (len(matrix)-1, len(matrix)-1)))
In [9]:
solve(example_matrix)
Out[9]:
2427
In [10]:
solve(matrix)
Out[10]:
427337