Statistics

Problem Statement for "SimplePath"

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

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

  2. "NWWS"

    {10,3,7,10}

    Returns: -1

    This road is a 10 x 10 x 10 U-shaped simple path.

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

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

  5. "NNNNNNNNNNNNNNNNNNNN"

    {1,2,1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,2,1,1}

    Returns: -1

  6. "NNNNNNNNNNNNNNNNNNSN"

    {1,2,1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,2,1,1}

    Returns: 17

  7. "ENWSE"

    {5,2,19,2,19}

    Returns: 0

  8. "EN"

    {5,2}

    Returns: -1

  9. "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW"

    {10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}

    Returns: -1

  10. "ESWNESWNESWNESWNESWNESWNESWNESWNESWNESWNESWNESWN"

    {9950,9950,9951,9951,9952,9952,9953,9953,9954,9954,9955,9955,9956,9956,9957,9957,9958,9958,9959,9959,9960,9960,9961,9961,9962,9962,9963,9963,9964,9964,9965,9965,9966,9966,9967,9967,9968,9968,9969,9969,9970,9970,9971,9971,9972,9972,9973,9973}

    Returns: -1

  11. "ESWNESWNESWNESWNESWNESWNESWNESWNESWNESWNESWNESWN"

    {9950,9950,9951,9951,9952,9952,9953,9953,9954,9954,9955,9955,9956,9956,9957,9957,9958,9958,9959,9959,9960,9960,9961,9961,9962,9962,9963,9963,9964,9964,9965,9965,9966,9966,9967,9967,9968,9968,9969,9969,9970,9970,9971,9970,9972,9972,9973,9973}

    Returns: 39

  12. "ENWNESW"

    {20,20,20,20,5000,30,5000}

    Returns: 1

  13. "ENWNESWS"

    {20,20,20,20,5000,30,5000,10}

    Returns: 0

  14. "ENWNESWS"

    {20,20,20,20,5000,30,5000,5000}

    Returns: 0

  15. "NNWSENW"

    {10,10,10,20,20,20,10}

    Returns: 0

  16. "NNWSENW"

    {10,10,10,21,20,21,10}

    Returns: 1

  17. "NNWSENWE"

    {10,10,10,21,20,21,10,20}

    Returns: 1

  18. "NNWSENW"

    {10,10,10,21,20,21,30}

    Returns: 1

  19. "EEEEEW"

    {1,1,1,1,1,10}

    Returns: 0

  20. "NENENWS"

    { 1, 1, 1, 1, 1, 1, 1 }

    Returns: 2

  21. "NWSE"

    { 100, 100, 100, 100 }

    Returns: 0

  22. "NWES"

    { 2, 2, 1, 2 }

    Returns: 1

  23. "EEEEEW"

    { 1, 1, 1, 1, 1, 10 }

    Returns: 0

  24. "NWSENW"

    { 4, 4, 2, 2, 1, 5 }

    Returns: 2

  25. "NWSEEN"

    { 5, 5, 3, 2, 5, 2 }

    Returns: 0

  26. "EEW"

    { 1, 1, 2 }

    Returns: 0

  27. "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN"

    { 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000 }

    Returns: -1

  28. "SESWNW"

    { 5, 5, 5, 3, 8, 8 }

    Returns: 0

  29. "NS"

    { 1, 1 }

    Returns: 0

  30. "NENENENENENENENENENENENENENENENENENENENENENENENENE"

    { 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000 }

    Returns: -1

  31. "EW"

    { 2, 1 }

    Returns: 0

  32. "EW"

    { 1, 2 }

    Returns: 0

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)2024, TopCoder, Inc. All rights reserved.
This problem was used for: