CareerCup

This sounds like a shortest distance algorthm to me. Assuming the snake and ladder board can be represented as a map, just use breadth-first search.

1. Get all next hop from starting/current position, store them in a queue
2. Pop the queue, get all next hop from this position, enqueue them
3. Repeat step 2 until we find the finish position. The number of repetition is the number of shortest jump

Create an array for all the numbers on the board 1-100. Go through the array in order, keeping track of all the jumps in a sorted fashion. Once you have this, discard the first array to free up space. Select the biggest jump, and iterate again to get to this biggest jump in best fashion (0-StartPoint1) (EndPoint1-100). Create two arrays in sorted fashion to get the next two biggest jumps. Iterate like this till you get the series of biggest jumps needed to finish.

This problem is similar to frog jump in an array.But before that we will have to model the problem in that format.

Create an array of size 100 and for each position store 6 if there is no snake or ladder. store jump count . if ladder is present at that point . If snake is present then store -ve jump at that location.

Now we have to solve in how many minimum steps we can reach till end.

Main problem can be solved using dynamic programing in O(n^2) time complexity and O(n ) space. tech-queries.blogspot.com/2011/08/find-optimal-number-of-jumps-to-reach.html

1> greedy approach: posion=posion+6 if there is no ladder between [posion, posion+6] and 
2>  posion+6 != snake position, i.e no negative weight. else posion=ladderTop
DP: 2nd approach

1. Consider the game as Directed Graph where every node has a directed edge of cost 1 to it's next 6 nodes . In addition a directed edge of cost 0 from bottom of ladder to top of ladder and directed edge of cost zero from snake's mouth to it's tail.

2. After this initialization apply single source shortest path (Bellman Ford) from 1 for 100.

the cost will be number of dice rolls.

Please comment if i missed some thing.

The snake board can be represented as an augmented linkedList Node
Class Node
{
Next ;
Random ;
}

Base case for back tracking is first if the prev node value is greater than the next node
if reached destination return count.

Class MyClass{

int positon=0;
public int getCurrentPosition{

position+= diceResult();

if(isLadderAvailable(postion)){

getCurrrentPostion();

if(postion==100)
break;
}


public int diceResult()
{
// throw the dice and return the results
}

boolean isLadderAvailable(int postion)
{
// check if the ladder is availale at the position given or not
}
}