The Shifty Maze
code-challenge maze grid python3
You are a wild mouse and you have stumbled on a maze that some human has constructed to observe your behavior. The maze is littered with blobs of peanut butter and has a cache of sunflower seeds near its center. After discovering the seeds, you decide that you want to take them all home to your personal cache. You must find your way to the seeds and exit the maze. Since there are so many seeds, it takes you many trips to get them all.
Things go well your first time. You find your way to the seeds, bring a few back, and return to the maze. To your surprise, when you return the second time, the maze looks nothing like it did before, but you quickly figure out that the entrance was simply in a different place and continue navigating as usual. The next time you return to the maze, you are once again lost, but you find a familiar pattern of peanut butter dabs and find your way to the sunflower seeds once again. Naturally, you catch onto this pattern and eventually retrieve all the sunflower seeds.
Your task is to make a "mouse" bot that navigates through a maze where the entrance moves to somewhere else on the edge of the maze every time you exit and enter it. You have no limits on memory, but no absolute sense of direction and a limited visual field. You can only exit the maze after finding the cache. Your goal is to get all of the seeds in as few steps as possible.
A perfect maze is randomly generated using a randomized version of Prim's Algorithm starting from a cell near the center. The seed cache will be close to the center. 10% of the cells will be dabbed with 3-5 units of peanut butter. There will not be any peanut butter on the same cell as the seed cache. The maze used for scoring will be 30x30 cells.
Each turn, you can move forward or turn 90 degrees in either direction. If there is any peanut butter on your current cell, you may also eat one unit of it instead of moving or turning. (Partially eaten peanut butter can be used to create landmarks for navigation.)
You can see every cell in a straight line in front of you until a wall obstructs your view. You can also see one cell to your left and right, provided there is no wall between that cell and your current cell.
For each cell that you can see, you can see whether there is a wall on each of the four edges of the cell, how much peanut butter is on that cell, and whether it is the seed cache or the exit.
Suppose you had this maze:
| | 5 | | |
| ----+-- +---+ | --+
|4 | |@ 3 |
| --+-+ --+---- | --+
| | | 4 <| |
| --+ | --+ | | +-+ |
| | | | | |
| | +-- --+-+ +-- +-+
| | | 3 | | |
@ is the seed cache. Numbers are blobs of peanut butter.
< is the mouse (facing west)
The vision for the mouse would look something like this:
+-+ + +
+ +-+ +
No memory limit
You can remember as little or as much as you would like. The challenge is in figuring out where you are as quickly as possible and reduce the amount of time you spend wandering.
The test driver can be found here.
Your solution should be compatible with Python 3.7. You should implement a class with the following methods:
- A constructor taking no arguments
get_action, which is called with one argument representing your vision on each step of navigation (more on that below). This should return a string representing the action to take:
eat are valid values. If this returns an action that cannot be taken, an exception will be thrown and your solution will be considered invalid.
enter_maze, which is called without arguments each time the maze is entered. No return value is expected and the function doesn't actually have to do anything. The next time
get_action is called, you are guaranteed to be on the cell on the edge of the maze facing away from the entrance/exit.
The Vision Object
You will receive an object with the following attributes:
right: the cells to your left and right. If there is a wall that obstructs your view, this will be
'???' instead of the cell view object.
forward: a list of all the cells in your forward vision, starting with your current cell and continuing until the last cell in your vision.
Any of these cell views may also be
None, indicating the entrance/exit of the maze.
Each visible cell inside the maze will be an object with the following attributes:
back: booleans indicating whether there is a wall in the given directions, oriented the same way as the mouse.
contents: an integer representing the amount of peanut butter (if any), None (if nothing is on the cell), or 'cache' if the cell contains the seed cache.
Scoring and Rules
- Standard loopholes apply.
- If your bot only works on the scoring maze, it is an invalid solution. Your bot does not receive enough input to distinguish the scoring maze from another maze, so hard-coding a route will produce an invalid solution.
- Run the test driver to score your result. It uses an isolated and seeded random number generator to ensure that all entries get the same maze and sequence of entrances. The total number of turns it took to retrieve all of the seeds (this takes 100 iterations through the maze) is your score.
- Include your score, your code, and an explanation in your solution post.
- You must output a valid move each turn. Moving into a wall or attempting to eat nonexistent peanut butter will result in an error that you have no opportunity to recover from.
- You may not exit the maze until you have visited the cell containing the seed cache since the last time you entered the maze.