Problem Statement |
| | A shape in 3D Cartesian space is valid if it is made up of identical unit cubes, each cube in the shape has all its edges parallel to coordinate axes and its vertices are at non-negative integer coordinates. Two shapes are considered the same if one can be transformed into the other by some rotation and translation. You are given a description of a valid shape and should return the lexicographically smallest description of a valid shape that is the same as the one supplied.
You are given a String[] shape. Each element of shape describes a single unit cube from the shape and will contain three space-separated non-negative integers. The first of these gives the x-coordinate of the cube, the second gives the y-coordinate, and the third the z-coordinate. The cube is positioned such that the line segment between (x, y, z) and (x+1, y+1, z+1) is a diagonal of the cube and its edges are all parallel to the coordinate axes. Return a String[] containing the lexicographically smallest description of a valid shape in the same format as the input that can be transformed to the supplied shape by rotation and translation. Each element of your return must contain 3 single-space-separated non-negative integers without leading zeros and with no leading or trailing spaces. Each element of your return must describe a distinct cube from the shape. |
| |
Definition |
| | | Class: | Shape3D | | Method: | findCanonical | | Parameters: | String[] | | Returns: | String[] | | Method signature: | String[] findCanonical(String[] shape) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The lexicographically earlier of two String[]s is the one that has the lexicographically earlier String in the first position at which they differ. |
| - | The lexicographically earlier of two Strings is the one that either has the earlier character (using ASCII ordering) at the first position at which they differ or is a proper prefix of the other. |
| - | In ASCII ordering, a space character (' ') comes before any digit. |
| - | The return will contain only digits ('0' - '9') and spaces (' '). |
| - | Since the cubes of any valid shape must be aligned with the coordinate axes, any valid rotation can be achieved by a sequence of 90 degree rotations around the coordinate axes. |
| |
Constraints |
| - | shape will contain between 1 and 50 elements, inclusive. |
| - | Each element of shape will contain 3 space-separated integers without leading zeros between 0 and 1000, inclusive. |
| - | Each element of shape will contain no leading or trailing spaces. |
| - | The elements of shape will be distinct. |
| - | The cubes described in shape will form a connected volume in 3D Cartesian space, where 2 cubes are considered to be connected if they share a face. |
| |
Examples |
| 0) | |
| | {"0 0 0","1 0 0","1 1 0","1 1 1","1 0 1","0 1 1","0 0 1","0 1 0"} |
| Returns: {"0 0 0", "0 0 1", "0 1 0", "0 1 1", "1 0 0", "1 0 1", "1 1 0", "1 1 1" } | | This shape is a cube of side length 2, with a corner at the origin. No rotation or translation is required here, simply rearrange the order of the cubes to give the lexicographically minimum description. |
|
|
| 1) | |
| | {"100 50 50","100 49 50","100 49 49"} |
| Returns: {"0 0 0", "0 0 1", "0 1 0" } | | This shape needs to be rotated and translated so one of the squares lies at the origin. |
|
|
| 2) | |
| | {"11 11 11","10 11 11","12 11 11"
,"11 11 10","11 11 12","11 10 11"
,"11 12 11","9 11 11","13 11 11"} |
| Returns:
{"0 1 1",
"1 1 1",
"2 0 1",
"2 1 0",
"2 1 1",
"2 1 2",
"2 2 1",
"3 1 1",
"4 1 1" } | |
|
| 3) | |
| | {"100 900 800","101 900 800","102 900 800","102 899 800"
,"102 898 800","102 897 800","102 896 800","102 896 801"
,"102 896 802","102 896 803","102 896 804","102 896 805"
,"102 896 806","102 896 807","102 896 808"} |
| Returns:
{"0 0 0",
"0 0 1",
"0 0 2",
"0 0 3",
"0 0 4",
"0 0 5",
"0 0 6",
"0 0 7",
"0 0 8",
"0 1 8",
"0 2 8",
"0 3 8",
"0 4 8",
"1 4 8",
"2 4 8" } | |
|
| 4) | |
| | {"2 2 0","2 2 1","2 2 3","2 2 4","2 0 2","2 1 2","2 3 2","2 4 2","0 2 2","1 2 2","3 2 2","4 2 2","2 2 2"}` |
| Returns:
{"0 10 10",
"1 10 10",
"2 10 10",
"2 10 11",
"2 10 12",
"2 10 8",
"2 10 9",
"2 11 10",
"2 12 10",
"2 8 10",
"2 9 10",
"3 10 10",
"4 10 10" } | | Be careful! Lexicographic ordering is not the same as numerical ordering. |
|
|