HackerRank Snakes and Ladders: The Quickest Way Up Problem Solution

HackerRank Snakes and Ladders: The Quickest Way Up

Yashwant Parihar,

In this post, we will solve HackerRank Snakes and Ladders: The Quickest Way Up Problem Solution.

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?”
Rules The game is played with a cubic die of 6 faces numbered 1 to 6.

  1. Starting from square 1, land on square 100 with the exact roll of the die. If moving the number rolled would place the player beyond square 100, 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 ladders[i] contains the start and end cell numbers of a ladder
  • snakes: a 2D integer array where each snakes[i] contains the start and end cell numbers of a snake

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

Output Format

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

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

3
5

Explanation
For the first test:
The player can roll a 5 and a 6 to land at square 12. There is a ladder to square 98. A roll of 2 ends the traverse in 3 rolls.
For the second test:
The player first rolls 5 and climbs the ladder to square 80. Three rolls of 6 get to square 98. A final roll of 2 lands on the target square in 5 total rolls.

HackerRank Snakes and Ladders: The Quickest Way Up Problem Solution
HackerRank Snakes and Ladders: The Quickest Way Up Problem Solution

Snakes and Ladders: The Quickest Way Up C Soluton

#include <stdio.h>
#include <string.h>

#define DIM 100

#define MIN(x,y) ((x) < (y) ? (x) : (y))

int graph[DIM][DIM];
int shortest[DIM];

void _reset(void)
{
  int i, j;
  
  for (i = 0; i < DIM; i++) {
      for (j = i; j < DIM; j++) {
          graph[i][j] = 0;
          graph[j][i] = 0;
      }
  }
  
  for (i = 0; i < DIM; i++) {
    for (j = i + 1; j < MIN(DIM, i + 7); j++) {
      graph[i][j] = 1;
      graph[j][i] = 1;
    }

    shortest[i] = -1;
  }

  shortest[DIM-1] = 0;
}

int _get_shortest(int coord)
{
  int min = 0x7fffffff;
  int i;

  if (shortest[coord] != -1) {
    goto ret;
  }

  for (i = coord + 1; i < DIM; i++) {
    if (!graph[coord][i]) {
      continue;
    }

    min = MIN(min, _get_shortest(i));
  }

  if (min == 0x7fffffff) {
    shortest[coord] = min;
  } else {
    shortest[coord] = min + 1;
  }

 ret:

  return shortest[coord];
}

int main(void)
{
  int n, N;

  scanf("%d", &N);
    
  for (n = 0; n < N; n++) {
    int l, ladders, s, snakes;
    int src, dst;

    scanf("%d,%d", &ladders, &snakes);

    _reset();

    for (l = 0; l < ladders; l++) {
      scanf("%d,%d", &src, &dst);
      src--;
      dst--;

      graph[src][dst] = 1;
      graph[dst][src] = 1;
    }

    for (s = 0; s < snakes; s++) {
      int i;

      scanf("%d,%d", &src, &dst);
      src--;
      dst--;
        
      for (i = 0; i < DIM; i++) {
        graph[i][src] = 0;
        graph[src][i] = 0;
      }
    }

    printf("%d\n", _get_shortest(0) - 1);
  }

  return 0;
}

Snakes and Ladders: The Quickest Way Up C++ Soluton

#include <cmath>
#include <cstdio>
#include <queue>
#include <vector>
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

vector<pair<int, int>> ladders;
vector<pair<int, int>> snakes;
vector<int> distances;

int HandleSnake(int x){
    auto iter = find_if(snakes.begin(), snakes.end(), [x](pair<int, int> snake){
        return snake.first == x;
    });
    
    if (iter == snakes.end())
        return x;
    
   // cout << "taking snake from " << x << " to " << iter->second << endl;
    return iter->second;
}

int HandleLadder(int x){
    auto iter = find_if(ladders.begin(), ladders.end(), [x](pair<int, int> ladder){
        return ladder.first == x;
    });
    
    if (iter == ladders.end())
        return x;
    
    return iter->second;
}

int BFS(){
    
    distances.clear();
    distances.resize(101, INT_MAX);
    
    
    queue<int> q;
    q.emplace(1);
    distances.at(1) = 0;
    while(!q.empty()){
        
        int curr = q.front();
        q.pop();
        
        
        for(int roll = 1; roll <= 6 ; ++roll){
            
            
            auto dest = curr + roll;                        
            if (dest > 100)
                continue;
            
            dest = HandleSnake(dest);
            dest = HandleLadder(dest);
            
            if (distances.at(dest) > distances.at(curr)+1){
    
                distances.at(dest) = distances.at(curr)+1;
                q.emplace(dest);
            }            
        }
    }    
    auto result = distances.back();
    result = (result == INT_MAX) ? -1 : result;
    return result;
}

void DoTestCase(){
    
    int num_ladders;
    cin >> num_ladders;
    ladders.resize(num_ladders);
    for(auto& ladder : ladders){
        cin >> ladder.first >> ladder.second;
    }
    
    int num_snakes;
    cin >> num_snakes;
    snakes.resize(num_snakes);

    for(auto& snake : snakes){
        cin >> snake.first >> snake.second;
    }
    
    cout << BFS() << endl;
}

int main() {
    int t;
    cin >> t; 
    for(int i = 0 ; i < t ; ++i){
        
        DoTestCase();
        
    }
    return 0;
}

Snakes and Ladders: The Quickest Way Up C Sharp Soluton

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class SnakesAndLadders
{
    static void Main(String[] args)
    {
        const int maxSquares = 100;
        var testCases = int.Parse(Console.ReadLine());

        for (int t = 0; t < testCases; t++)
        {
            var counts = Console.ReadLine().Split(',').Select(i => int.Parse(i)).ToList();
            var ladders = Console.ReadLine()
                .Split(' ')
                .Select(i =>
                {
                    var split = i.Split(',');
                    return new Tuple<int, int>(int.Parse(split[0]) - 1, int.Parse(split[1]) - 1);
                })
                .Take(counts[0])
                .ToList();

            var snakes = Console.ReadLine()
                .Split(' ')
                .Select(i =>
                {
                    var split = i.Split(',');
                    return new Tuple<int, int>(int.Parse(split[0]) - 1, int.Parse(split[1]) - 1);
                })
                .Take(counts[1])
                .ToList();

            var squares = new int?[100];
            squares[maxSquares - 1] = 0;

            for (int i = maxSquares - 2; i >= 0; i--)
            {
                var ladder = ladders.SingleOrDefault(j => j.Item1 == i);
                var snake = snakes.SingleOrDefault(j => j.Item1 == i);
                if (ladder != null)
                {
                    squares[i] = squares[ladder.Item2];
                }
                else if (snake != null)
                {
                }
                else
                {
                    squares[i] = Enumerable.Range(1, 6).Where(j => i + j < maxSquares).Min(j => squares[i + j]) + 1;
                }
            }

            foreach (var snake in snakes)
            {
                squares[snake.Item1] = squares[snake.Item2];
            }

            Console.WriteLine(squares[0]);

        }
    }
}

Snakes and Ladders: The Quickest Way Up Java Soluton

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;



class Result {

    /*
     * Complete the 'quickestWayUp' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. 2D_INTEGER_ARRAY ladders
     *  2. 2D_INTEGER_ARRAY snakes
     */
     
    static class QueueObject{
        int pos;
        int step;
        
        QueueObject(int p, int s){
            this.pos = p;
            this.step = s;
        }
        
        int getPos(){
            return this.pos;
        }
        
        int getStep(){
            return this.step;
        }
        
    }

    public static int quickestWayUp(List<List<Integer>> ladders, List<List<Integer>> snakes) {
    // Write your code here
            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.size(); i++) {
                graph[ladders.get(i).get(0)-1] = ladders.get(i).get(1)-1;
            }
            
            for (int i = 0; i < snakes.size(); i++) {
                graph[snakes.get(i).get(0)-1] = snakes.get(i).get(1)-1;
            }
            
            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;
    }

}

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

        int t = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, t).forEach(tItr -> {
            try {
                int n = Integer.parseInt(bufferedReader.readLine().trim());

                List<List<Integer>> ladders = new ArrayList<>();

                IntStream.range(0, n).forEach(i -> {
                    try {
                        ladders.add(
                            Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                                .map(Integer::parseInt)
                                .collect(toList())
                        );
                    } catch (IOException ex) {
                        throw new RuntimeException(ex);
                    }
                });

                int m = Integer.parseInt(bufferedReader.readLine().trim());

                List<List<Integer>> snakes = new ArrayList<>();

                IntStream.range(0, m).forEach(i -> {
                    try {
                        snakes.add(
                            Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                                .map(Integer::parseInt)
                                .collect(toList())
                        );
                    } catch (IOException ex) {
                        throw new RuntimeException(ex);
                    }
                });

                int result = Result.quickestWayUp(ladders, snakes);

                bufferedWriter.write(String.valueOf(result));
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Snakes and Ladders: The Quickest Way Up JavaScript Soluton

var getSpace = function(board, space) {
    var row = Math.floor((space - 1) / 10);
    var col = (space - 1) % 10 ;

    board[row][col].space = space;
    return board[row][col];
};

var atSpace = function(space, piece) {
    return piece.start === space;
};

var getEnd = function(move) {
    return move.end;
};

var createBoard = function() {
    var rows = new Array(10);
    
    for(var i = 0; i < rows.length; i++) {
        rows[i] = new Array(10);
        for(j = 0; j < rows[i].length; j++) {
            rows[i][j] = { visited: false, rolls: 100000000 };
        }
    }
    return rows;
};

var findMin = function(board, test) {
    var spacesToVisit = [1];
    while(spacesToVisit.length > 0) {
        var i = spacesToVisit.shift();
        var space = getSpace(board, i);
        
        if(space.visited) { continue; }
       
        var ladders = test.ladders.filter(atSpace.bind(null, i));
        var snakes = test.snakes.filter(atSpace.bind(null, i));
        var rolls;
        
        if(ladders.length > 0 || snakes.length > 0) {
            space.rolls--; // Move will be automatic without roll
            rolls = [];
        } else {
            rolls = [1,2,3,4,5,6].filter(function(roll) {
                return roll + i <= 100;
            }).map(function(roll) { 
                return { end: roll + i }; 
            });
        }
        
        var connections = ladders.concat(snakes).concat(rolls).map(getEnd).map(function(end) {
            return getSpace(board, end);
        });
        connections.forEach(function(con) {
           if(!con.visited && con.rolls > space.rolls + 1) {
               spacesToVisit.push(con.space);
               con.rolls = space.rolls + 1;
               con.previous = space;
           }
        });
        space.visited = true;
    }
    
    var winSpace = getSpace(board, 100);
    
    return winSpace.visited ? winSpace.rolls : -1;
};

var minRoute = function(test) {
    var board = createBoard();
    var start = getSpace(board, 1);
    start.rolls = 0;
    
    return findMin(board, test);
};

var main = function(testCases) {
    testCases.forEach(function(testCase) {
        console.log(minRoute(testCase)); 
    });
};

function processData(input) {
    var lines = input.split('\n');
    var testCases = [];
    for(var j=1; j < lines.length;) {
        var test = {
            ladders: [],
            snakes: []
        };
        var numLadders = Number.parseInt(lines[j]);
        var snakesStart = j + numLadders + 1;

        var numSnakes = Number.parseInt(lines[snakesStart]);
        var nextTest = snakesStart + numSnakes + 1;

        test.ladders = grabBoardPieces(lines, j, numLadders);
        test.snakes = grabBoardPieces(lines, snakesStart, numSnakes);
        testCases.push(test);
        j = nextTest;
    }
    
    main(testCases);
};

var grabBoardPieces = function(lines, base, numPieces) {
    var pieces = [];
    while(numPieces > 0) {
        var piece = lines[base+numPieces].split(' ').map(function(n) { return Number.parseInt(n); });
        pieces.push({start: piece[0], end: piece[1]});
        numPieces--;
    }
    return pieces;
};

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Snakes and Ladders: The Quickest Way Up Python Soluton

T = int(input())

for t in range(T):
  input()

  [start, finish] = [0, 99]
  graph = [[j for j in range(i+1, min(100, i+7))] for i in range(100)]

  for i in range(2):
  	features = [[int(y)-1 for y in x.split(',')] for x in input().split()]
  	for feature in features:
  		graph[feature[0]] = [feature[1]]

  for feature in features:
    graph[feature[0]] = [feature[1]]

  visited = {start}

  for distance in range(100):
    for v in visited:
      visited = visited.union(graph[v])
    if finish in visited:
      print(distance)
      break
c C# C++ HackerRank Solutions java javascript python

Leave a Reply