HackerRank Snakes and Ladders: The Quickest Way Up problem solution

In this 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?”

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.

HackerRank Snakes and Ladders: The Quickest Way Up problem solution in Python.

test_cases = int(input().strip())
for test_case in range(test_cases):
    snake_count = int(input().strip())
    shortcuts = {}
    for snake in range(snake_count):
        src, dst = [int(item)-1 for item in input().strip().split()]
        shortcuts[src] = dst
    ladder_count = int(input().strip())
    for ladder in range(ladder_count):
        src, dst = [int(item)-1 for item in input().strip().split()]
        shortcuts[src] = dst
    
    board = [0] + [None] * 99
    dst = 0
    while dst < 99:
        dst += 1
        moves = board[dst]
        sources = [cell for cell in board[max(dst-6, 0):dst] if cell is not None]
        if not sources:
            continue
        moves = min(sources) + 1
        new_dst = shortcuts.get(dst, dst)
        if board[new_dst] is None or moves < board[new_dst]:
            board[new_dst] = moves
            dst = min(dst, new_dst)

    print(board[-1] if board[-1] is not None else '-1')
    

Snakes and Ladders: The Quickest Way Up problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt();
        
        int M,N;
        for (int i = 0; i < T; i++){
            N = sc.nextInt();
            
            HashMap<Integer,Integer> ladders = new HashMap<>();
            int start, end;
            for (int j = 0; j < N; j++){
                start = sc.nextInt();
                end = sc.nextInt();
                ladders.put(start,end);
            }
            
            HashMap<Integer,Integer> snakes = new HashMap<>();
            M = sc.nextInt();
            for (int j = 0; j < M; j++){
                start = sc.nextInt();
                end = sc.nextInt();
                snakes.put(start, end);
            }
            
            int[] distances = new int[100];
            for (int j = 0; j < 100; j++){
                distances[j] = Integer.MAX_VALUE;
            }
            
            getShortestPathToEnd(getGameGraph(ladders, snakes), 1, distances, 0);
            
            System.out.println(distances[99] == Integer.MAX_VALUE ? -1 : distances[99]);
        }
    }
    
    private static int getShortestPathToEnd(HashMap<Integer,HashSet<Integer>> graph, int start, int[] distances, int depth){
       if (distances[start-1] > depth){
           distances[start-1] = depth;
       }
       else{
           return 0;
       }
        
       if (!graph.get(start).isEmpty()){
           for (Integer child : graph.get(start)){
               //System.out.println(start + " - " + child);
               getShortestPathToEnd(graph, child, distances, depth + 1);
           }
            
           return 0;
       }
       else{
           return -1;
       }
    }
    
    private static HashMap<Integer,HashSet<Integer>> getGameGraph(HashMap<Integer,Integer> ladders, HashMap<Integer,Integer> snakes){
        HashMap<Integer, HashSet<Integer>> graph = new HashMap<>();
        
        HashSet<Integer> neighbours;
        for (int i = 1; i <= 100; i++){
            neighbours = new HashSet<Integer>();
            for (int j = 1; j <= 6 && (i + j <= 100); j++){
                if(ladders.containsKey(i+j)){
                    neighbours.add(ladders.get(i+j));
                }
                else if (snakes.containsKey(i+j)){
                    neighbours.add(snakes.get(i+j));
                }
                else{
                    neighbours.add(i+j);
                }
            }
            graph.put(i, neighbours);
        }
        
        return graph;
    }
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
    int testNum;
    int distanceArray[110][110];
    cin>>testNum;
    for(int i = 0; i < testNum; ++i){
        memset(distanceArray, -1, sizeof(distanceArray));
        //construct the board
        int ladder, snake;
        scanf("%d,%d", &ladder, &snake);
        int start, end;
        for(int j = 0; j < ladder; ++j){
            scanf("%d,%d", &start, &end);
            distanceArray[start][end] = 0;
        }
        for(int j = 0; j < snake; ++j){
            scanf("%d,%d", &start, &end);
            distanceArray[start][end] = 0;
        }
        for(int p = 1; p <= 100; ++p){
            for(int q = 1; q <= 100; ++q){
                for(int k = 1; k <= 100; ++k){
                    if(distanceArray[p][k] == -1 && k > p){
                        distanceArray[p][k] = (k - p - 1) / 6 + 1;
                    }
                    if(distanceArray[k][q] == -1 &&  q > k){
                        distanceArray[k][q] = (q - k - 1) / 6 + 1;
                    }
                    if(distanceArray[p][k] >= 0 && distanceArray[k][q] >= 0){
                        if(distanceArray[p][q] == -1 || distanceArray[p][q] > distanceArray[p][k] + distanceArray[k][q] ){
                           distanceArray[p][q] = distanceArray[p][k] + distanceArray[k][q];
                        }
                    }
                }
            }
        }
        cout<<distanceArray[1][100]<<endl;
    }
    return 0;
}

Problem solution in C.

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

struct Cell
{
    int cost;
    int visited;
    int moves[6];
};

void Init(struct Cell *cells, int num)
{
    for (int i = 0; i < num; i++)
    {
        for (int j = 1; j <= 6; j++)
        {
            int move = i + j;
            cells[i].moves[j - 1] = (move >= 100) ? -1 : move; 
        }
        cells[i].visited = 0;
        cells[i].cost = -1;
    }
    cells[0].cost = 0;
}

void AddJump(struct Cell *cells, int from, int to)
{
    int start = from - 6;
    for (int i = start; i < from; i++)
    {
        if (i >= 0)
        {
            cells[i].moves[from - i - 1] = to;
            //printf("From %d with roll %d jump to %dn", i, from - i, to);
        }
    }
}

int FindNext(struct Cell *cells, int num)
{
	int next = -1, cost = -1;
	for (int i = 0; i < num; i++)
	{
		if ((cells[i].visited == 0) && 
			(cells[i].cost >= 0) && 
			(cost == -1 || cells[i].cost < cost))
		{
			cost = cells[i].cost;
			next = i;
		}
	}
	return next;
}

int Trace(struct Cell *cells, int num)
{
	int current = -1;
	while ((current = FindNext(cells, num)) != -1)
	{
		for (int j = 0; j < 6; j++)
		{
			int n = cells[current].moves[j];
			if (n >= 0 && cells[n].visited == 0)
			{
				int cost = cells[current].cost + 1;
				if (cells[n].cost == -1 || cost < cells[n].cost)
				{
					cells[n].cost = cost;
				}
			}
		}
		cells[current].visited = 1;
	}
	return cells[num - 1].cost;
}

int main() 
{
    int total = 0;
    struct Cell cells[100];
    scanf("%d", &total);
    for (int i = 0; i < total; i++)
    {
        int jumps = 0;
        Init(cells, 100);
        scanf("%d", &jumps);
        for (int j = 0; j < jumps; j++)
        {
            int from, to;
            scanf("%d %d", &from, &to);
            AddJump(cells, from - 1, to - 1);
        }
        scanf("%d", &jumps);
        for (int j = 0; j < jumps; j++)
        {
            int from, to;
            scanf("%d %d", &from, &to);
            AddJump(cells, from - 1, to - 1);
        }
        printf("%dn", Trace(cells, 100));
    }
    return 0;
}