Escape!
Description:
You're stuck in a maze and have to escape. However, the maze is blocked by various doors and you'll need the correct key to get through a door.
Basic instructions
You are given a grid as the input and you have to return the positions to go through to escape.
To escape, you have to collect every key and then reach the exit (the exit can only be unlocked if you have every key).
There are also doors in the way, and you can only get through a door if you have the corresponding key.
More detail
The grid is given as a tuple of string representing rows of a grid. The start position is given by '@'
and the end position is given by '$'
. Walls are given by '#'
Doors are represented by an upper case letter eg. 'A'
. And the corresponding key is represented by the lower case letter. For example. the key 'b'
unlocks the door 'B'
. To collect a key, you just have to travel over the position where it is located (it is automatically picked up).
You can move in 4 directions: up, down, left or right. You cannot move diagonally. You also cannot move out of the grid or through walls.
To escape, you have to return the shortest path to travel through to reach the end.
You have to return a list of all the positions you travel through (including the start and end) in the cartesian form (x, y)
, with x
being the horizontal position, and y
being vertical position. (0, 0)
will be the top left position. The shortest path is defined by the least amount of moves you have to make. If there is no solution, you should return None
.
You will have to deal with up to 8 keys per grid. There will always be as many keys as doors, and you have to collect all the keys to be able to escape through the exit. You can only travel through doors if you have the correct key. However, you can travel over the exit even if you don't have all the keys (imagine that the exit is a trapdoor).
You do not need collect the keys in alphabetical order.
For example:
grid2 in the sample tests is:
(
'.a..',
'##@#',
'$A.#'
)
You should return:
[(2, 1), (2, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2)]
as you have to go upwards to get key `a` before being able to go though door `A` to get to the exit.
grid3 in the sample tests is:
(
'aB..',
'##@#',
'$Ab#'
)
You should return:
[(2, 1), (2, 2), (2, 1), (2, 0), (1, 0), (0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2)]
If no keys are given, then you just have to reach the exit. If there are multiple shortest solutions, you can return any of them.
There are 101 tests in total: 8 sample tests and 93 random tests. The largest random tests will have maximum side lengths of 50 x 50
Remember:
- You can only go out the exit if you have collected all the keys.
- You can travel over the exit without all the keys, but you cannot travel over doors without the correct key
- You have to return the shortest path
- The doors may not be in alphabetical order (you may have a
B
door without there being anA
door)
Good luck! :)
Similar Kata:
Stats:
Created | Nov 7, 2019 |
Published | Nov 8, 2019 |
Warriors Trained | 888 |
Total Skips | 254 |
Total Code Submissions | 892 |
Total Times Completed | 87 |
Python Completions | 87 |
Total Stars | 68 |
% of votes with a positive feedback rating | 98% of 25 |
Total "Very Satisfied" Votes | 24 |
Total "Somewhat Satisfied" Votes | 1 |
Total "Not Satisfied" Votes | 0 |
Total Rank Assessments | 6 |
Average Assessed Rank | 3 kyu |
Highest Assessed Rank | 2 kyu |
Lowest Assessed Rank | 4 kyu |