SHARE
TWEET

Untitled

a guest Aug 25th, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # Feel free to add more classes/helper functions if you like, code quality counts!
  2. import queue
  3.  
  4. class RobotRouter:
  5.     # This class will be initialized with the map features from the problem input.
  6.     # barriers and laserCoordinates are arrays of Coordinate objects.
  7.     # laserDirections is an array of strings representing the direction of
  8.     # the corresponding laser in laserCoordinates.
  9.     def __init__(self, barriers, laserCoordinates, laserDirections):
  10.         self.barriers = set(barriers)
  11.         self.lasers = instantiateLasers(barriers, laserCoordinates, laserDirections)
  12.  
  13.     # This method will be called to get your optimal route.
  14.     # origin and destination are Coordinate objects (with x and y properties)
  15.     # It should return a list of Coordinate objects,
  16.     # starting with the origin and ending with the destination.
  17.     # If you could not find a valid route, return an empty list.
  18.     def route(self, origin, destination):
  19.         nodes = queue.Queue()
  20.         visited = {}
  21.         prev = {}
  22.         prev[origin] = origin
  23.         nodes.put(origin)
  24.  
  25.         while not nodes.empty():
  26.             lastnode = nodes.get()
  27.             visited[lastnode] = True
  28.  
  29.             if lastnode == destination:
  30.                 # generating the path to return
  31.                 pathnode = lastnode
  32.                 path = []
  33.                 while prev[pathnode] != pathnode:
  34.                     path.append(pathnode)
  35.                     pathnode = prev[pathnode]
  36.  
  37.                 path.append(pathnode)
  38.                 return path[::-1]
  39.  
  40.  
  41.             up = Coordinate(lastnode.x, lastnode.y + 1)
  42.             down = Coordinate(lastnode.x, lastnode.y - 1)
  43.             right = Coordinate(lastnode.x + 1, lastnode.y)
  44.             left = Coordinate(lastnode.x - 1, lastnode.y)
  45.  
  46.             if self.isAccessible(up) and up not in visited:
  47.                 nodes.put(up)
  48.                 prev[up] = lastnode
  49.             if self.isAccessible(down) and down not in visited:
  50.                 nodes.put(down)
  51.                 prev[down] = lastnode
  52.             if self.isAccessible(right) and right not in visited:
  53.                 nodes.put(right)
  54.                 prev[right] = lastnode
  55.             if self.isAccessible(left) and left not in visited:
  56.                 nodes.put(left)
  57.                 prev[left] = lastnode
  58.  
  59.         return []
  60.    
  61.     def isAccessible(self, coordinate):
  62.         if coordinate in self.barriers:
  63.             return False
  64.         for laser in self.lasers:
  65.             if laser.hits(coordinate):
  66.                 return False
  67.        
  68.         return True
  69.  
  70. def instantiateLasers(barriers, laserCoordinates, laserDirections):
  71.     lasers = []
  72.     for i in range(len(laserCoordinates)):
  73.         origin = laserCoordinates[i]
  74.         direction = laserDirections[i]
  75.         laser = Laser(origin, direction)
  76.         lasers.append(laser)
  77.         for barrier in barriers:
  78.             if direction == "N" and barrier.y > origin.y:
  79.                 if laser.limit == None:
  80.                     laser.limit = barrier
  81.                 else:
  82.                     laser.limit = Coordinate(origin.x, min(laser.limit.y, barrier.y))
  83.             if direction == "S" and barrier.y < origin.y:
  84.                 if laser.limit == None:
  85.                     laser.limit = barrier
  86.                 else:
  87.                     laser.limit = Coordinate(origin.x, max(laser.limit.y, barrier.y))  
  88.             if direction == "E" and barrier.x > origin.x:
  89.                 if laser.limit == None:
  90.                     laser.limit = barrier
  91.                 else:
  92.                     laser.limit = Coordinate(min(laser.limit.x, barrier.x), barrier.y)
  93.             if direction == "W" and barrier.x < origin.x:
  94.                 if laser.limit == None:
  95.                     laser.limit = barrier
  96.                 else:
  97.                     laser.limit = Coordinate(max(laser.limit.x, barrier.x), barrier.y)  
  98.  
  99.     return lasers        
  100.                      
  101.  
  102. class Laser:
  103.     def __init__(self, origin, direction, limit = None):
  104.         self.origin = origin
  105.         self.direction = direction
  106.         self.limit = limit
  107.  
  108.     def hits(self, coord):
  109.         if self.direction == "N":
  110.             if coord.x == self.origin.x and coord.y >= self.origin.y:
  111.                 if self.limit == None:
  112.                     return True
  113.                 if self.limit != None and coord.y < self.limit.y:
  114.                     return True
  115.             return False
  116.         elif self.direction == "S":
  117.             if coord.x == self.origin.x and coord.y <= self.origin.y:
  118.                 if self.limit == None:
  119.                     return True
  120.                 if self.limit != None and coord.y > self.limit.y:
  121.                     return True
  122.             return False
  123.         elif self.direction == "E":
  124.             if coord.y == self.origin.y and coord.x >= self.origin.x:
  125.                 if self.limit == None:
  126.                     return True
  127.                 if self.limit != None and coord.x < self.limit.x:
  128.                     return True
  129.             return False
  130.         else:
  131.             if coord.y == self.origin.y and coord.x <= self.origin.x:
  132.                 if self.limit == None:
  133.                     return True
  134.                 if self.limit != None and coord.x > self.limit.x:
  135.                     return True
  136.             return False
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top