# Snakes and Ladders: The Quickest Way Up

# Snakes and Ladders: The Quickest Way Up

m_a_r_c_e_li_n_o + 16 comments For those that are new to Graph Theory (i.e. myself), take a bit of time to firmly understand the construction of a Graph using an adjacency list, and how to explore the adjacency list using a "Breadth First Search" algorithm. Only then you'll be able to comprehend why this problem was categorized as "easy". I know there are people here succesfully solving it through "Dynamic Programming", and it's a valid method, but if you take that route, you'll miss out on an elegant and simple "Graph Theory" solution that I would argue is the purpose of this challenge. Admins, perhaps it might not be the worse idea to include "Adjacency List" and "Breadth First Search" as topics for this problem.

At any rate, if you are struggling as much as I was, take a look at this: http://theoryofprogramming.com/2014/12/25/snakes-and-ladders-game-code/

savras + 0 comments New to Graph theory and the link helped me solve this. Took me a while but it was well worth it! :)

smith1023 + 0 comments I definately will look into it. I solved it with a markov chain, it seemed apropriate... or maybe the name in the problem statement misleaded me :3

Foxkmi + 0 comments In that link:

"... He assume that getting caught by a snake is always unfavorable, and will not add to the progress of a short path..."

That is false. Is easy find an example.

jatinshravan + 2 comments "getting caught by a snake is always unfavorable, and will not add to the progress of a short path"

This does not seem to be accurate. Suppose a ladder is from 2 to 82, a snake is from 84 to 62 and another ladder is from 62 to 99 and nothing else, the optimal solution is to take the ladder to 82, then the snake from 84 to 62 and then take the ladder from 62 to 99.

alebrozzo + 0 comments Not correct, as the statement says "No square will have more than one of the starting or ending point of a snake or ladder (e.g. snake 56 to 44 and ladder 44 to 97 is not possible because 44 has both ending of a snake and a starting of a ladder)" However, Foxkmi is correct, you could have six consecutive short ladders that impede you to reach a large ladder, and theonly way to get that ladder is by the way of a snake. EG: ladders 21 to 39, 22 to 38, 23 to 37, 24 to 36, 25 to 35, 26 to 34, 28 to 95 snake 40 to 27 Falling from snake 40 helps you reach the ladder on square 28 that takes you one roll away from the winning square

mahpat + 1 comment Ladder from 2 to 82, Snake from 84 to 63 Ladder from 64 to 99

zainul118 + 1 comment but 100-82 = 18 so 3 turns which is same as with snake : 82-> 84, 63->64, 99->100.

I_luv_KitKat + 0 comments Then what about

Ladder from 2 to 50, Snake from 52 to 20, Ladder from 25 to 99

then it has only 4 steps to 100 (1-2) (50-52) (20-25) (99-100)

meteabogdan + 0 comments Thanks for the awesome link!!!

rizkidwip + 0 comments Thank you so much for this link. It gaves me correct way to solve this, with C# using BFS (level by level search) :

**my first Graph**harshloomba1 + 0 comments Thanks for the wonderful link. Here is my solution in java entirely based on the idea provied in the link

import java.io.

*; import java.util.*;public class QuickestWayUpLadder { private static byte MAX_ROLL = 6; private static byte BOARD_LEN = 100; private static Map> adjencyMap=new HashMap>(); private static Map listSnakes=new HashMap(); private static Map listLadders=new HashMap();

public static void main(String[] args) throws IOException { final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

`//Create board final byte[] board = new byte[BOARD_LEN]; //For every test case for(byte T = Byte.parseByte(br.readLine()); T > 0; --T){ //Initialize board for(byte i = 0; i < BOARD_LEN; ++i){ board[i] = i; } //Get ladder for(byte N = Byte.parseByte(br.readLine()); N > 0; --N){ final String[] line = br.readLine().split(" "); final byte S = (byte)(Byte.parseByte(line[0]) - 1); final byte E = (byte)(Byte.parseByte(line[1]) - 1); listLadders.put(S,E); } //Get snakes for(byte M = Byte.parseByte(br.readLine()); M > 0; --M){ final String[] line = br.readLine().split(" "); final byte S = (byte)(Byte.parseByte(line[0]) - 1); final byte E = (byte)(Byte.parseByte(line[1]) - 1); listSnakes.put(S,E); } System.out.println(); for(byte i = 0; i < BOARD_LEN; ++i){ System.out.print(board[i]+" "); } createAdjacencyList(board); replace(); printAdjencyList(); breathFirstSearch(); //Solve and print output`

// System.out.println(getMinMoves(board)); } }

private static void createAdjacencyList(byte[] board){

`for(byte i=0;i<board.length;i++){ for(byte j=0;j<7;j++){ if(i+j>99) break; if(adjencyMap.containsKey(board[i])) adjencyMap.get(board[i]).add(board[i+j]); else adjencyMap.put(board[i],new ArrayList(board[i+j])); } }`

}

private static void printAdjencyList(){ for(byte i :adjencyMap.keySet()){ System.out.println(); System.out.print("key: "+i+"values: "); for(byte temp: adjencyMap.get(i)) { System.out.print(temp+" "); } } }

private static void replace(){ for(Byte t: adjencyMap.keySet()){ List temp=new ArrayList();

`for(Byte t1: adjencyMap.get(t)) { if(listLadders.containsKey(t1)){ temp.add(listLadders.get(t1)); } else if(listSnakes.containsKey(t1)){ temp.add(listSnakes.get(t1)); } else temp.add(t1); } adjencyMap.put(t,temp); }`

}

private static void breathFirstSearch(){ int count=0; byte i=0; while(i!=99){ List temp=adjencyMap.get(i); Collections.sort(temp); i=temp.get(temp.size()-1); count++; if(i>99) break; } System.out.println(); System.out.println("number of steps: "+count); } }

rakeshKM + 0 comments Thanks man, for the link it was really helpfull

mk9440 + 5 comments Solved using Dijkshtra algorithm :D

import java.util.*; import java.io.*; public class Solution { public static void main(String[] args){ Scanner in=new Scanner(System.in); int test=in.nextInt(); for(int h=0;h<test;h++){ int w[][]=new int[101][101]; for(int i=1;i<=100;i++){ for(int j=1;j<=100;j++){ if(i!=j &&i<j && Math.abs(j-i)<=6){ w[i][j]=1; } else{w[i][j]=1000000;} }} int ladder=in.nextInt(); for(int i=0;i<ladder;i++){ int x=in.nextInt(),y=in.nextInt(); w[x][y]=0; } int snake=in.nextInt(); int sn[]=new int[snake]; for(int i=0;i<snake;i++){ int x=in.nextInt(),y=in.nextInt();sn[i]=x; w[x][y]=0; } Arrays.sort(sn);int cnt=0; for(int g=0;g<snake;g++){if(g>0 && sn[g]-sn[g-1]==1){++cnt;}else{cnt=0;}if(cnt>=6){break;}} Stack <Integer> t=new Stack<Integer>(); int src=1,des=100; for(int i=1;i<=100;i++){ if(i!=src){t.push(i);}} Stack <Integer> p=new Stack<Integer>(); p.push(src); while(!t.isEmpty()){int min=989997979,loc=-1; for(int i=0;i<t.size();i++){ w[src][t.elementAt(i)]=Math.min(w[src][t.elementAt(i)],w[src][p.peek()]+w[p.peek()][t.elementAt(i)]); if(w[src][t.elementAt(i)]<=min){ min=(int) w[src][t.elementAt(i)];loc=i;} } p.push(t.elementAt(loc));t.removeElementAt(loc);} if(cnt>=6){System.out.println("-1");continue;} if(w[src][des]!=1000000){System.out.println(w[src][des]);} else {System.out.println("-1");} }}}

Noel7 + 0 comments [deleted]Noel7 + 0 comments [deleted]Noel7 + 0 comments [deleted]pareek_kunal83 + 1 comment I think this one needs Djikstra to solve and not BFS as the top voted answer seems to suggest.

aleksander_wald1 + 1 comment I am only about to solve this problem but I think BFS is fine - all the edges in the graph have length of 1 (1 die roll to be precise) You should be fine doing BFS then.

Gh05t + 0 comments Yes, but Dijkstra is more easier to run on this problem, simply provide the snakes as posivitive weight and ladders as negative weight, and run dijkstra, making the graph suitable for bfs takes a bit of work.

alidanish + 0 comments Exactly I also did it with Dijkstra, but interesting thing is when cost of all edges are same in graph, then Dijkstra can be reduced to simple BFS with complexity of O(n). So Dijkstra is good but BFS gives better complexity as it is a special case of Dijkstra where cost of all edges are same.

12_gunank + 0 comments Thanks a lot for this link with amazing explanation!

saketk21 + 0 comments [deleted]DOER96 + 0 comments helpful link...gives an exact idea ..all u need is the implementation of the code and finding distance using bfs.

cs33shivam + 0 comments Thanks For the Link Sir, really helped me to undersatnd the concept.

subhajit104 + 0 comments really appreacited. All I understand how well you make the adj list. Just implememt bfs and "BINGO".

f(i,100){ if(snakes[i] or ladders[i]) continue; f1(j,1,7){ if(ladders[i+j] != 0){ adj[i].pb(ladders[i+j]); } else if(snakes[i+j] != 0 ){ adj[i].pb(snakes[i+j]); } else { adj[i].pb(i+j); } } } bfs(1);

partheshsoni + 0 comments I think using adjacency matrix is easier than using adjacency list due to relative easy of changing the updating the nodes for ladders and snakes.

sanketagarwal702 + 0 comments Your comment is very much helpful. Thankew very much

sidprasad + 0 comments It's a bigger challenge getting the input right, than solving the problem :P

AKSaigyouji + 6 comments I'm seeing some pretty crazy solutions for this problem (Dijkstra's, Bellman Ford, dynamic programming, etc.)

This is a straightforward BFS, and doesn't even require the explicit construction of a graph, just an array with 100 (or 101) slots. For each slot, place either the index of that slot (i.e. 5th spot has a 5 in it), or, if it has the head of a snake or start of a ladder, the endpoint of that snake/ladder.

The slots form an implicit graph where the connected vertices from a given slot are the 6 slots after the current one.

Running a BFS on this implicit graph will get you the solution.

The reason you don't need dijkstra's is that you're only measuring the number of die rolls: you don't care about distance travelled (edge weights). Similarly, you don't need bellman ford as that is an algorithm needed to handle negative edge weights.

onecrane + 0 comments Thanks for this - I was going to go Dijkstra, but it felt a little heavy for a graph with equal edge costs. I wouldn't have thought of BFS, and needed to think of how to apply it, but doing so gave me an addition to the toolbox!

ic3balandran + 1 comment This comment actually made more sense to me. Especially your last paragraph. I'm new to graph problems, I understand BFS and DFS, but I didn't know how to approach the whole die rolls. The key in the BFS is to enqueue its adjacent nodes based on the max die roll value which is 6 (Could be 12 if using two dice), but you need to watch out for snakes while doing it. Also for me I checked if there were 6 consecutive Nodes with a snake head and if I found that true I return -1, I did this before the BFS no need to do a BFS if there is no possible solution.

czhang2718 + 0 comments "I checked if there were 6 consecutive Nodes with a snake head and if I found that true I return -1"- Though this might pass the test cases, I don't think this necessarily is true because there could be a ladder before a block of 6 snakes that "hops over" them.

ryashin_egor + 0 comments Most useful hint! Thanks!

xdavidliu + 2 comments here's a simple java solution that does it according to your description

import java.util.Scanner; import java.util.ArrayDeque; import java.util.Queue; class Solution{ static final int squares=100; static final int nowhere=-1; static int solve(int[] trans){ boolean[] vis=new boolean[squares]; Queue<Integer> q=new ArrayDeque<Integer>(); final int start=0,dice=6,noSolution=-1,win=squares-1; q.add(start); vis[start]=true; int[] roll=new int[squares]; // q never contains spot with start of snake/ladder while(!q.isEmpty()){ int x=q.poll(); for(int i=1;i<=dice && x+i<squares;++i){ int j=x+i; while(!vis[j]){ vis[j]=true; if(j==win) return roll[x]+1; else if(trans[j]==nowhere){ q.add(j); roll[j]=roll[x]+1; } else j=trans[j]; } } } return noSolution; } static int[] transport(int[][] ladder, int[][] snake){ int[] tr=new int[squares]; for(int i=0;i<squares;++i) tr[i]=nowhere; for(int[] l: ladder) tr[l[0]]=l[1]; for(int[] s: snake) tr[s[0]]=s[1]; return tr; } static int[][] readEdge(int n, Scanner sc){ int[][] edge=new int[n][2]; for(int i=0;i<n;++i){ edge[i][0]=sc.nextInt()-1; edge[i][1]=sc.nextInt()-1; } return edge; } static void input(){ Scanner sc=new Scanner(System.in); int t=sc.nextInt(); for(int i=0;i<t;++i){ int n=sc.nextInt(); int[][] ladder=readEdge(n,sc); int m=sc.nextInt(); int[][] snake=readEdge(m,sc); int[] trans=transport(ladder,snake); System.out.println(solve(trans)); } sc.close(); } public static void main(String[] args){ input(); } }

da182 + 0 comments Thanks for the explanation!

dzmitry_lahoda + 0 comments For python3, i have used next starter before BFS cycle:

`visited = set() queue = [] ladders = {i:j for i,j in ladders} snakes = {i:j for i,j in snakes} queue.append((1,0))`

ziggystar + 1 comment Why can't this problem use the usual space and newline separated format?

shashank21jHackerRank Admin + 1 comment updated :)

ShubhamV06 + 1 comment how is (-1) possible?

jcarlson08 + 1 comment Imagine a board where space 100 is the goal and spaces 99, 98, 97, 96, 95, and 94 are all snakes leading to previous positions.

ShubhamV06 + 0 comments Thanks!

mtanida + 1 comment This problem is sort of unintuitive for people who've never heard of Snakes and Ladders. I feel like the problem description and the example problem can be improved to explain the rules of the game more clearly.

hwu533 + 0 comments Agreed. I feel like if we have to spend time reading an external link, it should be a cool algorithm not the rules for a game.

Sort 179 Discussions, By:

Please Login in order to post a comment