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.



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


-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.


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.
Returns: -1
This road is a 10 x 10 x 10 U-shaped simple path.
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.
Returns: 0
This road forms a square, so the last segment touches the first segment and we return the index of the first segment.
Returns: 0

Problem url:

Problem stats url:




lbackstrom , brett1479

Problem categories:

Geometry, Search