© Parineeth M R

** 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