Friday, May 8, 2015

Orchard

Problem:

TopCoder Problem Statement - Orchard
Single Round Match 167 Round 1 - Division II, Level Three

Overview:

Determine the position in an NxN array that is furthest from the edges, and from any tree.

Java Source:
     1 public class Orchard {
     2 
     3     int size;
     4     int[][] distances;
     5 
     6     public int[] nextTree(String[] orchard) {
     7 
     8         size = orchard.length;
     9 
    10         distances = new int[size][size];
    11 
    12         /*
    13         * Mark distances from the edges.
    14         * This create concentric squares with the distance
    15         * at the edges = 1, and the value increasing by
    16         * 1 as the squares move inward.
    17         */
    18         for (int i = 0; i < (size + 1) / 2; i++) {
    19             for (int j = i; j < (size - i); j++) {
    20                 distances[i][j] = i + 1;                // Top Row
    21                 distances[size - 1 - i][j] = i + 1;     // Bottom Row
    22                 distances[j][i] = i + 1;                // Left Column
    23                 distances[j][size - 1 - i] = i + 1;     // Right Column
    24             }
    25         }
    26 
    27         /*
    28         * Add trees into the mix
    29         * Updates the values in the distance matrix.
    30         */
    31         for (int row = 0; row < size; row++)  {
    32             for (int col = 0; col < size; col++)  {
    33                 if ('T' == orchard[row].charAt(col))  {
    34                     placeTree(row,col);
    35                 }
    36             }
    37         }
    38 
    39         /*
    40         * Find and return the greatest distance
    41         */
    42         int maxDistance = 0;
    43         int[] retValues = new int[] {1, 1};
    44 
    45         for (int y = 0; y < size; y++)  {
    46             for (int x = 0; x < size; x++)  {
    47                 if (distances[y][x] > maxDistance)  {
    48                     maxDistance = distances[y][x];
    49                     retValues[0] = y + 1;
    50                     retValues[1] = x + 1;
    51                 }
    52             }
    53         }
    54 
    55         return retValues;
    56     }
    57 
    58 
    59     /*
    60     * Places a tree at the given coordinate.  Then works outward from the
    61     * tree's location reducing the distances of it's neighboring squares.
    62     * Here's where all the work of updating the distances matrix is done.
    63     */
    64     private void placeTree(int row, int col)  {
    65 
    66         // Work the area above the tree.
    67         for (int dy = 0; row - dy >= 0; dy++)  {
    68 
    69             // Reduce neighbors above and to the left.
    70             for (int dx = 0; col - dx >= 0; dx++)  {
    71                 distances[row - dy][col - dx] =
    72                       Math.min(distances[row - dy][col - dx], dx + dy);
    73             }
    74 
    75             // Reduce neighbors above and to the right.
    76             for (int dx = 0; col + dx < size; dx++)  {
    77                 distances[row - dy][col + dx] =
    78                       Math.min(distances[row - dy][col +dx], dx + dy);
    79             }
    80         }
    81 
    82         // Works the area below the tree
    83         for (int dy = 0; row + dy < size; dy++)  {
    84 
    85             // Reduce neighbors below and to the left.
    86             for (int dx = 0; col - dx >= 0; dx++)  {
    87                 distances[row + dy][col - dx] =
    88                       Math.min(distances[row + dy][col - dx], dx + dy);
    89             }
    90 
    91             // Reduce neighbors below and to the right.
    92             for (int dx = 0; col + dx < size; dx++)  {
    93                 distances[row + dy][col + dx] =
    94                       Math.min(distances[row + dy][col +dx], dx + dy);
    95             }
    96         }
    97     }
    98 
    99 }

Notes:

There are several way to go about solving this problem. I've seen it solved using breadth-first search from every point in the grid. But, I believe this solution takes a far easier approach.

The idea is to create an NxN array that holds the distances from each point to and edge or a tree, then we can just scan through the distances array looking for the largest value. The loops on lines 18 - 25 initialize the array so that all elements on the outer edge have a value of 1. Then each concentric square moving inward gets increasing values. A 5x5 square, would look like this:

11111
12221
12321
12221
11111

Next, each tree is dropped into the matrix. The placeTree() method handles reducing the distance values in the matrix based on their proximity to the new tree. The method begins at the tree's location and then works by going upward one row at a time, first working to the left and then right. At each new location it determines if that distance should be reduced to the distance back to the tree, or left alone because its value was already smaller. After reaching the top of the matrix, the method starts over from the tree's location and works down to the bottom. Using the above example, a tree placed at location 2,1 would update the matrix to be:

11111
11221
10121
11221
11111

After all the trees have been placed, then it's a simple matter of looping through the distances array, and finding the largest value.

No comments:

Post a Comment