TopCoder problem "PrettyPrintASpiral" used in TCO09 Qual 3 (Division I Level Two)



Problem Statement

    

Consider an infinite square grid. Each square in the grid can be represented by a pair of integer coordinates that specify its row and column.

We will fill the entire grid with a spiral of positive integers. We will start by writing the number 1 into the square in row 0, column 0. Then we will write the number 2 into the square in row 0, column 1. From there, the spiral will continue in a counter-clockwise direction. The next few numbers are placed as shown in the scheme below: 

                columns
         -3 -2 -1  0  1  2  3
         --------------------
    -3 | 37 36 35 34 33 32 31
    -2 | 38 17 16 15 14 13 30
    -1 | 39 18  5  4  3 12 29
rows 0 | 40 19  6  1  2 11 28
     1 | 41 20  7  8  9 10 27
     2 | 42 21 22 23 24 25 26
     3 | 43 44 45 46 .. .. ..

Your task will be to return a String[] containing a pretty-printed version of a rectangular part of the filled grid.

More precisely, you will be given four ints row1, col1, row2, and col2. Here, row1,col1 will be the coordinates of the top left cell, and row2,col2 the coordinates of the bottom right cell to be displayed.

The returned String[] must be formatted according to the following rules:

  • The String[] contains one element for each row of the displayed rectangle. The elements are ordered by the row coordinate they describe.
  • Each element is a concatenation of space-separated tokens, each describing a cell in the corresponding row. The tokens are ordered by the column coordinates of cells they describe.
  • All tokens in the entire output have the same length.
  • The length of a token is minimal, i.e., equal to the number of digits in the largest number displayed.
  • Tokens that contain numbers with fewer digits are padded from the left using spaces.
 

Definition

    
Class:PrettyPrintASpiral
Method:getWindow
Parameters:int, int, int, int
Returns:String[]
Method signature:String[] getWindow(int row1, int col1, int row2, int col2)
(be sure your method is public)
    
 

Notes

-The constraints guarantee that the returned String[] will have at most 50 elements, and the length of each element will be at most 50.
 

Constraints

-row1 will be between -5,000 and 5,000, inclusive.
-col1 will be between -5,000 and 5,000, inclusive.
-row2 will be between -5,000 and 5,000, inclusive.
-col2 will be between -5,000 and 5,000, inclusive.
-row2-row1 will be between 0 and 49, inclusive.
-col2-col1 will be between 0 and 4, inclusive.
 

Examples

0)
    
0
0
0
0
Returns: {"1" }
The spiral starts at coordinates (0,0).
1)
    
-1
-2
-1
1
Returns: {"18  5  4  3" }
Note that the single-digit values are now padded with spaces.
2)
    
-2
2
0
3
Returns: {"13 30", "12 29", "11 28" }
3)
    
-3
-3
2
0
Returns: 
{"37 36 35 34",
"38 17 16 15",
"39 18  5  4",
"40 19  6  1",
"41 20  7  8",
"42 21 22 23" }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13758&pm=8693

Writer:

misof

Testers:

PabloGilberto , vorthys , ivan_metelsky

Problem categories:

Brute Force, Simple Math