TopCoder problem "SequenceOfCommands" used in SRM 473 (Division I Level One , Division II Level Two)



Problem Statement

    

You are standing on some arbitrary point in the infinite plane.

You are given a String[] commands that contains the commands you have to execute. Each character of each element of commands is one command. The commands must be executed in the given order: first you execute all commands in the first element of commands one by one, then those in the second element, etc.

There are only three types of commands: 'S' means "step forward", 'L' means "turn 90 degrees to the left", and 'R' means "turn 90 degrees to the right". All your steps have the same length.

You will be executing the commands forever: after you execute the last character of the last element of commands, you will always start from the beginning again.

We say that your path is bounded if there is some positive real number R such that while executing the infinite sequence of steps you will never leave the circle with radius R steps and center at your starting location.

Given the String[] commands, your method should determine whether your path will be bounded or not. Return the String "bounded" (quotes for clarity) if the path is bounded and "unbounded" if it is not.

 

Definition

    
Class:SequenceOfCommands
Method:whatHappens
Parameters:String[]
Returns:String
Method signature:String whatHappens(String[] commands)
(be sure your method is public)
    
 

Constraints

-commands will contain between 1 and 50 elements, inclusive.
-Each element in commands will contain between 1 and 50 characters, inclusive.
-Each character in each element of commands will be one of 'S', 'L', and 'R'.
 

Examples

0)
    
{"L"}
Returns: "bounded"
You are standing on the same spot forever, and in each step you take a turn 90 degrees to the left. This path is clearly bounded.
1)
    
{"SRSL"}
Returns: "unbounded"

Imagine that you start executing the commands facing to the north. While following this sequence you will repeatedly execute the following steps: make a step to the north, rotate right, make a step to the east, and rotate left (to face north again).

Given enough time, this path will take you arbitrarily far away from the spot where you started, hence it is unbounded.

2)
    
{"SSSS","R"}
Returns: "bounded"
While executing this sequence of commands, you will be walking along the boundary of a small square.
3)
    
{"SRSL","LLSSSSSSL","SSSSSS","L"}
Returns: "unbounded"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10979

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14155&pm=10979

Writer:

misof

Testers:

PabloGilberto , bmerry , ivan_metelsky

Problem categories:

Brute Force, Simple Math, Simulation