For those who are not familiar with the snakes and ladders game. Here is a link for introduction
. So the fastest reach in snakes and ladders, is a modified version of the game. So, you are playing the game called snakes and ladders and you have an enchanted dice. You are the master of the dice and you can command it to get any number between 1 and 6 both inclusive. This means that when you throw the dice, the number on the upper face is totally controlled by you. If you ask for a 5, you get a 5 and so on.
Problem Statement - Fastest Reach in Snakes and Ladders
The problem in hand is to find the minimum number of steps you will need to reach the cell labelled 100. The board given to you will have positions of ladders and snakes as follows:
L = 3 - [8, 77], [37, 94], [58, 82]
S = 5 - [99, 12], [87, 57], [72, 30], [90, 43], [53, 2]
The above data suggests that we have 3 blue ladders, the first one starts from cell 8 and takes you to the cell 77. The second one starts from cell 37 and takes you to cell 94 and so on. Similarly, there are 5 red snakes and if you land up on cell 99, the snake will bite you and you will end up on cell 12.
Approaching the problem
The problem is on the similar lines as Single Source Shortest Path
. In this problem we are expecting to find the shortest path given a directed graph. The vertices of the graph are cells and the edges are possible paths from one cell to another. Possible new paths or edges are result of ladders and snakes on the board.
Each vertex will have 6 outgoing edges. For e.g.: If you are at cell 1, you can choose to move to cell 2, 3, 4, 5, 6 or 7 by getting a number between 1-6 from the dice. This means that it takes just one turn to move from 1 to any of the next 6 cells.
The condition becomes interesting when there is a ladder. Consider that you are at cell 4. You can move to 5, 6, 7, 8, 9 or 10 by getting a number between 1 and 6 from the dice. But the moment you land on 8, by the property of the ladder you will reach 77. Hence, to reach 77 from cell 4 you will just need 1 turn.
Storing the Graph
The graph has to be stored in a way such that the operations on it for the given problem can be easily done. In this case, we just need to store the ladders and snakes, because rest all the cells (vertices) and paths (edge) are fixed.
For e.g.: we know that from each cell there are 6 outgoing edges to the next 6 consecutive cells. The only information which varies is the edges created by the snakes and the ladders. Hence, we will store the information in a board. The board is a one dimensional zero indexed array of length 100.
We will initialize the complete array with -1, just to mark that there are no snakes and ladders yet. Then as we get ladders and snakes we update the array. The array stores the destination of each ladder and snake. For e.g. the ladder which starts at 8 and ends at 77 can be stored as the value (77-1) at the index (8-1). So index 7 contains the value 76 (this is due to the zero based indexes).
Algorithm to solve fastest reach in snakes and ladders
Here is a simple algorithm which will work, the motivation for it is the breadth first search
- Start from the first cell, add it in a queue. The distance/ number of turns to reach this cell is zero.
- Remove the first cell from the queue and update the distances of next 6 cells to 1. This is because, you can reach to any of the six cells from the first cell, in one turn.
- Add all these 6 cells in the queue. Mark these cells as visited.
- Remove the cells from the queue one by one and follow the above procedure.
- Every time you visit an un-visited cell, update it distance as 1 + the distance to the current cell.
- When the final cell (100) is removed from the queue, the algorithm is over. The distance of cell 100 is the answer to the problem
In this algorithm, there will be cells where a ladder starts or a snake bites. The destination of the snake/ ladder will have the same distance as the source of the snake/ladder
Maintaining a list/array of vertices already added/removed to/from the queue is a good idea. This will prevent from extra comparisons and duplicate additions. Our algorithm must stop when the vertex 100 is removed from the queue. This is because we already processed the final vertex and no further processing can be done on the same.
Here is the source code for the solution.
Running Time Calculations:
The algorithm runs till the queue has a value. In worst case when there is no snakes or ladders. The algorithm will run for 100 times and each time it will evaluate the next 6 vertices. Hence the running time is O(100*C). If the size of the board is bigger and the dice can have more than 6 faces then the running time of the algorithm would vary as a function of both the attributes.
Hence, we can say that the running time is O(N*d) where N is the size of the board and d is the number of faces in the dice.
Auxiliary Space Calculations:
We are using a int array of 100 to store the board. A boolean array of 100 to maintain the visitor flag and a queue, which will contain a maximum of 100 - 36 = 74 elements in the worst case. This also means that the worst case space complexity is O(N) where N is the size of the board.
Many a times it is wise to create a small data structure which holds critical values, in this case we have created a Node data structure which contains the distance for this node from start. Also, this solution can be further optimized on space, we surely wont need that much of space to maintain visit flag. If we can have a data structure to just store the ones visited instead of all the nodes. But that may cost some running time. This is a classic problem because it resembles to three types of algorithms. Dynamic Programming, Graph Theory and Greedy Approach to some extent. No doubt Fastest Reach in Snakes and Ladders is a wonderful problem and it tests many aspect of your programming skills.