JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 8
Problem: MazeEscape

Problem Statement

    

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):

  1. The size of the maze (N) will be randomly chosen between 5 and 20.
  2. An exit will be chosen from one of the 4*N external walls. All other external walls will be blocked.
  3. Internal walls will be placed at random until placing any more internal walls would result in unreachable cells.
  4. 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.
 

Definition

    
Class:MazeEscape
Method:helpRover
Parameters:
Returns:int
Method signature:int helpRover()
(be sure your method is public)
 

Available Libraries

    
Class:Rover
Method:move
Parameters:String
Returns:String
Sample Call:val = Rover.move(commands);
    
 

Notes

-The maze will be square and between 5 and 20 units on a side.
-All coordinates returned from the static move function will be between -19 and 19 inclusive.
-Every cell of the maze will be reachable, and there will be an exit.
-The walls of the maze fall between cells of the maze.
 

Constraints

-There is a command limit of 50,000 command strings.
-The time limit is 30 seconds.
-The memory limit is 64 MB.
 

Examples

0)
    
A 2x2 maze with a minimum of 7 moves:

+-+-+
|...|
+.+.+
|R|..
+-+-+
This example violates the constraints by having a 2x2 maze to facilitate testing. Here is an possible dialog between your program and the rover:

  • C: "FFL"
  • R: "(0,-1)" (note that the grid is 2x2, and moving 1 unit corresponds to two characters in the picture)
  • C: "FFR"
  • R: "(0,-1)"
  • C: "RFRF"
  • R: "(1,0)"
  • C: "FLFLF"
  • R: "OUT"
In this example, the optimal command string would be "FRFRFLF" which would get the rover out of the maze with 1 call to the move method and 7 actual commands, for an optimal score of 17. The command sequence above used 4 calls to the move method and 13 commands (only 3 of the 5 in the final command string were used to get out), for a score of 2*17/(4*10 + 13) ~= 0.6415.
1)
    
A 5x5 maze with a minimum of 12 moves:

+-+.+-+-+-+
|...|     |
+.+-+-+-+ +
|...  |   |
+-+.+-+ +-+
|R..    | |
+ +-+-+-+ +
|   |     |
+ + + +-+ +
| |   |   |
+-+-+-+-+-+
2)
    
A 18x18 maze with a minimum of 92 moves:

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   |    R  |   |     |   |         |
+ + +-+-+.+-+-+ + +-+-+ +-+-+ +-+-+ +
| | |    .|   |   | | |       |   | |
+-+ +-+-+.+ +-+-+ + + +-+-+ + +-+ + +
|   | |...|  ...          | | | |   |
+-+ + +.+-+-+.+.+-+ + +-+-+-+ + +-+-+
| |   |.| |...|...| |   |       |   |
+ + + +.+ +.+ +-+.+-+-+-+ +-+-+ + + +
| | | |.|...| |  ...  | |   |     | |
+ +-+ +.+.+-+-+-+-+.+-+ +-+-+ + +-+-+
| | | |...| |     |...|       | |   |
+ + + +-+ + + +-+ +-+.+-+ +-+-+ + +-+
| |             | | |.    |   |     |
+ + + +-+-+-+ +-+-+ +.+-+-+ +-+-+-+ +
| | | |       |      .........    | |
+ + +-+-+ + + + +-+ +-+-+ +-+.+-+ +-+
|   | |   | | | |     |   | |.  | | |
+ +-+ +-+-+ +-+-+-+-+ +-+ + +.+ +-+ +
|     |       |     |   | | |.|     |
+-+-+-+ +-+-+ +-+-+ +-+-+-+ +.+-+-+ +
| |   | | |   | |          ...|     |
+ +-+ + + +-+-+ + +-+ +-+-+.+ +-+-+ +
| |   | |         | | |.....|     | |
+ + +-+-+ + +-+-+ + +-+.+ + + + +-+ +
|       | |   |   |.....| | | |   | |
+-+ +-+-+-+-+-+-+-+.+-+ +-+-+-+-+ +-+
| |   |       | |...| | |       |   |
+ +-+ +-+ +-+-+ +.+ + +-+ +-+-+ + +-+
..|...|.......| |.|   | | | |     | |
+.+.+.+.+ +-+.+ +.+-+ + +-+ + + +-+ +
|...|...| | |.....|   |   |   |     |
+ +-+ +-+-+ + +-+ +-+ + + +-+-+ +-+-+
| |   |         |   | | | |   |     |
+ +-+-+ + +-+ +-+-+-+ + + +-+ + +-+ +
| |     | |       |     | |       | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
3)
    
A 18x18 maze with a minimum of 47 moves:

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   | | |     |   | | | |           |
+ + + + + +-+ + +-+ + + + +-+-+ +-+-+
| |   | | | |       |         |     |
+-+ + + +-+ + +-+ + +-+ +-+ +-+-+-+-+
| | | | |     |   |     |     |   | |
+ + +-+ +-+ +-+ +-+ +-+-+ + +-+ +-+ +
....    | | |   |   |     | | |     |
+ +.+ +-+ +-+-+-+-+-+ +-+-+ + + +-+ +
| |.| | |   |   | | |   |     | |   |
+ +.+-+ + + +-+ + + + +-+-+ +-+ +-+-+
| |...|   | |   |   | | |     |   | |
+-+-+.+-+ +-+-+ + +-+-+ +-+ +-+ + + +
|   |...|     | |   | |     |   |   |
+-+ +-+.+ +-+-+ + +-+ +-+ + + +-+-+-+
|      ...| | |     |   | |     |   |
+-+-+-+ +.+ + +-+ +-+ +-+-+-+ + +-+ +
|   |   |.  |   |       |     | |   |
+ + +-+ +.+-+-+ + +-+ + + +-+-+-+ + +
| |     |.......| |   |     |   | | |
+-+-+ + +-+ +-+.+ +-+ +-+ + + +-+ +-+
|   | |   | |  ...|     | |     | | |
+ + +-+ + +-+ +-+.+-+-+-+ +-+ +-+ + +
| | |   |   | |...|     |   |     | |
+ +-+ +-+-+-+-+.+-+-+ +-+-+-+-+ +-+ +
|     |     | |.  |   | | |       | |
+-+-+-+-+ +-+ +.+-+ +-+ + + + + + + +
| |   |     |  ...|       | | | |   |
+ + +-+ +-+ +-+-+.+ + +-+-+-+-+-+-+ +
| |       | |  ...  |           |   |
+ + +-+ + + +-+.+ +-+-+-+-+-+ + +-+ +
| |   | | |   |.| |       |   |   | |
+ +-+-+-+ +-+-+.+-+-+ + +-+-+ + +-+-+
|           | |.  |   | |     |     |
+-+ + +-+-+ + +.+ + + + +-+-+ + +-+ +
|   |     |R....| | | |       | |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
4)
    
A 10x10 maze with a minimum of 21 moves:

+-+-+-+-+-+-+-+-+-+-+
|   |   |     |     |
+-+ +-+ + + + + +-+-+
|       | | | |   | |
+ +-+ +-+ +-+-+ + + +
| | | | |R..| | |   |
+ + + + +-+.+ + + +-+
|   |      .| | |   |
+-+-+-+-+-+.+ + +-+-+
|       | |...  |   |
+ + +-+-+ +-+.+ +-+ +
| |     |    .|   | |
+-+-+ +-+ +-+.+-+-+ +
|           |.|     |
+-+-+-+-+-+ +.+ +-+-+
|           |.....| |
+ + + +-+-+-+-+-+.+ +
| | |   |   |   |...|
+ + + +-+ + + +-+-+.+
| | |     |   |    .|
+-+-+-+-+-+-+-+-+-+.+
5)
    
A 11x11 maze with a minimum of 32 moves:

+-+-+-+-+-+-+-+-+-+-+-+
|           |         |
+ + + +-+-+-+-+ +-+-+ +
| | | | |     |     | |
+-+-+ + +-+ +-+-+ +-+-+
|     |   | |     |....
+ +-+ + + + +-+-+ +.+-+
|   |   | |     |  .  |
+-+-+-+ +-+ +-+-+-+.+-+
|  .........|   | |.  |
+-+.+ +-+-+.+ + + +.+-+
|  R| |  ...| |  ...| |
+-+-+-+-+.+-+-+-+.+ + +
| |   |  .....|  .| | |
+ +-+ + +-+ +.+-+.+-+ +
| |       | |.....    |
+ + + + +-+-+ +-+-+ +-+
|   | |   | |   |     |
+ +-+-+-+ + +-+-+ +-+ +
| |       |         | |
+-+-+ + +-+ +-+ +-+-+ +
|     | |     | |     |
+-+-+-+-+-+-+-+-+-+-+-+
6)
    
A 6x6 maze with a minimum of 24 moves:

+-+-+-+-+-+-+
|R  |     | |
+.+-+ +-+ + +
|.....  | | |
+-+-+.+-+-+ +
|    .| |   |
+-+-+.+ + + +
| | |.|...| |
+ + +.+.+.+-+
|    ...|...|
+-+ + +-+ +.+
|   |   | |..
+-+-+-+-+-+-+
7)
    
A 14x14 maze with a minimum of 21 moves:

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |   | | |               |
+ + + + + + +-+ + +-+ +-+-+ +
| | | |   |     | |   |     |
+ + +-+ +-+-+ +-+-+ +-+-+ +-+
|   |     |     |   |     | |
+ + + +-+ +-+ + +-+ +-+ +-+ +
| |     | |   |   |   |     |
+-+-+-+-+ +-+ + +-+ +-+ +-+-+
| | |     | | | |   |   |   |
+ + + + +-+ +-+-+ +-+-+ + + +
| | | | | |           | | | |
+ + + + + +-+ +-+-+-+ +-+ +-+
|   | | | |   |     |   |   |
+-+ + +-+ + +-+ +-+ + +-+ +-+
|       | |   | |           |
+-+-+-+ + +-+ +-+ + + + +-+-+
| |       |   |   | | | |   |
+ +-+-+-+ + +-+-+-+ +-+-+ + +
| |   | |   |   |.....| | | |
+ + + + +-+-+-+ +.+-+.+ + +-+
|   |          R..|  .|   | |
+-+-+ +-+ +-+ + +-+ +.+-+ + +
|   |   |   | | |   |.|   | |
+-+ + + +-+-+-+-+-+ +.+ +-+ +
|     | |   |   |   |.....  |
+-+ + + + +-+ + + +-+-+-+.+-+
|   | |   |   |     |.....  |
+-+-+-+-+-+-+-+-+-+-+.+-+-+-+
8)
    
A 20x20 maze with a minimum of 33 moves:

+-+-+-+-+-+-+-+-+-+-+.+-+-+-+-+-+-+-+-+-+
| | |     |     | | |.|   |   |   |     |
+ + +-+-+ + +-+-+ + +.+ +-+ +-+ + +-+ +-+
|         | |   |    .  | |     | |   | |
+-+ +-+-+-+ + +-+ +-+.+-+ +-+ +-+ +-+ + +
|     |     |   | | |...| |     | |     |
+-+-+ + + + + +-+-+ + +.+ + + +-+-+ +-+ +
| |   | | |           |.....| |   | |   |
+ + + + +-+-+-+ + + +-+-+-+.+-+-+ + +-+-+
|   |   | |     | |   |  ...|     | |   |
+-+-+-+-+ +-+-+ +-+ +-+-+.+-+-+ +-+ +-+ +
|   | | | | |   | | | |...  |       | | |
+ +-+ + + + +-+ + +-+ +.+-+-+ + +-+-+ + +
|   |   |         |    ...|   |         |
+ + + + + +-+-+ +-+-+-+-+.+-+ +-+-+-+-+ +
| |   |   | |   |     | |...| |         |
+-+ +-+ + + + +-+-+ +-+ +-+.+-+-+ +-+-+-+
|   | | | |         | |   |.|     |     |
+-+ + + +-+-+ +-+-+ + + +-+.+-+ +-+-+-+ +
|     |   |       |   |   |...|       | |
+-+ +-+-+-+ +-+ +-+-+ +-+ + +.+ +-+-+ + +
|     |   | |       | | |   |R  |     | |
+-+ +-+-+ +-+-+-+ + + + + + + + +-+-+-+ +
|   | |       |   | |   | | | |   | |   |
+-+-+ +-+ +-+-+-+ +-+ + +-+ +-+ +-+ +-+ +
|       |   |       | |   | | | |   |   |
+ +-+ +-+ +-+ +-+-+-+ + +-+ + + + + + + +
| |   |   |     | |   | |   | | | |   | |
+-+-+ + +-+-+-+ + +-+-+-+-+ + + + + + +-+
|         |   |   | |     | |     | | | |
+ + +-+-+-+ + + + + +-+ +-+-+ +-+-+ +-+ +
| |     |   |   |   |   |     |         |
+ +-+ +-+ + +-+-+-+ +-+ +-+-+ +-+ +-+-+-+
|   |     |     | | |   |     | | | |   |
+ +-+-+-+-+ +-+ + +-+-+ +-+ +-+ + + + +-+
|   | |     | | |   |     | |           |
+-+ + + + + + + + +-+-+ +-+ + +-+-+-+ + +
| |   | | | |   |       |   | |       | |
+ + +-+-+ + +-+ +-+-+-+ + +-+-+-+ + + + +
|     |   |   | |               | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
9)
    
A 5x5 maze with a minimum of 2 moves:

+-+-+-+-+-+
.R    |   |
+-+ +-+ + +
|       | |
+ +-+ +-+ +
|   | |   |
+ +-+-+-+-+
| |     | |
+ + + + + +
|   | |   |
+-+-+-+-+-+

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.