Advertisement
acclivity

pyFindMinimumPath

Aug 18th, 2022
521
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.83 KB | Software | 0 0
  1. import itertools
  2. import time
  3.  
  4. array = [(131, 673, 234, 103, 18, 444, 333),
  5.          (201, 96, 342, 965, 150, 111, 222),
  6.          (630, 803, 746, 422, 111, 44, 77),
  7.          (630, 803, 746, 422, 111, 44, 77),
  8.          (805, 732, 524, 37, 331, 777, 123)]
  9.  
  10. ymax = len(array)
  11. xmax = len(array[0])
  12. select = ["D"] * (ymax - 1) + ["R"] * (xmax - 1)
  13. perms = itertools.permutations(select, ymax + xmax - 2)
  14.  
  15. st = time.time()
  16. mintot = float('inf')
  17. minpath = ""
  18. for path in perms:
  19.     x, y = 0, 0
  20.     tot = array[y][x]
  21.     for direct in path:
  22.         if direct == "R":
  23.             x += 1
  24.         else:
  25.             y += 1
  26.         tot += array[y][x]
  27.         if tot > mintot:
  28.             break
  29.     if tot < mintot:
  30.         mintot = tot
  31.         minpath = path
  32.  
  33. en = time.time()
  34. print(f"{minpath=}, {mintot=}  time= {en-st:.2f}")
  35.  
  36.  
  37.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement