Wrong output with dynamic programming on Limited Subway Surfer challenge

Question

I tried solving this code challenge using Dynamic Programming, but I do not get expected result.

The "Limited Subway Surfer" challenge

Nidhi has created an alternate version of Subway Surfer game. Her new version is not on a train track unlimited length, rather limited to a track of length N + 1. Just like the original game, this alternate version also has three lanes.

The track has points on it ranging from 0 to N.

In the three lanes, at some points, certain manholes are present. Now, to avoid these manholes, our player needs to jump sideways and switch lanes, as he cannot go from i to (i + 1)^th point on the same lane if there is no manhole on the lane at point i + 1.

You are given an array manholes of length N + 1 where manholes[i] tells us on which lane is the manhole present for point i. For example, if manholes[2] = 1, this means that on point 2 of the train track, a manhole is present on lane 1.

Find the minimum number of lane changes our player has to perform in order to reach from point 0 to point N on the train track.

Note:

If manholes[i] = 0, this means that for point i, there is no manhole present on any lane.

manholes[0] and manholes[N] are always 0.

Input Format:

First line of input contains integer T, representing the number of test cases.

First line of each test case contains the integer N.

Second line of each test case contains N + 1 space separated integers, representing manholes[i].

Our player always begins from the middle lane.

Constraints:

• manholes.length == n + 1
• 1 <= t <= 100
• 1 <= N <= 5 * 104
• 0 <= manholes[i] <= 3
• manholes[0] == manholes[n] == 0

Output Format:

Minimum number of lane changes to reach from point 0 to N.

Sample Input:

4
0 1 2 3 0

Sample Output:

2

Explanation:

The optimal path followed by our player is shown in the image below:

It is clear that to reach from point 0 till point N optimally, our player will have to change lanes twice at minimum.

Attempt

My code for the above challenge is:

    public int minLaneChanges(int[] manholes) {
        int N = manholes.length - 1;
        int[][] dp = new int[N + 1][3];

        // Set initial values
        dp[0][0] = dp[0][2] = 0;

        // Iterate over the points
        for (int i = 1; i <= N; i++) {
            // Iterate over the lanes
            for (int j = 0; j < 3; j++) {
                if (manholes[i] == 0 || manholes[i] == j + 1) {
                    // Manhole on a different lane, find minimum lane change
                    dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + 1);
                } else {
                    dp[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        return Math.min(dp[N][0], Math.min(dp[N][1], dp[N][2]));
        
    }

My approach is to start in the first row, then I iterate each row and column from second row. If I see a hurdle/Manhole I set the current position value to Max value, else I set the current value to min(previous position on same lane, min(previous of other lanes)+1).

Finally I return min among the last row.

My approach fails. For the example input above, it outputs -2147483648. What is the mistake?

Answer 1

Here are some of the issues:

• There is this important specification for the challenge:

  Our player always begins from the middle lane.

  This already means that your initialisation of dp is wrong. The cost to get in the left lane is 1 (one side step). So the initialisation should be:

  dp[0][0] = dp[0][2] = 1;
  dp[0][1] = 0;
  

• manholes[i] == j + 1 checks the opposite from what you write in comments just below it. This condition is true when lane j has a manhole, so in that case you should execute the else block.

• In the if block you add 1 to the second argument of the outer Math.min call. Combined with the fact that you store Integer.MAX_VALUE in some dp entries, you risk adding 1 to that value, which evaluates to Integer.MIN_VALUE and obviously distorts your results. This is why you got -2147483648 as output in one of your tests. I'd suggest not using Integer.MAX_VALUE, but just N. That is a large enough value.

• Your code assumes that a lane switch is possible (in the previous row) even when dp[i-1][j] has a manhole.

Not a problem, but you can reduce the dp array to just one dimension (with three entries). You can incrementally update the same triplet to align it to the current point.

Here is the suggested updated code:

    public int minLaneChanges(int[] manholes) {
        int N = manholes.length - 1;
        int[] dp = new int[]{1, 0, 1}; // Initialise that player is in middle

        // Iterate over the points
        for (int i = 1; i <= N; i++) {
            // If there is a manhole, invalidate paths that arrive there:
            if (manholes[i] > 0) dp[manholes[i] - 1] = N;
            // Get the best lane at this point 
            int best = Math.min(dp[0], Math.min(dp[1], dp[2]));
            // Check if non-best lanes (without hole) can be improved
            //    by jumping sideways from the best lane
            for (int j = 0; j < 3; j++) {
                if (j + 1 != manholes[i]) dp[j] = Math.min(dp[j], best + 1);
            }
        }
        return Math.min(dp[0], Math.min(dp[1], dp[2]));
    }