| | NASA has landed a rover on Saturn's moon Titan, but unfortunately, it seems to have landed in a maze. Due to budget cuts, the rover is not very capable, and it needs help finding its way out of the maze.
The size of the maze is unknown, as is the rover's location within it. In addition, the rover only has enough memory for 16 commands, and it can't transmit or receive data while keeping the commands in memory. Fortunately, it can execute the commands (F for Forward, R for rotate right, L for rotate left) fairly quickly, so that the limiting time factor is the time it takes commands and status updates to travel from Earth to Titan and back. There is the additional problem that the walls of the maze appear to be too high for the rover to collect any solar power, and each move uses some of its energy reserve.
Your job is to help the rover escape from this maze. You need to preserve energy, but you also must get it out as quickly as possible, so your score will be equal to N*mintm/(10*t + m) where N is the size of the maze (which you don't know), t is the number of sets of commands you send it before it escapes the maze, m is the total number of commands it executes before escaping, and mintm is the minimum possible (10*t + m) for the particular maze. If you send more than 50,000 sets of commands, or you use more than 30 seconds of CPU time, your score will be 0.
The rover starts at position (0,0) facing in the negative y direction (negative y is up, while positive x is to its right). You can send the robot a set of commands using the move function, which takes a set of commands, executes them, and then returns the rover's position.
The string commands consists of up to 16 'F', 'R', or 'L' characters (any other character will result in the rover clearing the remainder of the buffer, and any characters over the limit of 16 will be silently discarded). If the rover is facing a wall and the next character is a 'F', it still uses energy trying to go forward, but fails to move.
The result of this static method is the rover's position after executing the commands in the form "(x,y)".
When the rover escapes the maze, it will return "OUT" instead of a set of coordinates. Once the rover is out of the maze, any remaining commands in the command string are ignored and do not count against the energy usage. Sending more commands to the rover once it is out of the maze, however, will result in a score of 0.
Test cases are generated as follows (all randomly chosen numbers are chosen uniformly and all ranges are inclusive):
- The size of the maze (N) will be randomly chosen between 5 and 20.
- An exit will be chosen from one of the 4*N external walls. All other external walls will be blocked.
- Internal walls will be placed at random until placing any more internal walls would result in unreachable cells.
- The starting location of the rover is chosen at random.
To help you get started, a simple sample solution is provided in each language. This solution implements a simple wall following strategy which ensures it will always leave the maze. Download in
C++,
Java,
C#,
Visual Basic, or
Python.
|