TopcoderArchiveVisit Topcoder
Archive
Algorithm problem

RobotController

Problem statement, definition, constraints, and public examples.

Problem Statement

PROBLEM STATEMENT

Create a control program which moves a robot about a grid and returns the
robot's final position as an int. A grid consists of a 5 by 5 matrix of cells
numbered from 0 to 24 in the following arrangement:

 0  1  2  3  4                   North
 5  6  7  8  9                     ^
10 11 12 13 14             West <--|-->  East
15 16 17 18 19                     v
20 21 22 23 24                   South

The robot has both a position and a heading. Its position is the cell number it
occupies. Its heading is one of four directions, north, east, south, or west. A
robot starts in cell 0 and has an initial heading of east, that is, towards
cell 1. The robot can be programmed to move about the grid. A program consists
of a string from 1 to 32 characters in length. Each character of the string is
a single program instruction. The valid instructions are the seven characters
'F' 'B' 'L' 'R' ':' 'J' 'X' (the letters must be uppercase). TopCoder will
ensure that the program is valid.

Write a method that takes a control program as input, executes the instructions
in the program, and returns the final cell position of the robot. The
instructions are executed as follows:

'F' moves the robot one cell in the direction of the heading. The heading is
unchanged.
'B' moves the robot one cell in the opposite direction of the heading. The
heading is unchanged.
'L' changes the heading by rotating 90 degrees to the left (counterclockwise).
The cell position is unchanged. For example, if the heading is east, 'L' causes
the heading to be set to north.
'R' changes the heading by rotating 90 degrees to the right (clockwise). The
cell position is unchanged. For example, if the heading is east, 'R' causes the
heading to be set to south.
':' marks the target of a jump instruction. Otherwise treated as a no operation
(NOP) instruction.
'J' skips ahead over instructions until a ':' instruction is encountered.
Execution of the program continues at the ':' instruction. Execution of a
subsequent 'X' instruction will return to the instruction following the 'J'. If
there is no ':' instruction following the 'J' instruction, the program halts
and the current position of the robot is returned.
'X' returns to the instruction immediately following the most recently executed
'J' instruction. Once used as the target of a return, the 'J' instruction is
forgotten as a return point. If no return point is available, the program halts
instead, and the current position of the robot is returned.

DEFINITION
Class Name: RobotController
Method Name: execute
Parameters: String
Returns: int
Method signature (be sure your method is public): int execute(String program);  

NOTES
'J' is, in effect, a subroutine call, and 'X' is the return. Calls to
subrountines can be nested and returns behave in a last-in, first-out (LIFO)
manner.
If the program runs out of instructions to execute it halts, even if 'J's
without corresponding 'X's have been executed. 
Every permutation of instructions in a program represents a valid program that
will halt and return the robot's position. Should the robot be instructed to
move in a direction that would take it off of the grid, the robot simply stays
where it is. For example, if the robot is on cell 4 heading east and is
instructed to move forward, it simply stays on cell 4.

Example:
"FJRJX:FFX"  Initial robot position is 0, it's heading is east.

0 'F' the robot moves to cell 1
1 'J' program control skips ahead to the first : it encounters
5 ':' do nothing
6 'F' the robot moves to cell 2
7 'F' the robot moves to cell 3
8 'X' program returns to the instruction following the J
2 'R' turn to the right. Heading is now south.
3 'J' program control skips ahead to the first : it encounters
5 ':' do nothing
6 'F' the robot moves to cell 8
7 'F' the robot moves to cell 13
8 'X' program returns to the instruction following the J
4 'X' there is no previously executed 'J' instruction awaiting a return and so
the program halts

The program returns the robot's current cell position, 13.

"FJBBR:FF"  Executes 'F','J',':','F','F' then stops since there are no more
instructions, even though there is a 'J' instruction awaiting a return. The
result is 3.

"FJBBR:JX:FFX" Executes
'F','J',':','J',':','F','F','X','X','B','B','R',':','J','F','F','X','X'.
Returns 11.

"::FFFFFFRF"     returns 9.
"JJX:LBBX"       returns 12.
"RJJ:FFLX"       returns 2.
"RFFJJ:LFFLJFRF" returns 12.

Definition

Class:
RobotController
Method:
execute
Parameters:
String
Returns:
int
Method signature:
int execute(String param0)
(be sure your method is public)

Constraints

    Examples

      No public sample cases were explicitly marked for this problem in the original data.

      Back to all problems