Minimum steps to win Snake Ladder

algorithm, arrays

Solution

Have a look at this blog post, it does a full mathematical analysis of Chutes and Ladders, using both Monte-Carlo simulations and Markov chains. He does show a way of calculating the minimum number of steps to win (basically construct a transition matrix and see how many times you have to multiply the starting vector to get to a solution that has a non-zero final position). This is probably not the most efficient way of doing it, but the post is well worth the read.

Here is a quick solution in python, using sets. I got the numbers in the jump-table from the blog post. At every step, it simply calculates all the positions reachable from the previous step, and continues to do so until the final position is among the reachable positions:

jumps = {1: 38, 4: 14, 9: 31, 21: 42, 28: 84, 36: 44, 51: 67, 71: 91, 80: 100,
  98: 78, 95: 75, 93: 73, 87: 24, 64: 60, 62: 19, 56: 53, 49: 11, 48: 26, 16: 6}
final_pos = 100
positions = {0} #initial position off the board
nsteps = 0

while final_pos not in positions:
    nsteps += 1
    old_positions = positions
    positions = set()
    for pos in old_positions:
        for dice in range(1, 7):
            new_pos = pos + dice
            positions.add(jumps.get(new_pos, new_pos))

print 'Reached finish in %i steps' % nsteps

Execution time is negligible and it spits out the correct answer (see blog) of 7.

Problem

Given a snake and ladder game, write a function that returns the minimum number of jumps to take top or destination position. You can assume the die you throws results in always favor of you ** Here is my solution, but not sure it's correct or not. 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.

Original source