# Prepare the Bunnies' Escape

Sep 16th, 2023
706
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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()
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)
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.