CareerCup

This question seems wrong, or at least in one corner case...
I think the second part of the question (the maximum from 51-100) might yield a value of infinity.
Suppose 51 is an empty cell and 52 is a snake that leads to 51.
If I land on 51 and the dice always shows 1 then I'll loop there forever...

For 1 to 50
Using DP

1. Initialize dp[0] to dp[6] = 1 {Since these can be reached in 1 dice roll} and all dp[7] to dp[50] = INT_MAX (high number)

2. Ladders will have 2 endpoints : Starting Cell and Ending Cell of which obviously ending cell will be greater.
Sort all the ladders in ascending of their starting cell.

3. For i = 1 to 6
4.Check if there is a ladder with starting cell i. Say ending cell of such a ladder is e. If so make dp[e] = 1;

5. For i = 7 to 50
6. max = INT_MAX (some very high value)
7. For j = i to j = i-6
8. if max < dp[j]+1 then max = dp[j]+1;
9. if dp[i] > max dp[i] = max;
10. Check if there is a ladder with starting cell i. Say ending cell of such a ladder is e. If so make dp[e] = dp[i]+1;
11. dp[50] is the minimum number of dice rolls required to reach 50.

If there are ladders on top of another ladder, example: ladder1 from cell 9 to cell 12 and ladder2 from cell 12 to 25.
In this case repeat Step 4 and Step 10 till there are no more ladders.

Step 10:
10a. flag = 0, s = i;
10b. while flag == 0
10c. Check if there is a ladder with starting cell s. Say ending cell of such a ladder is e. If so make dp[e] = dp[s];
and set s = e;
10d. If there is no such ladder then flag = 1;

I thought about a recursive solution with complexity Nx(num of ladders).

Better solutions welcome:

int min_rolls(node * start)
{
int arr[6] = {INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX}
int i = 0;
int j = 0;
for(int i = 1; i <= 6; i++)
{
// if its 50 then return 1;
if(*start+i == 50)
return 1;

// for each ladder climbup & recursive call min_roll
if(is_ladder(start+i) && ladder_top(start+i) < 50)
arr[i-1] = min_rolls(ladder_top(start+i));

else if(is_not_snake(start+i))
// keeping track of last non_ladder non_snake index
j = i;

}
// if all 6 indexes are not snakes & ladders then
// recursively call min_rolls with last non_ladder non_snake index.
if(j != 0)
{
arr[j-1] = min_rolls(start + j);
}
return ( MIN(arr[0-5]) +1 );
}

From 1 to 50
Let the coin be at the initial position and the number of steps moved is zero
>>the next six step or cell(2,3,4,5,6,7) can be reached with minimum 1 dice roll
>>mark the cell with 1
>>if any of these six cell has lower point of ladder then mark upper point of ladder with 1
>>continue the above steps with MAXIMUM upper point of the ladder and mark the further cell with current weight(here it is 1) with 1

For 51 to 100
>> instead of ladder use snake!!

let S[x] = number of steps to add at position x, for ladder S[x] is positive for snake its negative else its 0.

Let M[x] = min number of rolls to get to pos x
so M[x] = min(min (i=1to6) (M[x-i] + 1), M[x])

int minDiceRoll(int n, int* S)
{
	int M[x];
	for (x = 0 to n)
		M[x] = -1
	M[0] = 0;
	for(x=1;x<n;x++)
	{
		min = M[x]
		for(i=1;i<=6;i++)
		{
			if (x-i>0)
			{
				if (min == -1 || min > M[x-i] + 1)
					min = M[x-i] + 1;
			}
		}
		M[x] = min;
		if (S[x] != 0 && S[x] > 0)
		{
			M[x+S[x]] = M[x];
		}
	}
	return M[n-1];
}

For minimum dice roll use the algorithm above. For max path, if there exist even a single snake in the path, we can have infinite number of dice rolls, as one will always roll the dice to go the snake position.

every cell is a node. Path is an edge.
for 0 < i < 50 and i < j <= 50
w[i,j] = 1 ; if j-i <= 6
w[i,j] = 1 ; if there's a ladder from i to j
w[i,j] = -1 ; if there's a snake from i to j
w[i,j] = infy ; otherwise
run floyd warshall to find the minimum path from 1 to 50.

for 50 < i < 100 and i < j <= 100
invert the weights and find the minimum path from 51 to 100.
I think this should work.

For 1 - 50 , give each ladder +1 weight and snake +1 and now apply Dijkstra Single Source Shortest path algorithm.

For 51-100, give each ladder a weight of (end point - starting point) and each snake a weight of -1, now apply Bellman Ford or Floyd Warshall algo, longest path can be infinite.

Only Microsoft can ask getMaxMoves. Crap!

For 1 to 50:
Consider the board as directed graph.
1. k is linked to k + 1 k + 2, k + 3, k + 4, k + 5, k +6 because from k you can reach these nodes in one throw of dice.
2. If any of these neighbors of k has a ladder which takes you to j, then j becomes the neighbor instead of the base of the ladder. Lets say k + 3 node takes you to j node, then instead of k + 3, j is the neighbor of k.
3. Similarly if any of the neighbors of k has a snake which takes you to l, then l is a neighbor of k.
4. The value of each edge ranges from 1 to 6. For ex., k->k+1 has 1 weight, k->k+2 has 2 weight, and so on...... upto k->k+6 having 6 weight.
Using these conditions, build the graph. Now this is transformed into a Shortest path between two nodes in a directed graph problem.

For 51 to 100
I agree with what anonymous said in the first post.

1-50: use BFS

51-100: infinity unless any constraints are placed

On a side note I think single linked list with random pointers (ladder, snake) might be a good DS to represent snake and ladder board.