Guest User

Untitled

a guest
Aug 25th, 2019
99
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