Table of Contents

• Introduction

• Explanation

  • Solution Steps

    • Step 1
    • Step 2
    • Step 3
    • Final Code

• Complexity explanation

• Conclusion

Introduction

When I was young, I remember playing the game on the back of a delicious pack of cabin biscuits with my siblings. It involved rolling a die on a board, and moving your game piece the distance equivalent to your die roll. You also had to follow the instructions laid out on each cell till you hopefully reached the finish line. We called this game Snake and Ladder and little did I know that I’d find myself needing to play this game but using algorithms.

So without further ado, let’s solve LeetCode 909: Snake and Ladders.

We won’t cover the full description of the problem, just what we need to achieve. Please go through the link for the problem description.

Explanation

This is a shortest distance problem where we’re needed to find the minimum number of steps that would get us to the end. Given what we know about distance problems, we’d use a breadth-first search for solving this problem. Before we proceed, let’s understand the rules that govern this game.

• A board contains a snake or ladder if the content of the cell is not -1
• The destination cell of a die roll (next) is in the range [curr + 1, min(curr + 6, n^2)] where curr is the current cell you’re on.
• If next is a snake or a ladder, you must move to the destination of that snake or ladder.
• The game ends when you reach the n^2 cell.

Some edge cases we have to consider,

1. The 1st position of the board starts from the bottom left position as opposed to the top left.
2. The spiral nature of moving across the board, i.e. left-to-right → right-to-left → left-to-right → and so on.
3. The board could be even or odd-sided.

To solve the first problem, we need to find a way to map the exact coordinates (row, column) to a number (1 to n inclusive) on an nxn matrix. There are two possible ways to solve this

1. Create a list A whose index is the number i and whose value is the exact coordinate such that A[i] = (X_i, Y_i).
2. Define a function that returns the coordinate of any given number, and computes the coordinate of any given number on the fly.

While the first approach is more space-intensive than the second (n^2), it’s faster because we’d only need to compute it once and subsequent calls to get a coordinate would be constant.

The way we’d construct our position to coordinate map list would help us in covering the second edge case and for the last edge case which determines where (n^2) is located on the board, we’d use a neat trick to figure that out.

Solution Steps

• Step 1 → Build the position to coordinate map
• Step 2 → Get the end coordinate
• Step 3 → Play the game and return minimum steps.

Step 1

1def buildSquareToCell(self, board: list[list[int]]) -> list[list[tuple[int, int]]]:
2       self.squareToCell = []
3       leftToRight = True
4
5       for r in range(self.ROW - 1, -1, -1):
6           for c in range(self.COL):
7               if leftToRight:
8                   coordinate = (r, c)
9               else:
10                   coordinate = (r, self.COL - c - 1)
11               self.squareToCell.append(coordinate)
12           leftToRight = not leftToRight

Let’s explain what’s happening in the code above. First, we define a squareToCell list that holds the coordinates in the board and a leftToRight variable that determines the spiral order i.e. left to right or right to left. The board always starts left to right. Next, we iterate from the last row (position 1 starts from the bottom left position) and the first column. If we’re currently traversing from left to right, then our coordinate position is (r,c) otherwise our row remains the same, but the column starts from right to left and we get that by subtracting the current column and 1 from the overall size of the column. Lastly, we append the coordinate to the squareToCell list and reverse the order of our traversal.

Step 2

The end coordinate is dependent on whether the board is odd-sized or even-sized. If it’s even-sized, the end coordinate is (0,0) else the end coordinate is first row, last column i.e. (0, self.COL - 1).

1# define end coordinate as it varies 
2# if board is odd-sized or even-sized
3endCoordinate = (0, 0) if self.COL % 2 == 0 else (0, self.COL - 1)

Step 3

1def snakesAndLadders(self, board: list[list[int]]) -> int:
2        self.ROW = self.COL = len(board)
3        self.buildSquareToCell(board)
4        
5        visited = set()
6        queue = collections.deque([(1, 0)])
7        
8        # define end coordinate as it varies if board is odd-sized or even-sized
9        endCoordinate = (0, 0) if self.COL % 2 == 0 else (0, self.COL - 1)
10        
11        while queue:
12            curr, step = queue.popleft()
13            currX, currY = self.squareToCell[curr - 1]
14            
15            if (currX, currY) == endCoordinate:
16                return step
17            
18            for newPosition in range(curr + 1, min(curr + 7, self.ROW ** 2 + 1)):
19                
20                newX, newY = self.squareToCell[newPosition - 1]
21                
22                if board[newX][newY] != -1:
23                    finalPosition = board[newX][newY]
24                    
25                    if finalPosition not in visited:
26                        visited.add(finalPosition)
27                        queue.append((finalPosition, step + 1))
28                else:
29                    if newPosition not in visited:
30                        queue.append((newPosition, step + 1))
31                        visited.add(newPosition)
32        return -1

Let’s break the code above down.

• We define the ROW and COL size to be the size of the board
• Then we call buildSquareToCell function to populate squareToCell with the position to coordinate mapping
• Then a visited set that would store the positions that we’ve visited on the board
• A queue that initially contains the starting position and the number of steps taken for us to get there.
• We iterate while our queue isn’t empty and pop the last item from the queue. This would contain the current position (curr) and the number of steps (step)
• We retrieve the coordinates of the position we’re currently traversing (curX, curY) from the squareToCell list.
• If the coordinate we retrieved is the end coordinate, then we’ve reached the end of the board and we return the steps.
• Else we consider all possible steps that we could take from our current position. This is achieved by iterating over the range of possible positions from curr + 1 and the minimum between 6 positions after the current or the last position in the board which is gotten as the square of the dimension. You’d notice that we are adding +7 to the first argument to minimum and +1 to the second argument. This is because the stop argument to the range function is exclusive and we want to ensure we consider 6 positions.
  • Next, we get the coordinate of newPosition , if the coordinate is a snake or ladder, we retrieve the position we’re to follow and we add it to our set holding visited positions and append it to our queue with steps increased by one. This is equivalent to following the destination of the snake or ladder as the newPosition contained a snake/ladder that took us to a new position on the board.
  • If the coordinates of newPosition aren’t a snake or ladder, we append newPosition to the visited set if it hasn’t been traversed previously. We also append it to the queue with a step increase of one.
• We only add positions to the queue when they’re not found in the visited set because if that position has been found in the set, then there’s been a previous position on the board that we’ve traversed that contains the minimum number of steps to get us to that position (newPosition).
• Lastly, if we terminate from the loop without returning the steps, then there’s no possible path that gets us to the end of the board so we return -1.

Final Code

1class Solution:
2    
3    def buildSquareToCell(self, board: list[list[int]]) -> list[list[tuple[int, int]]]:
4
5        self.squareToCell = []
6        leftToRight = True
7        
8        for r in range(self.ROW - 1, -1, -1):
9            for c in range(self.COL):
10                if leftToRight:
11                    coordinate = (r, c)
12                else:
13                    coordinate = (r, self.COL - c - 1)
14                self.squareToCell.append(coordinate)
15            leftToRight = not leftToRight
16
17    def snakesAndLadders(self, board: list[list[int]]) -> int:
18        self.ROW = self.COL = len(board)
19        self.buildSquareToCell(board)
20        
21        visited = set()
22        queue = collections.deque([(1, 0)])
23        
24        # define end coordinate as it varies if board is odd-sized or even-sized
25        endCoordinate = (0, 0) if self.COL % 2 == 0 else (0, self.COL - 1)
26        
27        while queue:
28            curr, step = queue.popleft()
29            currX, currY = self.squareToCell[curr - 1]
30            
31            if (currX, currY) == endCoordinate:
32                return step
33            
34            for newPosition in range(curr + 1, min(curr + 7, self.ROW ** 2 + 1)):
35                
36                newX, newY = self.squareToCell[newPosition - 1]
37                
38                if board[newX][newY] != -1:
39                    finalPosition = board[newX][newY]
40                    
41                    if finalPosition not in visited:
42                        visited.add(finalPosition)
43                        queue.append((finalPosition, step + 1))
44                else:
45                    if newPosition not in visited:
46                        queue.append((newPosition, step + 1))
47                        visited.add(newPosition)
48        return -1

Complexity explanation

Let’s look at the complexity of this problem.

If N is the size of the board, we have a total of N * N squares on the board which means the highest level we can traverse on the board is equal to N which also represents the depth of the tree.

Breadth-First Search Complexity

1. If there are no ladders or snakes on the board, we’d have to traverse every inch of the board step by step and explore possibly all paths which means that at some point they’d all be on the board but at most once thanks to the set of visited positions.
2. Each time we pop out of the queue, the board would contain N - 1 element, so in the worst case, we’d have popped N * N - (N-1) times which is equivalent to N*N times. During the iteration for new positions to visit, we loop through a maximum of 6 possible newPosition because we use a 6-sided die. In each iteration of the loop, we perform constant operations
   • Retrieval of coordinates → O(1)
   • Set lookup and entry → O(1) each
   • Queue addition → O(1) each
3. Therefore, the time complexity is upper-bounded by N^2 and the space complexity is N where N is the size of the queue.

Position to Coordinate Mapping List For building the squareToCell array, we

1. loop N^2 times and perform constant operations to append the coordinates to the list.
2. the sqaureToCell array size is N^2 because it contains all the positions on the board.
3. Therefore the time and space complexity of constructing the squareToCell list is O(N^2)

Overall Complexity

• Time complexity → O(N^2)
• Space complexity → O(N^2)

Conclusion

Thank you for making it to the end, we hope you enjoyed this post as much as we enjoyed solving it. I found this problem really interesting and it took us more than an hour to come up with a solution that passed LeetCode’s judgement. We also had to discover the edge cases the hard way after minutes of racking our brains to figure out what we were missing.

In summary, we started with a big problem and found a way to break it down into smaller steps that helped us arrive at the solution. I’m sure there’s a software engineering concept for this but I can’t remember what it is 😁; tweet me if you do remember. Here’s my challenge for you, how would you solve this problem and can you come up with an algorithm that computes the coordinates of the position on the ✈️ ?