arrays - Minimum steps to win Snake Ladder -

given snake , ladder game, write function returns minimum number of jumps take top or destination position. can assume die throws results in favor of you

**

here solution, not sure it's correct or not.

this problem similar frog jump in array.but before have model problem in format.

create array of size 100 , each position store 6 if there no snake or ladder. store jump count . if ladder present @ point . if snake present store -ve jump @ location.

now have solve in how many minimum steps can reach till end. main problem can solved using dynamic programing in o(n^2) time complexity , o(n ) space.

have @ this blog post, full mathematical analysis of chutes , ladders, using both monte-carlo simulations , markov chains. show way of calculating minimum number of steps win (basically construct transition matrix , see how many times have multiply starting vector solution has non-zero final position). not efficient way of doing it, post worth read.

here quick solution in python, using sets. got numbers in jump-table blog post. @ every step, calculates positions reachable previous step, , continues until final position among 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 board nsteps = 0  while final_pos not in positions:     nsteps += 1     old_positions = positions     positions = set()     pos in old_positions:         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 negligible , spits out correct answer (see blog) of 7.