Advertisement
Mussab_Blue

Low cost Path Finder

Aug 18th, 2022 (edited)
485
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.05 KB | None | 0 0
  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.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement