SHARE
TWEET

Untitled

a guest Aug 25th, 2019 82 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.             return coord.x == self.origin.x and coord.y >= self.origin.y and self.limit != None and coord.y < self.limit.y
  111.         elif self.direction == "S":
  112.             return coord.x == self.origin.x and coord.y <= self.origin.y and self.limit != None and coord.y > self.limit.y
  113.         elif self.direction == "E":
  114.             return coord.y == self.origin.y and coord.x >= self.origin.x and self.limit != None and coord.x < self.limit.x
  115.         else:
  116.             return coord.y == self.origin.y and coord.x <= self.origin.x and self.limit != None and coord.x > self.limit.x
  117.  
  118.            
  119.  
  120.        
  121.  
  122. class Coordinate:
  123.     def __init__(self, x, y):
  124.         self.x = x
  125.         self.y = y
  126.  
  127.     def __eq__(self, other):
  128.         return isinstance(other, self.__class__) and self.x == other.x and self.y == other.y
  129.  
  130.     def __hash__(self):
  131.         return hash((self.x, self.y))
  132.  
  133.     def __str__(self):
  134.         return '%d,%d' % (self.x, self.y)
  135.  
  136. import sys
  137.  
  138. def readCoordinate(rawCoordinate):
  139.     parts = rawCoordinate.split(',')
  140.     return Coordinate(int(parts[0]), int(parts[1]))
  141.  
  142. def writeMapAndRoute(origin, destination, barriers, laserCoordinates, laserDirections, route):
  143.     bottomLeft = origin
  144.     topRight = origin
  145.  
  146.     for coordinate in (destination, *barriers, *laserCoordinates, *route):
  147.         bottomLeft = Coordinate(min(bottomLeft.x, coordinate.x), min(bottomLeft.y, coordinate.y))
  148.         topRight = Coordinate(max(topRight.x, coordinate.x), max(topRight.y, coordinate.y))
  149.  
  150.     barrierSet = set(barriers)
  151.     lasers = { laserCoordinates[i]: laserDirections[i] for i in range(len(laserCoordinates)) }
  152.     routeSet = set(route)
  153.  
  154.     for y in range(topRight.y, bottomLeft.y - 1, -1):
  155.         for x in range(bottomLeft.x, topRight.x + 1):
  156.             coordinate = Coordinate(x, y)
  157.  
  158.             if coordinate == origin:
  159.                 sys.stdout.write('o')
  160.             elif coordinate == destination:
  161.                 sys.stdout.write('d')
  162.             elif coordinate in barrierSet:
  163.                 sys.stdout.write('X')
  164.             elif coordinate in lasers:
  165.                 direction = lasers[coordinate]
  166.                 if direction == 'N':
  167.                     sys.stdout.write('^')
  168.                 elif direction == 'E':
  169.                     sys.stdout.write('>')
  170.                 elif direction == 'W':
  171.                     sys.stdout.write('<')
  172.                 elif direction == 'S':
  173.                     sys.stdout.write('v')
  174.                 else:
  175.                     sys.stdout.write('?')
  176.             elif coordinate in routeSet:
  177.                 sys.stdout.write('.')
  178.             else:
  179.                 sys.stdout.write(' ')
  180.         sys.stdout.write('\n')
  181.  
  182.     sys.stdout.write('\n')
  183.  
  184.     if route:
  185.         sys.stdout.write('Route:\n')
  186.         for coordinate in route:
  187.             sys.stdout.write(str(coordinate))
  188.             sys.stdout.write('\n')
  189.     else:
  190.         sys.stdout.write('No Route')
  191.  
  192. def main():
  193.     origin = readCoordinate(sys.stdin.readline().strip())
  194.     destination = readCoordinate(sys.stdin.readline().strip())
  195.     barriers = []
  196.     laserCoordinates = []
  197.     laserDirections = []
  198.  
  199.     barrierLine = sys.stdin.readline().strip()
  200.     if barrierLine:
  201.         barriers = [readCoordinate(barrier) for barrier in barrierLine.split(' ')]
  202.  
  203.     laserLine = sys.stdin.readline().strip()
  204.     if laserLine:
  205.         rawLasers = laserLine.split(' ')
  206.         laserCoordinates = [readCoordinate(laser) for laser in rawLasers]
  207.         laserDirections = [laser.rsplit(',', 1)[1] for laser in rawLasers]
  208.  
  209.     route = RobotRouter(barriers, laserCoordinates, laserDirections).route(origin, destination)
  210.     writeMapAndRoute(origin, destination, barriers, laserCoordinates, laserDirections, route)
  211.  
  212. main()
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
 
Top