Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import sys
- import scipy
- def addpt(pt1, pt2):
- return (pt1[0] + pt2[0], pt1[1] + pt2[1])
- def mdist(pt1, pt2):
- return abs(pt1[0] - pt2[0]) + abs(pt1[1] - pt2[1])
- def g(grid, pt):
- return grid[pt[0]][pt[1]]
- def inrange(pt, ysize, xsize):
- return pt[0] >= 0 and pt[1] >=0 and pt[0] < ysize and pt[1] < xsize
- DIRS=((1, 0), (0,1), (-1,0),(0,-1))
- grid = []
- for l in sys.stdin:
- l = l.strip()
- if l:
- grid.append(l)
- ysize = len(grid)
- xsize = len(grid[0])
- eloc = None
- sloc = None
- for j in range(ysize):
- for i in range(xsize):
- loc = (j,i)
- if g(grid, loc) == "E":
- eloc = loc
- elif g(grid, loc) == "S":
- sloc = loc
- # Find path. If there's only one path. it's trivia.
- path = [sloc]
- while path[-1] != eloc:
- loc = path[-1]
- spaces = 0
- found = False
- newlocs = []
- for d in DIRS:
- newloc = addpt(loc, d)
- if inrange(newloc, ysize, xsize) and g(grid, newloc) in ".ES":
- newlocs.append(newloc)
- if len(newlocs) > 2:
- print("FAIL: Too many paths", loc)
- exit(-1)
- elif not newlocs or (len(newlocs) == 1 and loc != sloc):
- print("FAIL: Not enough paths", loc)
- newloc = newlocs[0]
- if len(newlocs) > 1:
- if newloc == path[-2]:
- newloc = newlocs[1]
- elif newlocs[1] != path[-2]:
- print("FAIL: path not a line?", path, newlocs, path[-2])
- exit(-1)
- path.append(newloc)
- #print(path)
- kdpath = scipy.spatial.KDTree(path)
- maxcheat = 20
- mincheat = 2
- minsave = 100
- pairs = kdpath.query_pairs(maxcheat, p=1.0) # p = 1.0 means Manhattan metric
- tot = 0
- for (i, j) in pairs:
- cheatlen = mdist(path[i], path[j])
- savings = j - i - cheatlen
- if savings >= minsave:
- tot += 1
- print(tot)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement