TopCoder problem "TreeDrawing" used in TCCC '04 Semifinals 1 (Division I Level Three)



Problem Statement

    

Trees are common in computer science and in the business world: search trees, inheritance diagrams, organization charts, etc. Anytime we work with trees, we inevitably end up wanting to draw pictures of them. In this problem, you will write a method that draws textual pictures of trees. For example, here is a sample picture of the kind that you will draw:

         ALICE         
           |           
    BOB-------CONROY   
     |          |      
DENISE-EDITH FRANCINE  
                |      
          GILBERT-HARRY 
Notice that every node has a label that is a sequence of one or more uppercase letters ('A'-'Z'). Sibling nodes are connected by dashes ('-'), and each parent node is connected to its children by a single vertical bar ('|'). Nodes are limited to at most two children. For example, in the above picture, "BOB" has two children but "CONROY" has only one child (all quotes for clarity only).

The layout of a picture is controlled by the following rules:

  1. A child node is always drawn two rows below its parent.
  2. Within a row, nodes are drawn from left to right in the same order that they appear in the input. (See below for the format of the input.)
  3. Sibling nodes are separated by one or more dashes ('-'). Adjacent non-sibling nodes in the same row are separated by one or more spaces (' ').
  4. The vertical bar ('|') connecting a parent to its children is drawn directly below the middle character of the parent's label and directly above the character midway between the first character of the first child's label and the last character of the last child's label. When the middle of the parent's label and/or the children's labels falls between characters, the vertical bar is aligned with the character immediately to the left of the true center.
  5. Sibling nodes are drawn as close together as possible without violating Rules 1-4. Placing siblings lower in the tree close together takes precedence over siblings higher in the tree (see Example 1).

A tree will be specified by a String in the following format:

     <tree>     = <label> "[" <treelist> "]"
     <treelist> = "" | <tree> | <tree> <tree>
     <label>    = one or more uppercase letters
Note that spaces in the grammar are for clarity only, and do not appear in the input. In words, a tree is written as the label of its root followed by its subtrees in square brackets. For example, a one-node tree with the label "FRED" would be written "FRED[]" while a three-node tree with labels "ROOT", "LEFTCHILD", and "RIGHTCHILD" would be written "ROOT[LEFTCHILD[]RIGHTCHILD[]]". The tree drawn above would be written
  "ALICE[BOB[DENISE[]EDITH[]]CONROY[FRANCINE[GILBERT[]HARRY[]]]]"
In practice, the written form of a tree may be too long to fit comfortably in a single String. The actual input will be a String[] tree. However, you should think of all the elements of tree as being concatenated together. For example, the written form of the tree drawn above might be input as the String[]
  { "ALICE[BOB[DENISE[]EDITH[]]CONR",
    "OY[FRANCINE[GILBERT[]HARRY[]]]]" }
Given the String[] tree, you are to generate and return a rectangular String[] containing the picture of the tree. Pad each row on the front and/or back with spaces as needed to make the return value rectangular, but be careful to maintain the alignment of your picture. Your picture should not contain any rows or columns that are entirely spaces.
 

Definition

    
Class:TreeDrawing
Method:draw
Parameters:String[]
Returns:String[]
Method signature:String[] draw(String[] tree)
(be sure your method is public)
    
 

Constraints

-tree contains between 1 and 3 elements, inclusive.
-Each element of tree contains between 1 and 50 characters, inclusive.
-Each element of tree contains only uppercase letters ('A'-'Z') and square brackets ('[' and ']').
-The concatenation of the elements of tree contains at least 3 characters.
-The concatenation of the elements of tree satisfies the grammar shown above.
 

Examples

0)
    
{ "ALICE[BOB[DENISE[]EDITH[]]CONR",
  "OY[FRANCINE[GILBERT[]HARRY[]]]]" }
Returns: 
{ "         ALICE         ",
 "           |           ",
 "    BOB-------CONROY   ",
 "     |          |      ",
 "DENISE-EDITH FRANCINE  ",
 "                |      ",
 "          GILBERT-HARRY" }
The example above.
1)
    
{ "A[B[C[DDDDDDDDDDDDDDD[]]E[]]F[G[H[]]I[]]]" }
Returns: 
{ "            A      ",
 "            |      ",
 "        B--------F ",
 "        |        | ",
 "       C-E      G-I",
 "       |        |  ",
 "DDDDDDDDDDDDDDD H  " }
Notice that by moving C and E farther apart, we could draw B and F closer together, as in
                A      
                |      
             B------F   <<< B and F are now separated by 6 dashes instead of 8
             |      | 
          C-----E  G-I  <<< C and E are now separated by 5 dashes instead of 1
          |        |  
   DDDDDDDDDDDDDDD H  
However, priority is given to the lower siblings, so we keep C and E close together.
2)
    
{ "A[BBBBB[]C[D[FFFFFFFFF[]]E[]]]" }
Returns: 
{ "   A      ",
 "   |      ",
 "BBBBB-C   ",
 "      |   ",
 "     D-E  ",
 "     |    ",
 " FFFFFFFFF" }
Notice that by drawing D and E farther apart, we could make the overall picture narrower, as in
      A     
      |     
   BBBBB-C  
         |  
       D---E   <<< D and E are now separated by 3 dashes instead of 1
       |    
   FFFFFFFFF   <<< the overall picture is now 9 characters wide instead of 10
However, making the overall picture narrower is not our goal, so we keep D and E close together.
3)
    
{ "TOPCODERCOLLEGIATECHALLENGE[SEMIFINALROOMONE[",
  "TOMEK[ERYX[]ADRIANKUEGEL[MICKLE[]]]BSTANES",
  "CU[LARS[RALPHFURMANIAK[]]RUBERIK[]]]]" }
Returns: 
{ "    TOPCODERCOLLEGIATECHALLENGE ",
 "                 |              ",
 "          SEMIFINALROOMONE      ",
 "                 |              ",
 "      TOMEK----------BSTANESCU  ",
 "        |                |      ",
 "ERYX-ADRIANKUEGEL   LARS-RUBERIK",
 "          |          |          ",
 "        MICKLE RALPHFURMANIAK   " }
4)
    
{"A[B[]C[ABCDEFGHIJK[]]]"}
Returns: 
{ "    A      ",
 "    |      ",
 "   B-C     ",
 "     |     ",
 "ABCDEFGHIJK" }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5076&pm=1875

Writer:

vorthys

Testers:

zoidal , lbackstrom , schveiguy

Problem categories:

String Manipulation