Snake and ladders game – The Coding Interview Blog

Question 57. Find the least number of dice throws needed to complete the snake and ladders game

To find the least number of dice throws, we use the following dynamic programming technique:

1. Initialize the least number of throws needed to reach the positions 1-6 on the board as 1 since we can reach these positions with a single dice throw of a 6-sided dice

2. For any remaining position, we can either reach it from
• any of the previous 6 positions with one dice throw. If there is a snake at a previous position, then we ignore that cell while calculating the least number of throws for the current position

• or we can reach it by a ladder if present from some previous position. If there is a ladder from position I to position P, and we need N throws to reach I, then we can reach P also in N throws.

So we use the formula below to calculate the least number of throws for positions greater than 6

3. The least number of throws to reach the final position of the board gives the least number of throws needed to complete the game

C/C++


/*is_snake: if there is a snake at position 20, then is_snake[20] is set to 1
ladder: if there is a ladder from position 30 to 44, then ladder[44] = 30.
	if there is no ladder at location 90 then ladder[90] = -1
predecessor: this array has the previous board position from where we came to 
	current position with least number of dice throws. If predecessor[100]   
	= 95, then we reached 100 from 95. It is computed and returned. 
Return value: least number of throws to reach the final position on the board
*/
int find_least_throws(int is_snake[], int ladder[], int predecessor[]) 
{
	/*for a particular position pos on the board, least_throws[pos] will store
	the least number of dice throws required to reach the position*/
	int least_throws[MAX_POSITIONS_ON_BOARD + 1];
	int min_throws, i;
	int pos, prev_pos, ladder_start_pos;

	/*Positions from 1 to 6 can be reached from a single dice throw*/
	for (pos = 1; pos <= 6; pos++) {
		least_throws[pos] = 1;
		predecessor[pos] = 0;
	}

	for (pos = 7; pos <= MAX_POSITIONS_ON_BOARD; ++pos) {
		min_throws = MAX_POSITIONS_ON_BOARD;

		/*Find how many dice throws are needed to reach pos from any of 
		the 6 previous cells*/
		for (i = 1; i <= 6; ++i) {
			prev_pos = pos - i;

			if (is_snake[prev_pos])
				continue;

			/*Pick the minimum throws needed from the 6 previous cells*/
			if (least_throws[prev_pos] + 1 < min_throws) {
				min_throws = least_throws[prev_pos] + 1;
				predecessor[pos] = prev_pos;
			}
		}

		/*Suppose we are at pos = 14 and ladder[14] = 4, then there is a ladder
		from 4 to 14. So number of dice throws needed to reach 14 = number of 
		dice throws needed to reach position 4*/
		ladder_start_pos = ladder[pos];
		if (ladder_start_pos != -1) {
			if (least_throws[ladder_start_pos] < min_throws) {
				min_throws = least_throws[ladder_start_pos];
				predecessor[pos] = ladder_start_pos;
			}
		}

		least_throws[pos] = min_throws;
	}
	return least_throws[MAX_POSITIONS_ON_BOARD];
}

Java


/*isSnake: if there is a snake at position 20, isSnake[20] is true
ladder: if there is a ladder from position 30 to 44, then ladder[44] = 30.
	if there is no ladder at location 90 then ladder[90] = -1
predecessor: this array has the previous board position from where we came to 
	current position with least number of dice throws. If predecessor[100]   
	= 95, then we reached 100 from 95. It is computed and returned. 
Return value: least number of throws to reach the final position on the board
*/
public static int findLeastThrows(boolean[] isSnake, int[] ladder, 
					int[] predecessor) {
	/*for a particular position pos on board, leastThrows[pos] will store
	the least number of dice throws required to reach the position*/
	int[] leastThrows = new int [MAX_POSITIONS_ON_BOARD + 1];

	/*All positions from 1 to 6 can be reached from a single dice throw*/
	int pos;
	for (pos = 1; pos <= 6; pos++) {
		leastThrows[pos] = 1;
		predecessor[pos] = 0;
	}

	for (pos = 7; pos <= MAX_POSITIONS_ON_BOARD; ++pos) {
		int minThrows = MAX_POSITIONS_ON_BOARD;

		/*Find how many dice throws are needed to reach pos from any of
		the 6 previous cells*/
		for (int i = 1; i <= 6; ++i) {
			int prevPos = pos - i;

			if (isSnake[prevPos])
				continue;

			/*Pick minimum throws needed from the 6 previous cells*/
			if (leastThrows[prevPos] + 1 < minThrows) {
				minThrows = leastThrows[prevPos] + 1;
				predecessor[pos] = prevPos;
			}
		}

		/*Suppose we are at pos = 14 and ladder[14] = 4, then there is 
		a ladder from 4 to 14. So number of dice throws needed to reach 
		14 = number of dice throws needed to reach position 4*/
		int ladderStartPos = ladder[pos];
		if (ladderStartPos != -1) {
			if (leastThrows[ladderStartPos] < minThrows) {
				minThrows = leastThrows[ladderStartPos];
				predecessor[pos] = ladderStartPos;
			}
		}

		leastThrows[pos] = minThrows;
	}
	return leastThrows[MAX_POSITIONS_ON_BOARD];
}

Python


#is_snake: if there is a snake at position 20, is_snake[20] is set to True
#ladder:  if there is a ladder from position 30 to 44, then ladder[44] = 30.
#	if there is no ladder at location 90 then ladder[90] = -1
#Return value:  1. least number of throws to reach the position on the board
#		2. predecessor list
def find_least_throws(is_snake, ladder) :

	#for a particular position pos on the board, least_throws[pos] will store
	#the least number of dice throws required to reach the position
	least_throws = [0] * (MAX_POSITIONS_ON_BOARD + 1)

	#predecessor list has the previous board position from where we came to 
	#current position with least number of dice throws. If predecessor[100]   
	# = 95, then we reached 100 from 95.
	predecessor = [0] * (MAX_POSITIONS_ON_BOARD + 1) 

	#All positions from 1 to 6 can be reached from a single dice throw
	for  pos in range(1, 7):
		least_throws[pos] = 1
		predecessor[pos] = 0
	
	for  pos in range(7, MAX_POSITIONS_ON_BOARD+1):
		min_throws = MAX_POSITIONS_ON_BOARD

		#Find how many dice throws are needed to reach pos from any of 
		#the 6 previous cells
		for  i in range(1, 7):
			prev_pos = pos - i

			if (is_snake[prev_pos]):
				continue

			#Pick the minimum throws needed from the 6 previous cells
			if (least_throws[prev_pos] + 1 < min_throws) :
				min_throws = least_throws[prev_pos] + 1
				predecessor[pos] = prev_pos
			

		#Suppose we are at pos = 14 and ladder[14] = 4, then there is a ladder
		#from 4 to 14. So number of dice throws needed to reach 14 = number of 
		#dice throws needed to reach position 4
		ladder_start_pos = ladder[pos]
		if (ladder_start_pos != -1) :
			if (least_throws[ladder_start_pos] < min_throws) :
				min_throws = least_throws[ladder_start_pos]
				predecessor[pos] = ladder_start_pos
			
		least_throws[pos] = min_throws

	return least_throws[MAX_POSITIONS_ON_BOARD], predecessor