TopCoder problem "NENE" used in TCCC '03 Int'l Regional (Division I Level Three)



Problem Statement

    A fortress has been built to protect the queen. It consists of a collection of walls built in circular arcs around the queen's throne. Each arc is described by the directions from the throne to its two ends. Directions are specified using N,E,W,S to indicate the four compass points. NE, NW, SE, SW indicate the directions half way between. Every other direction is specified by preceding one of these four 2-letter directions with a sequence of letters, each of which matches one of the direction's final 2 letters. For example, ENE is the direction halfway between NE and E. NENE is the direction halfway between ENE and the next more northern direction which can be expressed in 3 or fewer letters (NE). SWWWSSW is halfway between WWWSSW and the next more southerly direction that can be expressed in 6 or fewer letters (WSSW).

No more than 10 letters are ever used to name a direction. That means that there are exactly 2048 directions. This diagram shows all of the directions in the Northeast quadrant that can be expressed in 4 or fewer letters. 

               N
               |  NNNE
               |      NNE
               |        ENNE
               |          NE
               |           NENE
               |             ENE
               |              EENE
    -----------+-----------------E
               |
               |
               |
               |
               |

Create a class NENE that contains the method vulnerable that takes the ends of the circular arcs as inputs, and returns the first direction counterclockwise from East which is not protected. Return the String "SAFE" if all legal directions are protected. A wall does protect the directions at its endpoints.

The ends are input as String[] cw and String[] ccw. Corresponding elements of cw and ccw give the directions of the clockwise and counterclockwise ends of a wall. The wall extends less than 360 degrees, going counterclockwise from its cw end to its ccw end.

 

Definition

    
Class:NENE
Method:vulnerable
Parameters:String[], String[]
Returns:String
Method signature:String vulnerable(String[] cw, String[] ccw)
(be sure your method is public)
    
 

Notes

-E is the last direction to check and return. See Example 4)
-the returned direction must be a legal one, so it must have no more than 10 characters
-every legal direction other than the compass points must end in either NE, SW, SE, or NW so, for example, EN or NEN would not be legal directions
-a wall protects its own endpoints.
 

Constraints

-cw has between 1 and 50 elements
-ccw has the same number of elements as cw
-each element of cw and ccw contains between 1 and 10 characters inclusive
-each element of cw and ccw is a legal direction
-no element of cw is equal to the corresponding element of ccw
 

Examples

0)
    
{"E"}
{"W"}
Returns: "WWWWWWWWSW"
The one wall has an end to the east, and extends from there counterclockwise until its other end is to the west. The answer is the first legal direction counterclockwise from W.
1)
    
{"E","E","SE"}
{"W","N","S"}
Returns: "SSSSSSSSSE"
The first wall is the same as in the preceding example. The second wall protects nothing new. The third wall covers everything except the section from S to SE. The answer is the first direction counterclockwise from S.
2)
    
{"E","WWWWWWWWSW"}
{"W","NE"}
Returns: "SAFE"
Even though there is a small gap, all the legal directions are covered.
3)
    
{"EEEENE","WNW","SSWWSW"}
{"NNNNENEENE","WWNW","EEENE"}
Returns: "NEENE"
4)
    
{"EEEEEEEENE","W"}	
{"WWWWWWWWNW","EEEEEEEESE"}
Returns: "E"
5)
    
{"W"}
{"S"}
Returns: "EEEEEEEENE"

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4466&pm=1138

Writer:

dgoodman

Testers:

lbackstrom , brett1479

Problem categories:

Geometry