🐍 Snake and Ladders

Hi, Today we are going to solve a famous programming interview problem which has been asked in many companies like big giants Amazon, Microsoft, D E Shaw etc.

Snake Ladder is the big question I would definitely urge you to go through it before reading on.

Snake and Ladder Problem - GeeksforGeeks

In this problem you are given a board of N cell in which each cell denotes three type of things {Empty,ladder,snake}. You are the player and you are standing initially at cell 1 now you have to play the game such that you reaches the end cell in minimum number of dice throw.

For example our board looks like this

      [-1,-1,-1,-1,-1,-1] END
      [-1,-1,-1,-1,-1,-1]
      [-1,-1,-1,-1,-1,-1]
      [-1,35,-1,-1,13,-1]
      [-1,-1,-1,-1,-1,-1]
START [-1,15,-1,-1,-1,-1]

Here in board -1 means it is safe you can go to that cell but if the value of cell is not -1 then that means there will be either snake or ladder. if the value on a particular cell is taking you more closer to end that means it is a ladder otherwise it is a snake.

The minimum number of dice throw required in this case is 4.

BUT HOW ?🙄

So the answer is initially you are at cell 1 at bottom now you throw a dice with facing 1 on which you found a ladder and that takes you to cell number 15 then you throw the dice with facing 2 and reaches block no 17 on which snake bites you and you get down to block no 13 and then and then you throw the dice with facing 1 and that takes you to block no 35 through ladder and after that you need only 1 more dice throw with facing 1 and then you reaches destination.

What if the size of board is 1000 or more than is it possible for human to get minimized answer easily ?

No 😶

Here’s the programming come into the picture. We can make program so that our computer can easily calculate it.

Let’s write the code

vector<int> board(size+1);     //replace size with the size of board
vector<bool> vis(size+1,false);  //keep track of each cell

Initialize board with -1 value where -1 represent cell with no ladder or snake.

for(int i=1;i<=board.size();i++)
board[i]=-1;

Now take the input from the user of ladders and store them into board. Suppose user give you the input in the following form {a,b} that means on cell a store value b.

cin>>a>>b;
board[a]=b;

Similarly take input for snakes also.

Main Code Begins now

make a queue of pair to store cell information each information will consist of last traversed cell number with min throws till now.

queue<array<int,2>> q;
q.push({1,0});
vis[1]=true;

We have initialize queue with initial position 1 and min thrown dice is 0 and make vis true.

        while(!q.empty())
        {
            array<int,2> top=q.front();
            q.pop();
            
            int ind=top[0];
            
            if(ind>=size)
            {
                cout<<top[1]<<endl;
                break;
            }
         }

So till now we have initialize queue with initial position and traverse the queue while is does not get empty or till we find the last cell.

            for(int i=ind+1; i<size+1 && i<=(ind+6);i++)
            {
                if(vis[i]==false)
                {
                    array<int,2> temp;
                    temp[1]=top[1]+1;
                    vis[i]=true;
                    
                    if(board[i]!=0)
                    {
                        temp[0]=board[i];
                    }
                    else
                    temp[0]=i;
                    
                    q.push(temp);
                }
            }

Now we have initialize a for loop with condition i<size+1 && i≤(ind+6) because from a particular position you can go till 6 cell ahead so we tried all possibility and making dice throw increase by 1 of previous dice throw i.e (new dice throw = previous dice throw+1)and checking that after throwing dice we are at a particular position and on that position if it’s value is -1 then we take top[0] as i otherwise we take top[0] as board[i].

All code together

        vector<int> board(size+1,-1);
        vector<bool> vis(size+1,false);
        for(int i=0;i<size;i++)
        {
            int a,b;
            cin>>a>>b;
            board[a]=b;
        }
        
        queue<array<int,2>> q;
        q.push({1,0});
        vis[1]=true;
        
        while(!q.empty())
        {
            array<int,2> top=q.front();
            q.pop();
            
            int ind=top[0];
            
            if(ind>=size)
            {
                cout<<top[1]<<endl;
                break;
            }
            
            for(int i=ind+1; i<size+1&& i<=(ind+6);i++)
            {
                if(vis[i]==false)
                {
                    array<int,2> temp;
                    temp[1]=top[1]+1;
                    vis[i]=true;
                    
                    if(board[i]!=0)
                    {
                        temp[0]=board[i];
                    }
                    else
                    temp[0]=i;
                    
                    q.push(temp);
                }
            }
        }

That’s all for now!

I hope this article will help people who want to learn about programming or those who want to enhance their skills.