Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Feel free to add more classes/helper functions if you like, code quality counts!
- import queue
- class RobotRouter:
- # This class will be initialized with the map features from the problem input.
- # barriers and laserCoordinates are arrays of Coordinate objects.
- # laserDirections is an array of strings representing the direction of
- # the corresponding laser in laserCoordinates.
- def __init__(self, barriers, laserCoordinates, laserDirections):
- self.barriers = set(barriers)
- self.lasers = instantiateLasers(barriers, laserCoordinates, laserDirections)
- # This method will be called to get your optimal route.
- # origin and destination are Coordinate objects (with x and y properties)
- # It should return a list of Coordinate objects,
- # starting with the origin and ending with the destination.
- # If you could not find a valid route, return an empty list.
- def route(self, origin, destination):
- nodes = queue.Queue()
- visited = {}
- prev = {}
- prev[origin] = origin
- nodes.put(origin)
- while not nodes.empty():
- lastnode = nodes.get()
- visited[lastnode] = True
- if lastnode == destination:
- # generating the path to return
- pathnode = lastnode
- path = []
- while prev[pathnode] != pathnode:
- path.append(pathnode)
- pathnode = prev[pathnode]
- path.append(pathnode)
- return path[::-1]
- up = Coordinate(lastnode.x, lastnode.y + 1)
- down = Coordinate(lastnode.x, lastnode.y - 1)
- right = Coordinate(lastnode.x + 1, lastnode.y)
- left = Coordinate(lastnode.x - 1, lastnode.y)
- if self.isAccessible(up) and up not in visited:
- nodes.put(up)
- prev[up] = lastnode
- if self.isAccessible(down) and down not in visited:
- nodes.put(down)
- prev[down] = lastnode
- if self.isAccessible(right) and right not in visited:
- nodes.put(right)
- prev[right] = lastnode
- if self.isAccessible(left) and left not in visited:
- nodes.put(left)
- prev[left] = lastnode
- return []
- def isAccessible(self, coordinate):
- if coordinate in self.barriers:
- return False
- for laser in self.lasers:
- if laser.hits(coordinate):
- return False
- return True
- def instantiateLasers(barriers, laserCoordinates, laserDirections):
- lasers = []
- for i in range(len(laserCoordinates)):
- origin = laserCoordinates[i]
- direction = laserDirections[i]
- laser = Laser(origin, direction)
- lasers.append(laser)
- for barrier in barriers:
- if direction == "N" and barrier.y > origin.y:
- if laser.limit == None:
- laser.limit = barrier
- else:
- laser.limit = Coordinate(origin.x, min(laser.limit.y, barrier.y))
- if direction == "S" and barrier.y < origin.y:
- if laser.limit == None:
- laser.limit = barrier
- else:
- laser.limit = Coordinate(origin.x, max(laser.limit.y, barrier.y))
- if direction == "E" and barrier.x > origin.x:
- if laser.limit == None:
- laser.limit = barrier
- else:
- laser.limit = Coordinate(min(laser.limit.x, barrier.x), barrier.y)
- if direction == "W" and barrier.x < origin.x:
- if laser.limit == None:
- laser.limit = barrier
- else:
- laser.limit = Coordinate(max(laser.limit.x, barrier.x), barrier.y)
- return lasers
- class Laser:
- def __init__(self, origin, direction, limit = None):
- self.origin = origin
- self.direction = direction
- self.limit = limit
- def hits(self, coord):
- if self.direction == "N":
- if coord.x == self.origin.x and coord.y >= self.origin.y:
- if self.limit == None:
- return True
- if self.limit != None and coord.y < self.limit.y:
- return True
- return False
- elif self.direction == "S":
- if coord.x == self.origin.x and coord.y <= self.origin.y:
- if self.limit == None:
- return True
- if self.limit != None and coord.y > self.limit.y:
- return True
- return False
- elif self.direction == "E":
- if coord.y == self.origin.y and coord.x >= self.origin.x:
- if self.limit == None:
- return True
- if self.limit != None and coord.x < self.limit.x:
- return True
- return False
- else:
- if coord.y == self.origin.y and coord.x <= self.origin.x:
- if self.limit == None:
- return True
- if self.limit != None and coord.x > self.limit.x:
- return True
- return False
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement