Edsger Hates Getting Wet

Let $f(n,m)$ be the number of paths of minimum length starting in $(n,m)$ , it's easy to see that

$f(n)=\begin{cases} 0 & if \; n \gt 25 \lor m \gt 25 \lor grid(n,m)=\boxed{\#} \\ 1 & if \; n=25 \land m=25 \\ 1+f(n+1,m)+f(n,m+1) & otherwise \end{cases}$

Here is my dynamic programming approach. It is the same idea as in the solution of @Brian Riccardi .

 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

"""
solution of:
https://brilliant.org/practice/trees-level-4-challenges/?p=3
"""
import urllib
def get_raw_data():
    """
    returns the input data for the puzzle
    """
    url = 'https://pastebin.com/raw/8C49dRQx'
    tmp_data = urllib.request.urlopen(url).read().decode("utf-8").split('\r\n')
    return [list(_) for _ in tmp_data]

def find_number_of_min_paths(raw_data, start_pos, end_pos):
    """
    find the number of shortest paths connecting start_pos and end_pos
    on a board described by raw_data
    """
    res_data = {}
    def inner(in_pos):
        nonlocal res_data
        res = 0
        pos_x, pos_y = in_pos
        if in_pos in res_data:
            res = res_data[in_pos]
        elif in_pos == end_pos:
            res = 1
        elif pos_y < len(raw_data) and pos_x < len(raw_data[pos_y]) and \
            raw_data[pos_y][pos_x] == '.':
            res = inner((pos_x, pos_y+1))+inner((pos_x+1, pos_y))
            res_data[in_pos] = res
        return res
    return inner(start_pos)
RAW_DATA = get_raw_data()
RES = find_number_of_min_paths(RAW_DATA, (0, 0), (24, 24))
print(f"Number of paths: {RES}")