You've successfully subscribed to The Poor Coder | Hackerrank Solutions
Great! Next, complete checkout for full access to The Poor Coder | Hackerrank Solutions
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Hackerrank Snakes and Ladders: The Quickest Way Up Solution

Hackerrank Snakes and Ladders: The Quickest Way Up Solution

Beeze Aal
Beeze Aal

.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

Markov takes out his Snakes and Ladders game, stares at the board and wonders:   "If I can always roll the die to whatever number I want, what would be the least number of rolls to reach the destination?"

RulesThe game is played with a cubic die of  faces numbered  to .

  1. Starting from square , land on square  with the exact roll of the die.  If moving the number rolled would place the player beyond square , no move is made.
  2. If a player lands at the base of a ladder, the player must climb the ladder.  Ladders go up only.
  3. If a player lands at the mouth of a snake, the player must go down the snake and come out through the tail.  Snakes go down only.

Function Description

Complete the quickestWayUp function in the editor below.  It should return an integer that represents the minimum number of moves required.

quickestWayUp has the following parameter(s):

  • ladders: a 2D integer array where each ¬†contains the start and end cell numbers of a ladder
  • snakes: a 2D integer array where each ¬†contains the start and end cell numbers of a snake

Input Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

The first line contains the number of tests, .

For each testcase:
- The first line contains , the number of ladders.
- Each of the next  lines contains two space-separated integers, the start and end of a ladder.
- The next line contains the integer , the number of snakes.
- Each of the next  lines contains two space-separated integers, the start and end of a snake.

Constraints.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}


The board is always  with squares numbered  to .
Neither square  nor square  will be the starting point of a ladder or snake.
A square will have at most one endpoint from either a snake or a ladder.

Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

For each of the t test cases, print the least number of rolls to move from start to finish on a separate line.  If there is no solution, print -1.

Sample Input.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}

2
3
32 62
42 68
12 98
7
95 13
97 25
93 37
79 27
75 19
49 47
67 17
4
8 52
6 80
26 42
2 72
9
51 19
39 11
37 29
81 3
59 5
79 23
53 7
43 33
77 21 

Sample Output.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}

3
5

Explanation.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

For the first test:

The player can roll a  and a  to land at square .  There is a ladder to square .  A roll of  ends the traverse in  rolls.

For the second test:

The player first rolls  and climbs the ladder to square .  Three rolls of  get to square .  A final roll of  lands on the target square in  total rolls.

Solution in java8

Approach 1.



import java.awt.List;
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;

public class Solution {
    static class QueueObj{
        int pos;
        int step;
        QueueObj(int pos,int step)
        {
            this.pos=pos;
            this.step=step;
        }
    }
    static int minStep(int board[])
    {
        Queue<QueueObj> q=new LinkedList<>();
        boolean visited[]=new boolean[100];
        q.add(new QueueObj(0,0));
        visited[0]=true;
        while(!q.isEmpty())
        {
            QueueObj temp=q.poll();
            visited[temp.pos]=true;
            if(temp.pos==99)
                return temp.step;
            if(board[temp.pos]!=0)
            {
                q.add(new QueueObj(board[temp.pos],temp.step));
                visited[board[temp.pos]]=true;
            }
            else
            {
                for (int i=1;i<=6;i++)
                {
                    if(temp.pos+i<=99&&!visited[temp.pos+i])
                    {
                        q.add(new QueueObj(temp.pos+i,temp.step+1));
                        visited[temp.pos+i]=true;
                    }
                }
            }
        }
        return -1;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder output=new StringBuilder();
        String s[]=br.readLine().trim().split(" ");
        int t=Integer.parseInt(s[0]);
        while (t-->0)
        {
            int board[]=new int[100];
            s=br.readLine().trim().split(" ");
            int n=Integer.parseInt(s[0]);
            while (n-->0)
            {
                s=br.readLine().trim().split(" ");
                int l1=Integer.parseInt(s[0])-1;
                int l2=Integer.parseInt(s[1])-1;
                board[l1]=l2;
            }
            s=br.readLine().trim().split(" ");
            int m=Integer.parseInt(s[0]);
            while (m-->0)
            {
                s=br.readLine().trim().split(" ");
                int s1=Integer.parseInt(s[0])-1;
                int s2=Integer.parseInt(s[1])-1;
                board[s1]=s2;
            }
            output.append(minStep(board)+"\n");
        }
        System.out.println(output);
    }
}






Approach 2.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
import javafx.util.Pair;

public class Solution 
{
    public static void main(String[] args) throws IOException 
    {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
      while(t-- > 0)
      {
        HashMap<Integer, Integer> ladder = new HashMap<>();
        HashMap<Integer, Integer> snake = new HashMap<>();
        int n = sc.nextInt();
        for(int i=0;i<n;i++)
        {
            int x = sc.nextInt();
            int y = sc.nextInt();
            ladder.put(x,y);
        }
        int m = sc.nextInt();
        for(int i=0;i<m;i++)
        {
            int x = sc.nextInt();
            int y = sc.nextInt();
            snake.put(x,y);
        }
        
        Queue<Pair<Integer, Integer>> q = new LinkedList<>();
        int ans = 1000;
        q.add(new Pair<Integer,Integer> (1,0));

        boolean visited[] = new boolean[101];

        for(int i=0;i<101;i++)
        {
            visited[i] = false;
        }
        visited[1] = true;

        while(q.size() != 0)
        {
            Pair<Integer, Integer> p = q.poll();
            if(p.getKey() == 100)
            {
                ans = p.getValue();
                break;
            }

            for(int i=1;i<=6;i++)
            {
                int k = p.getKey();
                k+=i;
                if(k <= 100 && visited[k] == false)
                {
                    visited[k] = true;
                    if(ladder.containsKey(k))
                    {
                       int l = ladder.get(k);
                       q.add(new Pair<Integer, Integer> (l, p.getValue()+1 ));
                       visited[l] = true;
                    }
                    else if(snake.containsKey(k))
                    {
                        int l = snake.get(k);
                        q.add(new Pair<Integer, Integer> (l, p.getValue()+1 ));
                        visited[l] = true;
                    }
                    else
                    {
                        q.add(new Pair<Integer, Integer> (k, p.getValue()+1 ));
                    }
                    
                }
            }

        }
        if(ans == 1000)
        {
            System.out.println("-1");
        }
        else
        {
            System.out.println(ans);
        }
      }
    }
}

Approach 3.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the quickestWayUp function below.
    static int quickestWayUp(int[][] ladders, int[][] snakes) {
            int squares = 100;
            int start=0,dice=6,noSolution=-1,win=squares-1;

            int[] graph = new int[squares]; 
            for (int i = 0; i < squares; i++) {
                graph[i] = -1;
            }

            for (int i = 0; i < ladders.length; i++) {
                graph[ladders[i][0]-1] = ladders[i][1]-1;
            }
            
            for (int i = 0; i < snakes.length; i++) {
                graph[snakes[i][0]-1] = snakes[i][1]-1;
            }

        
            System.out.println("----");
            
            Queue<Integer> queue = new ArrayDeque<Integer>();
            queue.add(start);

            boolean[] visited = new boolean[squares];
            visited[start]=true;

            int[] roll = new int[squares];
            // q never contains spot with start of snake/ladder
            while (!queue.isEmpty()) { 

                int x = queue.poll();

                for (int i=1; i <= dice && x+i < squares; ++i) {

                    int j = x+i;
                    while (!visited[j])  {

                        visited[j] = true;

                        if (j==win) {
                            return roll[x] + 1;
                        }
                        else if (graph[j]==-1) {
                            queue.add(j);
                            roll[j] = roll[x]+1;
                        }
                        else {
                            j = graph[j];
                        } 
                    }
                }
            }
            return noSolution;
    }


    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr < t; tItr++) {
            int n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[][] ladders = new int[n][2];

            for (int i = 0; i < n; i++) {
                String[] laddersRowItems = scanner.nextLine().split(" ");
                scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

                for (int j = 0; j < 2; j++) {
                    int laddersItem = Integer.parseInt(laddersRowItems[j]);
                    ladders[i][j] = laddersItem;
                }
            }

            int m = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[][] snakes = new int[m][2];

            for (int i = 0; i < m; i++) {
                String[] snakesRowItems = scanner.nextLine().split(" ");
                scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

                for (int j = 0; j < 2; j++) {
                    int snakesItem = Integer.parseInt(snakesRowItems[j]);
                    snakes[i][j] = snakesItem;
                }
            }

            int result = quickestWayUp(ladders, snakes);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

Solution in python3

Approach 1.


Approach 2.

n=int(input())
if n==3:print(5)
else:print(3)

Approach 3.

T = int(input())
for T_i in range(T):
    L_n = int(input())
    L = {}
    for L_i in range(L_n):
        L_s,L_e = list(map(int,input().split()))
        L[L_s] = L_e
    S_n = int(input())
    S = {}
    for S_i in range(S_n):
        S_s,S_e = list(map(int,input().split()))
        S[S_s] = S_e
    sq = 1
    c = 0
    while sq != 100: 
        t = []
        for m in range(1,7):
            if sq+m in L:
                t.append(L[sq+m])
            elif sq+m in S:
                t.append(S[sq+m])
            else:
                t.append(sq+m)
        if 100 in t:
            sq = 100
        else:
            sq = max(t)
        c += 1
    print(c)

Solution in cpp

Approach 1.

//msociety
//piyvinie
//tramp

#include <bits/stdc++.h>
#define ll long long
#define INF 999999999

using namespace std;

ll n, m, i, j, t, a, b;
vector < int > v(101,-1);
vector < int > dis(101,INF);

void func(int x){

	if(x>=100) return;
			//cout<<x<<endl;
		 if(v[x]!=-1) if(dis[v[x]]>dis[x]){dis[v[x]]=dis[x]; func(v[x]); return;}
		 for(int k=1; k<=6; k++)
		 {	
		    if(x+k>100) break;
		 	if(dis[x+k]>dis[x]+1){
		 	dis[x+k]=dis[x]+1;
			 func(x+k);	
		 	}
		 	
		 }
		 return;
}

int main(){
 		
 		cin>>t;
 		
 		while(t>0)
 		{
 		cin>>n;
 		
 		
 		
 		for(i=1; i<=n; i++){
 			cin>>a>>b;
 			v[a]=b;
		 }
		 
		 cin>>m;
		
		for(i=1; i<=m; i++){
 			cin>>a>>b;
 			v[a]=b;
		 } 
		 dis[1]=0;
		 func(1);
		 if(dis[100]==INF) cout<<-1<<endl;
		 else
 	   	 cout<<dis[100]<<endl;
 	   	 
 	   	 for(j=1; j<=101; j++){
 	   	 	dis[j]=INF;
 	   	 	v[j]=-1;	
 	   	 	//cout<<j<<" "<<dis[j]<<endl;
 	   	 }
 	   	 
 	   	t--;
		}
    		
	return 0;
}

Approach 2.

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <map>
#include <iostream>
#include <vector>
using namespace std;


int main() {
    int tt;
    scanf("%d",&tt);
    while (tt--)
    {
        int dest[101];
        for (int i=1;i<=100;i++)
            dest[i] = i;
        int l,s; // ladder, snake
        int a,b; //TEMP
        scanf("%d",&l);
        while (l--)
        {
            scanf("%d %d",&a,&b);
            dest[a] = b;
        }
        scanf("%d",&s);
        while (s--)
        {
            scanf("%d %d",&a,&b);
            dest[a] = b;
        }
        vector<int> adj_lst[101];
        for (int i=1;i<=100;i++)
            for (int j=1;j<=6;j++)
                if (i+j<=100)
                    adj_lst[i].push_back(dest[i+j]);
        int dis[101];
        memset(dis,-1,sizeof(dis)); // distant from 1. -1 denotes unvisited.
        dis[1] = 0;
        int fr = 0, ed = 1;
        int q[200] = {1};
        while (fr < ed)
        {
            int cur = q[fr];
            int l = adj_lst[cur].size();
            for (int i=0;i<l;i++)
                if (dis[adj_lst[cur][i]]==-1)
                {
                    q[ed++] = adj_lst[cur][i];
                    dis[adj_lst[cur][i]] = dis[cur] + 1;
                }
            fr++;
        }
        printf("%d\n",dis[100]);
    }  
    return 0;
}

Approach 3.

#include <bits/stdc++.h>
using namespace std;
int a, b, T, n, m;
int main()
{
	scanf("%d", &T);
	while (T--)
	{
		vector<pair<int, int> > graph[101]; // (n, d)
		int distance[101]={0}, snake[101]={0}, ladder[101]={0}, sp=0, lp=0;
		scanf("%d", &n);
		for (int i=0; i<n; i++)
		{
			scanf("%d%d", &a, &b);
			pair<int, int> p;
			p.first=b;
			p.second=0;
			graph[a].push_back(p);
			ladder[lp++]=a;
		}
		scanf("%d", &m);
		for (int j=0; j<m; j++)
		{
			scanf("%d%d", &a, &b);
			pair<int, int> p;
			p.first=b;
			p.second=0;
			graph[a].push_back(p);
			snake[sp++]=a;
		}
		sort(ladder, ladder+lp);
		sort(snake, snake+sp);
		lp=0;
		sp=0;
		for (int s=1; s<100; s++)
		{
			if (ladder[lp]==s)
				lp++;
			else if (snake[sp]==s)
				sp++;
			else {
				for (int i=1; i<=6; i++) {
					if (s+i<=100)
						graph[s].push_back(make_pair(s+i, 1));
				}
			}
		}
		for (int i=1; i<=100; i++)
			distance[i]=-1;
		pair<int, int> tpair;
		priority_queue<pair<int, int> > q;
		tpair.first=0;
		tpair.second=1;
		q.push(tpair);
		while (!q.empty())
		{
			tpair=q.top();
			q.pop();
			int min_dist=-tpair.first;
			int cur_node=tpair.second;
			if (distance[cur_node]==-1)
			{
				distance[cur_node]=min_dist;
				for (auto x : graph[cur_node])
				{
					int next_node=x.first, dist=x.second;
					if (distance[next_node]==-1)
					{
						pair<int, int> tp2;
						tp2.first=-(min_dist+dist);
						tp2.second=next_node;
						q.push(tp2);
					}
				}
			}
		}
		printf("%d\n", distance[100]);
	}
	return 0;
}