# Low cost Path Finder

Aug 18th, 2022 (edited)
542
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. def find_path(grid):
2.     w, h = len(grid[0])-1, len(grid)-1 # width & height
3.
4.     def foo(x,y):
5.         if x < 0 or y < 0: return []
6.         if x==0 and y==0: return [[(x,y)]]
7.
8.         _paths = []
9.
10.         for i, j in [(1, 0), (0, 1)]:
11.             (path:=foo(x-i, y-j)) and [_paths.append([*p, (x,y)]) for p in path]
12.         return _paths
13.
14.     path = min(foo(h, w), key=lambda x: sum([grid[i][j] for i,j in x]))
15.
16.     for i, row in enumerate(grid):
17.         print(row,'\t'.rjust(6), ["#" if (i, ii) in path else n for ii, n in enumerate(row)])
18.     print()
19.
20.
21. g1 = [[131, 673, 234],
22.       [201, 96, 342],
23.       [630, 803, 200]]
24.
25. g2 = [[131, 673, 234, 103, 18],
26.      [201, 96, 342, 212, 400],
27.      [630, 803, 746, 322, 111]]
28.
29. g3 = [
30.     [131, 673, 234, 103, 18],
31.     [201, 96, 342, 965, 150],
32.     [630, 803, 746, 422, 111],
33.     [537, 699, 497, 121, 956],
34.     [805, 732, 524, 37, 331]]
35.
36. g4 = [[131, 673, 234, 103, 18],
37.      [201, 96, 342, 965, 150],
38.      [630, 803, 746, 422, 111],
39.      [537, 699, 400, 120, 956],
40.      [805, 732, 524, 37, 331],
41.      [805, 732, 524, 10, 100]]
42.
43.
44. find_path(g1)
45. find_path(g2)
46. find_path(g3)
47. find_path(g4)
48.
49.