Advertisement
Guest User

Untitled

a guest
Dec 20th, 2024
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.81 KB | Source Code | 0 0
  1. import sys
  2. import scipy
  3.  
  4. def addpt(pt1, pt2):
  5. return (pt1[0] + pt2[0], pt1[1] + pt2[1])
  6.  
  7. def mdist(pt1, pt2):
  8. return abs(pt1[0] - pt2[0]) + abs(pt1[1] - pt2[1])
  9.  
  10. def g(grid, pt):
  11. return grid[pt[0]][pt[1]]
  12.  
  13. def inrange(pt, ysize, xsize):
  14. return pt[0] >= 0 and pt[1] >=0 and pt[0] < ysize and pt[1] < xsize
  15.  
  16. DIRS=((1, 0), (0,1), (-1,0),(0,-1))
  17.  
  18. grid = []
  19. for l in sys.stdin:
  20. l = l.strip()
  21. if l:
  22. grid.append(l)
  23.  
  24. ysize = len(grid)
  25. xsize = len(grid[0])
  26. eloc = None
  27. sloc = None
  28. for j in range(ysize):
  29. for i in range(xsize):
  30. loc = (j,i)
  31. if g(grid, loc) == "E":
  32. eloc = loc
  33. elif g(grid, loc) == "S":
  34. sloc = loc
  35.  
  36. # Find path. If there's only one path. it's trivia.
  37. path = [sloc]
  38. while path[-1] != eloc:
  39. loc = path[-1]
  40. spaces = 0
  41. found = False
  42. newlocs = []
  43. for d in DIRS:
  44. newloc = addpt(loc, d)
  45. if inrange(newloc, ysize, xsize) and g(grid, newloc) in ".ES":
  46. newlocs.append(newloc)
  47. if len(newlocs) > 2:
  48. print("FAIL: Too many paths", loc)
  49. exit(-1)
  50. elif not newlocs or (len(newlocs) == 1 and loc != sloc):
  51. print("FAIL: Not enough paths", loc)
  52. newloc = newlocs[0]
  53. if len(newlocs) > 1:
  54. if newloc == path[-2]:
  55. newloc = newlocs[1]
  56. elif newlocs[1] != path[-2]:
  57. print("FAIL: path not a line?", path, newlocs, path[-2])
  58. exit(-1)
  59. path.append(newloc)
  60. #print(path)
  61. kdpath = scipy.spatial.KDTree(path)
  62. maxcheat = 20
  63. mincheat = 2
  64. minsave = 100
  65. pairs = kdpath.query_pairs(maxcheat, p=1.0) # p = 1.0 means Manhattan metric
  66. tot = 0
  67. for (i, j) in pairs:
  68. cheatlen = mdist(path[i], path[j])
  69. savings = j - i - cheatlen
  70. if savings >= minsave:
  71. tot += 1
  72. print(tot)
  73.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement