Frank's typical day

This problem is primed for a dynamic programming solution. Let's define $F(i,j)$ to be the shortest time to reach the district in the $i$ th row and $j$ th column. Then we can see that $F(N,j) = d_{N,j}\qquad \forall j=1,2, \ldots,M$ $F(i,0) = F(i,M+1) = \infty \qquad \forall i=1,2,\ldots,N$ $F(i,j) = \min\big\{F(i+1,j-1), F(i+1,j), F(i+1,j+1)\big\} + d_{i,j}\qquad \forall i=1,2,\ldots, N-1,\quad j=1,2,\ldots,M$ [Note that the second line is just to make the computation in third line easier, and in the context of the problem $\infty$ can be any finite number larger than $\displaystyle\sum_{i,j}(d_{i,j})$ ]

Using this, the cost of the cheapest route is just $C = \min_j \{F(1,j)\}$

Note that I haven't cared to keep track of the $m_i$ or the $S$ . The reason for this is due to $S + \sum_{i=1}^{N-1} m_i = S + \sum_{i=1}^{N-1} (m_i - 2) + 2(N-1) = E + 2(N-1)$ where $E = \mbox{argmin}_j \{F(1,j)\}$ denotes the ending district's position. Therefore, the complete answer is $C + S + \sum_{i=1}^{N-1} m_i = C + E + 2(N-1) = \min_j \{F(1,j)\} + \mbox{argmin}_j\{F(1,j)\} + 2(N-1)$

When you run the dynamic programming scheme through your favorite language, we find $C = 9958, E = 465, 2(N-1) = 998$ $C + E + 2(N-1) = \boxed{11421}$

Here is python implementation of the solution. In the contrary, what @Brian Moehring has written in his solution, I did keep track of the minimal path and the starting position. This could be optimized.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

"""
solution of:
    https://brilliant.org/problems/franks-typical-day/
"""
import re
import math
def get_input_data(file_name):
    """
    reads the input file in the format as described in:
        https://brilliant.org/problems/franks-typical-day/
    """
    res_data = {}
    with open(file_name, 'r') as input_file:
        file_str = input_file.read()
    raw_data = re.split(r'\s+', file_str)
    raw_data = [int(_) for _ in raw_data if _]
    row_num = raw_data[0]
    col_num = raw_data[1]
    assert len(raw_data) == row_num*col_num+2
    cur_row = row_num
    cur_col = 1
    for _ in raw_data[2:]:
        res_data[(cur_row, cur_col)] = _
        cur_col += 1
        if cur_col > col_num:
            cur_col = 1
            cur_row -= 1
    assert cur_row == 0
    assert cur_col == 1
    return res_data

def find_solution(in_data):
    """
    returns the solution in the format described in:
        https://brilliant.org/problems/franks-typical-day/
    """
    def get_board_size(in_data):
        max_row_num = 0
        max_col_num = 0
        for (cur_row, cur_col) in in_data:
            max_col_num = max(cur_row, max_col_num)
            max_row_num = max(cur_col, max_row_num)
        return max_row_num, max_col_num
    max_row_num, max_col_num = get_board_size(in_data)
    res_data = {}
    def get_data(in_row_num, in_col_num):
        in_pos = (in_row_num, in_col_num)
        if in_pos in res_data:
            res = res_data[in_pos]
        elif in_row_num == max_row_num:
            res = (in_data[in_pos], [])
        else:
            cur_min_dir = 2
            cur_min_data = get_data(in_row_num+1, in_col_num)
            if in_col_num > 1:
                min_data_left = get_data(in_row_num+1, in_col_num-1)
                if cur_min_data[0] > min_data_left[0]:
                    cur_min_dir = 1
                    cur_min_data = min_data_left
            if in_col_num < max_col_num:
                min_data_right = get_data(in_row_num+1, in_col_num+1)
                if cur_min_data[0] > min_data_right[0]:
                    cur_min_dir = 3
                    cur_min_data = min_data_right
            res = (in_data[in_pos]+cur_min_data[0], [cur_min_dir]+cur_min_data[1])
            res_data[in_pos] = res
        return res
    full_min = math.inf
    full_min_path = []
    full_min_start_pos = -1
    for cur_start_pos in range(1, max_col_num+1):
        cur_data = get_data(1, cur_start_pos)
        if cur_data[0] < full_min:
            full_min = cur_data[0]
            full_min_path = cur_data[1]
            full_min_start_pos = cur_start_pos
    return full_min+full_min_start_pos+sum(full_min_path)

INPUT_DATA = get_input_data('Route.txt')
print(find_solution(INPUT_DATA))