Monday, June 30, 2014

HillHike

Problem:

TopCoder Problem Statement - HillHike

Overview:

Determine the number of possible paths over a hill. At each step, you may go up, down, or stay level. You must reach the maximum height and a number of landmarks in between.

Java Source:
    1  : /*
    2  : TopCoder
    3  : Single Round Match: 145
    4  : Division: 1
    5  : Level: 3
    6  : Points: 1000
    7  : Description: http://community.topcoder.com/stat?c=problem_statement&pm=1158
    8  :  */
    9  :
    10 : public class HillHike {
    11 :
    12 :     private int maxDistance;
    13 :
    14 :     private int maxHeight;
    15 :
    16 :     private int[] landmarks;
    17 :
    18 :     private PathCache pathCache;
    19 :
    20 :     public long numPaths(int distance, int maxHeight, int[] landmarks) {
    21 :
    22 :         this.maxDistance = distance;
    23 :         this.maxHeight = maxHeight;
    24 :         this.landmarks = landmarks;
    25 :
    26 :         // Initialize a new PathCache to store values once they've been seen.
    27 :         pathCache = new PathCache(distance, maxHeight, landmarks.length);
    28 :
    29 :         /*
    30 :         The first move must be to distance=1, height=1 so we might as well
    31 :         start from there.
    32 :          */
    33 :         return getPaths(0, 0, 0, false);
    34 :     }
    35 :
    36 :     /*
    37 :     Calculates the number of paths starting from a point at distance,height.
    38 :     The number of paths also depends on how many landMarks haave been seen
    39 :     and whether or not the maximum height has been reached yet.
    40 :      */
    41 :     private long getPaths(int distance, int height, int landMarksSeen,
    42 :                           boolean maxHeightReached) {
    43 :
    44 :         // Check for going beyond height or distance
    45 :         if (distance > maxDistance) { return 0; }
    46 :         if ((height > maxHeight) || (height < 0)) { return 0; }
    47 :
    48 :         // Can't climb faster or descend faster than 1:1
    49 :         if (height > distance) { return 0; }
    50 :
    51 :         // Won't be able to get down in time
    52 :         if (height > (maxDistance - distance)) { return 0; }
    53 :
    54 :         // Can only have a height of 0 at the start and finish
    55 :         if ((height == 0) && (distance != 0) && (distance != maxDistance)) {
    56 :             return 0;
    57 :         }
    58 :
    59 :         /*
    60 :         If we've seen these values before, we'll use that instead of
    61 :         recalculating.
    62 :          */
    63 :         long numPaths = pathCache.getPath(distance, height, landMarksSeen,
    64 :                 maxHeightReached);
    65 :
    66 :         if (numPaths >= 0) { return numPaths; }
    67 :
    68 :         /*
    69 :         If we've reached maxDistance, and we've:
    70 :             Seen the maximum height
    71 :             Seen all of the landmarks
    72 :             and are now back down to height == 0
    73 :         Then we have a valid path, return 1
    74 :         Otherwise return 0
    75 :          */
    76 :         if (distance == maxDistance) {
    77 :             return (maxHeightReached && (height == 0) &&
    78 :                     (landMarksSeen == landmarks.length)) ? 1 : 0;
    79 :         }
    80 :
    81 :         // True if we've seen maxHeight in the past, or are at it now.
    82 :         boolean seenMaxHeight = maxHeightReached || (height == maxHeight);
    83 :
    84 :         int newLandMarksSeen = landMarksSeen;
    85 :
    86 :         /*
    87 :         If we haven't seen all the landmarks yet, and the current height
    88 :         equals the height of the next landMark, then increment the number
    89 :         of landMarks seen.
    90 :          */
    91 :         if (landMarksSeen < landmarks.length) {
    92 :             if (landmarks[landMarksSeen] == height) {
    93 :                 newLandMarksSeen++;
    94 :             }
    95 :         }
    96 :
    97 :         // Check how many paths if we go up from here.
    98 :         numPaths = getPaths(distance + 1, height + 1, newLandMarksSeen,
    99 :                 seenMaxHeight);
    100:
    101:         // Add how many paths if we stay level from here.
    102:         numPaths += getPaths(distance + 1, height, newLandMarksSeen,
    103:                 seenMaxHeight);
    104:
    105:         // Add how many paths if we descend from here.
    106:         numPaths += getPaths(distance + 1, height - 1, newLandMarksSeen,
    107:                 seenMaxHeight);
    108:
    109:         // Store this value so we don't have to recalculate it.
    110:         pathCache.storePath(distance, height, landMarksSeen,
    111:                 seenMaxHeight, numPaths);
    112:
    113:         return numPaths;
    114:     }
    115:
    116:     /*
    117:       Stores the paths that have already been calculated,
    118:       so that we don't have to calculate them again.
    119:     */
    120:     class PathCache {
    121:
    122:         /*
    123:         The number of paths from a given point to the finish is determined by
    124:          the distance to the point, it's height, how many landMarks have been
    125:           seen up to that point, and if the highest elevations has been
    126:           reached yet.  This multi-dimensions array stores the number of
    127:           paths given each of these combinations.
    128:          */
    129:         private final long[][][][] pathsFound;
    130:
    131:         PathCache(int maxDistance, int maxHeight, int numLandMarks) {
    132:
    133:             pathsFound = new long[maxDistance + 1][maxHeight + 1]
    134:                     [numLandMarks + 1][2];
    135:
    136:             // Initialize all values in pathsFound to -1
    137:             for (int i = 0; i <= maxDistance; i++) {
    138:                 for (int j = 0; j <= maxHeight; j++) {
    139:                     for (int k = 0; k <= numLandMarks; k++) {
    140:                         for (int m = 0; m < 2; m++) {
    141:                             pathsFound[i][j][k][m] = -1;
    142:                         }
    143:                     }
    144:                 }
    145:             }
    146:         }
    147:
    148:         /*
    149:         Stores the number of paths for the given parameters.
    150:          */
    151:         void storePath(int distance, int height, int landMarksSeen,
    152:                        boolean maxHeightReached, long numPaths) {
    153:
    154:             pathsFound[distance][height][landMarksSeen]
    155:                     [maxHeightReached ? 1 : 0] = numPaths;
    156:         }
    157:
    158:         /*
    159:        Returns the number of paths given the input conditions, or
    160:        -1 if they haven't been calculated yet.
    161:         */
    162:         long getPath(int distance, int height, int landMarksSeen,
    163:                      boolean maxHeightReached) {
    164:
    165:             return pathsFound[distance][height][landMarksSeen]
    166:                     [maxHeightReached ? 1 : 0];
    167:         }
    168:     }
    169: }
Notes:

There are two important concepts on display here. The first is determining the number of paths to the finish given a set of parameters. The second is storing those values so that they do not need to be recalculated over and over. You can get by on small input sets without storing the calculated values, but you will fail at least one of the tests due to the 2 second time limit.

The general approach goes like this: The number of paths to the finish equals the number of successful paths if the next point is a climb, plus the number of paths if the next point is the same height, plus the number of paths if the next point is a descent. We'll recursively call getPaths() on each of these three points and add them together. At each point, if our current height equals the maximum height, then we'll set maxHeightReached to true. Also, if our current height equals the height of the next landmark, then we'll check that off and begin looking for the next landmark. When we reach the finish (distance == maxDistance), then we'll check to see if all the conditions have been met.

First, look at the getPaths() method beginning on line 41. Lines 45-57 perform some rudimentary checks to see if it's even possible to reach the finish given the input. If we're already past the maximum distance, gone over the maximum height, too high given the forward distance, cannot possibly get back down to a height of zero in the remaining distance, of if our height is zero and we're not at either the start or finish; then the are no possible paths - return 0.

Once we've passed all of these checks, lines 63-66 determine if we've already calculated the number of paths given these inputs. If we have, then just return that number and we skip the trouble of recalculating. It's important that we check the out of bounds conditions in the previous paragraph first, as this will prevent ArrayIndexOutOfBoundsExceptions. This can happen if for example, we check for a height above the maximum height.

On line 66, we'll get back a -1 if the path from here has not you been calculated.

Lines 76-80 check to see if we've reach the end and have met all the conditions. We've reached the maximum height at least once. We've passed through all the landmarks, and we've reached distance == maxDistance at height == 0. If all these are true, then return 1 - otherwise, return 0. If we haven't reached maxDistance yet, then we'll continue on and calculate the number of paths from here.

On Line 82, we set seenMaxHeight to be true if we've been at maxHeight previously, or are at it now.

Lines 91-95 check the height of the next expected landMark. If we're at the height of that next land mark, then we increment newLandMarksSeen. That way we'll begin looking for the next land mark height - or if newLandMarksSeen equals the number of land marks, then we know we've seen all of them.

Lines 98-110 recursively call getPaths() using the next distance, and points that are higher then, equal to, and lower than the current point. The sum of all these paths becomes the number of paths from the current point to the finish. We'll store that value at line 110 so that it does not need to be calculated again.

With this setup, we can call getPaths() from the first point 0,0 and it will calculate all possible paths from the start to the finish that meet the constraints of the problem.

The inner class PathCache at line 120 stores the number of paths given the inputs. This technique is know as memoization and it comes in very handy in this case. By storing values that we've seen before, we can eliminate the need to calculate the same subtrees over and over again.

On line 129, a 4 dimensional array is created. This allows any possible combination of distance, height, number of land marks seen, and max height seen to be mapped to a long - which is the number of paths from that point. Initially these are all set to -1, so a value of 0 or more denotes a number that has already been calculated.

The distance and height dimensions are 1 unit larger than the need to be, bu t this prevents having to do some -1 calculations in other places. The size of the numLandMarks dimension must be one larger than the number of landmarks to protect against the case where the number of landmarks is zero. We always want at least one unit here. The final dimension maps to the boolean maxHeightReached. Here true gets location 1 and false is location 0.

If you're unconvinced about the need to store the previously calculated paths, please try this: Run test 4 from the topcoder arena with the code as is. For me, it took about 7ms to complete. Now comment out lines 66 and replace it with "return -1". This essentially forces every path to be calculated as if it weren't cached. My time is now... we'll it's been running for more than 10 minutes, so I'll let you know when it completes.

No comments:

Post a Comment