TopCoder problem "GeneralChess" used in SRM 197 (Division I Level One , Division II Level Two)



Problem Statement

    You have decided that too many people do not know how to play chess. So, in an effort to teach the rules you must write some software that helps to understand how chess-pieces affect one another. Your current project involves the knight and its ability to threaten one or more pieces at once. The knight has an unusual style of "jumping" around the board. One move consists of traveling two squares in one of the four cardinal directions, followed by one square perpendicular to the original direction. For example, if a knight is on (0,0), it may move to (2,1), (2,-1), (1,2), (1,-2), (-2, 1), (-2,-1), (-1,2), or (-1,-2). In addition, if a piece is on any of those locations, it is threatened by the knight on (0,0).

You will be given a String[] pieces, where each element is a comma delimited set of coordinates.  Every element in pieces is formatted as "<x-coordinate>,<y-coordinate>" (quotes and angle brackets for clarity).  Calculate and return a String[] where each element represents a position from which a knight threatens every piece in pieces.  Your return String[] must be in the same format as pieces and sorted in increasing order by the x-coordinate.  If two sets of coordinates have the same x-coordinate, the one with the smaller y-coordinate must come first.
 

Definition

    
Class:GeneralChess
Method:attackPositions
Parameters:String[]
Returns:String[]
Method signature:String[] attackPositions(String[] pieces)
(be sure your method is public)
    
 

Constraints

-pieces will contain between 1 and 8 elements, inclusive.
-Each element in pieces will be formatted as "<x-coordinate>,<y-coordinate>" (quotes and angle brackets for clarity).
-Each <x-coordinate> will be an integer between -10000 and 10000, inclusive and will not contain leading zeros.
-Each <y-coordinate> will be an integer between -10000 and 10000, inclusive and will not contain leading zeros.
-Each element in pieces will be unique.
 

Examples

0)
    
{"0,0"}
Returns: { "-2,-1",  "-2,1",  "-1,-2",  "-1,2",  "1,-2",  "1,2",  "2,-1",  "2,1" }
This location is threatened from eight different places.
1)
    
{"2,1", "-1,-2"}
Returns: { "0,0",  "1,-1" }
A knight may be in two places such that both pieces are threatened. In chess, placing your pieces in such positions is usually undesirable when your opponent has a knight.
2)
    
{"0,0", "2,1"}
Returns: { }
3)
    
{"-1000,1000", "-999,999", "-999,997"}
Returns: { "-1001,998" }
No three pieces can ever be threatened by a knight from more than one position.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5072&pm=2430

Writer:

ValD

Testers:

lbackstrom , brett1479

Problem categories:

Simple Search, Iteration