TopCoder problem "SimplePath" used in SRM 202 (Division II Level Three)



Problem Statement

    A road has been laid out so that it consists of segments, each of which runs either North-South or East-West. We will say that one segment "touches" another segment if the two segments have a common point, other than the common point between two sequential segments in the path. We want to check the surveyor's data to make sure that it represents a simple path -- specifically one in which no two segments touch.

We are given a String direction and a int[] length giving the surveyor's data for each segment of the road. The i-th character of direction tells the direction ('N','E','S', or 'W') of the i-th segment, and the i-th element of length tells the length of that segment. Create a class SimplePath that contains a method trouble that is given direction and length and returns the zero-based index of the lowest-indexed segment that touches another segment. If no two segments touch, return -1.

 

Definition

    
Class:SimplePath
Method:trouble
Parameters:String, int[]
Returns:int
Method signature:int trouble(String direction, int[] length)
(be sure your method is public)
    
 

Constraints

-direction will contain between 1 and 50 characters inclusive.
-length will contain the same number of elements as direction has characters.
-Each character of direction will be an uppercase letter 'N', 'E', 'S', or 'W'.
-Each element of length will be between 1 and 10,000 inclusive.
 

Examples

0)
    
"NWSEEN"
{5,5,3,2,5,2}
Returns: 0
The first segment goes north 5 units. The second then goes 5 west. The third segment goes 3 south. The fourth goes 2 east. The fifth segment continues east and touches (in fact intersects) the first segment. Return the zero-based index of the first segment.
1)
    
"NWWS"
{10,3,7,10}
Returns: -1
This road is a 10 x 10 x 10 U-shaped simple path.
2)
    
"NWES"
{2,2,1,2}
Returns: 1
Nothing touches the first segment, but the second segment touches the third segment. In fact, the third segment doubles back and covers half of the second segment. The zero-based index of the second segment is 1.
3)
    
"NWSE"
{100,100,100,100}
Returns: 0
This road forms a square, so the last segment touches the first segment and we return the index of the first segment.
4)
    
"EEEEEW"
{1,1,1,1,1,10}
Returns: 0

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5848&pm=2876

Writer:

dgoodman

Testers:

lbackstrom , brett1479

Problem categories:

Geometry, Search