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?"

HackerRank Snakes and Ladders: The Quickest Way Up problem solution


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')
    

{"mode":"full","isActive":false}


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;
    }
}

{"mode":"full","isActive":false}


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;
}

{"mode":"full","isActive":false}


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 %d\n", 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("%d\n", Trace(cells, 100));
    }
    return 0;
}

{"mode":"full","isActive":false}