Snakes and Ladders Optimization

Source: Flipkart Interview Question from Interview Street (taken from Chinmay - CSE IITB Blog)




Problem:

Find the smallest number of jumps (i.e. optimal number of dice throws) needed to win a snakes and ladders game. Assume you are given a board with all the necessary inputs like start/end positions of all ladders and snakes.





Solution:

Highlight the part between the * symbols for the answer.
* Model the board as a graph: one node per square, and from square x a directed edge to square transport(x + k) for each die value k = 1..6, where transport sends ladder bottoms to ladder tops and snake heads to snake tails (squares past the final square are ignored or bounce, per the rules). Every edge costs exactly one dice throw, so the answer is the shortest path from the start square to the final square in an UNWEIGHTED directed graph: plain BFS.

Complexity: each node has at most 6 outgoing edges, so BFS is O(V + E) = O(N) for an N-square board.

Note: the graph is NOT a DAG (snakes can create cycles), so topological-order DP does not apply; and Dijkstra works but is overkill since all edge weights are 1. Also mark transported squares correctly: landing on a snake head or ladder bottom is not a real stop - expand only the transported destination.

Solution by Pratyush Rathore from the comments. *

Comments

  1. Pratyush Rathore1:24 PM, December 26, 2012

    DAG, with each number as a node. A number x is linked to x + 1, x + 2, .. x + 6 with edge 1. A number with snake's head is linked only to the snakes tail with edge weight 0. A number with ladder's tail is linked only to the number with ladder's head with weight 0.
    BFS with destination = final point.

    Maximum number of edges from a vertex = 6. At worse, I travel each edge exactly once. So, at definitely it is O(n). Although, I am reasonably sure, the complexity in this case will come out to be much lesser.

    ReplyDelete
  2. dante8:11 PM, December 26, 2012

    this question also came during flipkart hiring process at other IITs , i also thought it was a DAG, but one can easily form a cycle here using a snake ,plus the edge weights were different so went with dijkstra later , (however wasn't able to code dijkstra during the time limit , so had to contend with BFS code which wasnt giving full score :/ )

    ReplyDelete
  3. timequalsmoney9:38 PM, October 20, 2013

    I would say it seems like an application of Djiktra's algorithm with source as 0 and destination as 100. Considering every move as unit cost, we just have to find the shortest path... And everything needed is given as input hence we have a graph with edges and weights.

    ReplyDelete
  4. Pratik Poddar12:29 AM, September 13, 2026

    Right idea, with two refinements: (1) since every edge has unit cost, plain BFS suffices - Dijkstra's priority qu

    ReplyDelete

Post a Comment

Popular posts from this blog

Polya's Urn Problem: Expected Balls in the Smaller Urn

Puzzle: There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the smaller sized urn? Source: P. Winkler's Puzzles book. (Chapter: Probability). Solution: Highlight the part between the * symbols for the answer. * This problem can be reformulated as the following problem. Suppose I have a stack of black cards and one red card. Initially I take red card in my hand. Now I add black cards randomly between any two cards (so, initially its either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent. No...
Read more

Lion and Man in a Circular Cage: Can the Lion Catch the Tamer?

Source: Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University) Problem: A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.) Solution: Highlight the part between the * symbols for the answer. * Answer: surprisingly, no - the tamer can avoid being caught forever. This is the famous Lion and Man problem, posed in the 1930s and settled by Besicovitch; the proof appears in Littlewood's "A Mathematician's Miscellany" (and opens Bollobas's "The Art of Mathematics"). What the lion CAN do (Rado's strategy): move to the center, then always stay on the radius through the tamer, using any spare speed to move outward. Since the lion runs on a smaller circle, it can match the tamer's angular position while steadily increasing its radiu...
Read more

Expected Tosses for Consecutive Heads: 2 Heads vs 3 Heads Puzzle

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more