Advertisement
azraelgnosis

Prepare the Bunnies' Escape

Sep 16th, 2023
917
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.07 KB | Source Code | 0 0
  1. Prepare the Bunnies' Escape
  2. # ===========================
  3. # You're awfully close to destroying the LAMBCHOP doomsday device and freeing Commander Lambda's bunny workers,
  4. # but once they're free of the work duties the bunnies are going to need to escape Lambda's space station
  5. # via the escape pods as quickly as possible.
  6. # Unfortunately, the halls of the space station are a maze of corridors
  7. # and dead ends that will be a deathtrap for the escaping bunnies.
  8. # Fortunately, Commander Lambda has put you in charge of a remodeling project
  9. # that will give you the opportunity to make things a little easier for the bunnies.
  10. # Unfortunately (again), you can't just remove all obstacles between the bunnies and the escape pods -
  11. # at most you can remove one wall per escape pod path,
  12. # both to maintain structural integrity of the station and to avoid arousing Commander Lambda's suspicions.
  13. #
  14. # You have maps of parts of the space station, each starting at a work area exit and ending at the door to an escape pod.
  15. # The map is represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls.
  16. # The door out of the station is at the top left (0,0) and the door into an escape pod is at the bottom right (w-1,h-1).
  17. #
  18. # Write a function solution(map) that generates the length of the shortest path from the station door to the escape pod,
  19. # where you are allowed to remove one wall as part of your remodeling plans.
  20. # The path length is the total number of nodes you pass through, counting both the entrance and exit nodes.
  21. # The starting and ending positions are always passable (0).
  22. # The map will always be solvable, though you may or may not need to remove a wall.
  23. # The height and width of the map can be from 2 to 20.
  24. # Moves can only be made in cardinal directions; no diagonal moves are allowed.
  25.  
  26. from queue import Queue
  27.  
  28.  
  29. def get_neighbors(x: int, y: int, max_x: int, max_y: int) -> list:
  30.     return list(filter(None, [
  31.         [x-1, y] if x > 1 else None,
  32.         [x, y+1] if y < max_y else None,
  33.         [x+1, y] if x < max_x else None,
  34.         [x, y-1] if y > 1 else None
  35.     ]))
  36.  
  37.  
  38. def solution(layout: list[list[int]]) -> int:
  39.     max_x = len(layout[0])
  40.     max_y = len(layout)
  41.  
  42.     frontier = Queue()
  43.     frontier.put([0, 0])
  44.     reached = set()
  45.     reached.add((0, 0))
  46.  
  47.     while not frontier.empty():
  48.         current_x, current_y = frontier.get()
  49.         neighbors = get_neighbors(current_x, current_y, max_x, max_y)
  50.  
  51.         for x, y in neighbors:
  52.             if layout[x][y] == 1:
  53.                 continue
  54.  
  55.             for new_x, new_y in get_neighbors(x, y, max_x, max_y):
  56.                 if (new_x, new_y) not in reached and layout[new_x][new_y] == 0:
  57.                     frontier.put(new_x, new_y)
  58.             reached.add((x, y))
  59.  
  60.     return int()
  61.  
  62.  
  63. assert solution([
  64.     [0, 0, 0, 0, 0, 0],
  65.     [1, 1, 1, 1, 1, 0],
  66.     [0, 0, 0, 0, 0, 0],
  67.     [0, 1, 1, 1, 1, 1],
  68.     [0, 1, 1, 1, 1, 1],
  69.     [0, 0, 0, 0, 0, 0]]) == 11
  70.  
  71. assert solution([
  72.     [0, 1, 1, 0],
  73.     [0, 0, 0, 1],
  74.     [1, 1, 0, 0],
  75.     [1, 1, 1, 0]]) == 7
  76.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement