javaalgorithmdata-structuresdynamic-programming# Wrong output with dynamic programming on Limited Subway Surfer challenge

## The "Limited Subway Surfer" challenge

## Attempt

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

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 * 10`

^{4}`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.

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?

Solution

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]));
}
```

- Maven (commandline): No compiler is provided in this environment
- Java Swing: display Text selectable
- How to make a query for mongodb using spring to return objects ordered alphabetically'
- cant update array contents java
- In Gradle, how can I generate a POM file with dynamic dependencies resolved to the actual version used?
- Why do we use @Embeddable In Hibernate
- IS there a way to configure ehcache 2 for spring boot 3?
- org.hibernate.mapping.Table.getColumn returns null
- Java Swing bars floating instead of starting from the same baseline
- How to find files that match a wildcard string in Java?
- java.lang.ClassCastException: oracle.sql.CLOB cannot be cast to oracle.sql.CLOB
- Update a Vertex after Retrieving it
- Read nested list with other attributes in Java streams
- Do you not need a password to access a truststore (made with the java keytool)?
- Creating new Instance of @Component each time FXMLLoader calls applicationContext.getBean(class)
- Add ' to particular place in String in Java
- ExecutionCompletionService hangs when used with Project loom
- How do you handle "impossible" exceptions in Java?
- Android navigation drawer, change text/hover color
- Fastest way to determine if an integer's square root is an integer
- Play WAV file backward
- EclipseLink and Derby with Java 19
- SpringBoot + AWS cognito, can't resolve issuerUri
- Is there a way to use a custom, arbitrary SQL query for loading an entity in Jmix?
- Fill an array with matches from a HashMap in Java
- Print retry count with @Retryable
- Actuator endpoints returning 500 error after upgrade to spring boot 3
- Bufferedimage resize
- What is the difference between ExecutorService.submit and ExecutorService.execute in this code in Java?
- Spring Boot - Process finished with exit code 0