HackerRank Red Knight’s Shortest Path problem solution

In this HackerRank Red Knight’s Shortest Path problem solution we have given the coordinates of the starting position of the red knight and the coordinates of the destination, print the minimum number of moves that the red knight has to make in order to reach the destination and after that, print the order of the moves that must be followed to reach the destination in the shortest way. If the destination cannot be reached, print only the word “Impossible”.

Problem solution in Python.

#!/bin/python3

import sys


def printShortestPath(n, i_start, j_start, i_end, j_end):
    #  Print the distance along with the sequence of moves.
    diff_i = i_end - i_start
    diff_j = j_end - j_start
    i = i_start
    j = j_start
    if diff_i % 2 == 1:
        print('Impossible')
        return
    if diff_i % 4 == 0 and diff_j % 2 == 1:
        print('Impossible')
        return
    if diff_i % 4 == 2 and diff_j % 2 == 0:
        print('Impossible')
        return
    moves = []
    while diff_i < 0 and diff_i // -2 > diff_j:
        if j == 0:
            diff_i += 2
            diff_j -= 1
            i -= 2
            j += 1
            moves.append('UR')
            continue
        diff_i += 2
        diff_j += 1
        i -= 2
        j -= 1
        moves.append('UL')
    while diff_i < 0:
        diff_i += 2
        diff_j -= 1
        i -= 2
        j += 1
        moves.append('UR')
    while diff_j > 0 and diff_j > diff_i // 2:
        moves.append('R')
        j += 2
        diff_j -= 2
    while diff_i > 0 and diff_i // -2 < diff_j:
        if j == n - 1:
            diff_i -= 2
            diff_j += 1
            i += 2
            j -= 1
            moves.append('LL')
            continue
        moves.append('LR')
        diff_i -= 2
        diff_j -= 1
        i += 2
        j += 1
    while diff_i > 0:
        diff_i -= 2
        diff_j += 1
        i += 2
        j -= 1
        moves.append('LL')

    if diff_i == 0:
        if diff_j > 0:
            move = diff_j // 2
            moves += ["R"] * move
        else:
            move = -diff_j // 2
            moves += ["L"] * move

    print(len(moves))
    print(' '.join(moves))


if __name__ == "__main__":
    n = int(input().strip())
    i_start, j_start, i_end, j_end = input().strip().split(' ')
    i_start, j_start, i_end, j_end = [int(i_start), int(j_start), int(i_end), int(j_end)]
    printShortestPath(n, i_start, j_start, i_end, j_end)

Problem solution in Java.

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

public class Solution {
    static int INF=(int)1e9;
    static String[] neighborS = {"UL", "UR", "R", "LR", "LL", "L"};
    static int[] neighborI = {-2, -2, 0, 2, 2, 0};
    static int[] neighborJ = {-1, 1, 2, 1, -1, -2};
    
    static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) {
        //  Print the distance along with the sequence of moves.
        Pair[] q = new Pair[n*n];
        int qt=0, qh=0;
        q[qt++]=new Pair(i_start, j_start);
        int[][] dist = new int[n][n];
        Pair[][] prev = new Pair[n][n];
        String[][] prevS = new String[n][n];
        for(int i=0; i<n; ++i)
            Arrays.fill(dist[i], INF);
        dist[i_start][j_start]=0;
        while(qt>qh) {
            Pair p = q[qh++];
            for(int i=0; i<6; ++i) {
                int nI=p.a+neighborI[i], nJ=p.b+neighborJ[i];
                if(nI<0||nI>=n||nJ<0||nJ>=n||dist[nI][nJ]<INF)
                    continue;
                prevS[nI][nJ]=neighborS[i];
                prev[nI][nJ] = new Pair(p.a, p.b);
                dist[nI][nJ]=dist[p.a][p.b]+1;
                q[qt++]=new Pair(nI, nJ);
            }
        }
        if(dist[i_end][j_end]>=INF)
            System.out.println("Impossible");
        else {
            String s="";
            for(Pair p=new Pair(i_end, j_end); prev[p.a][p.b]!=null; p=prev[p.a][p.b])
                s=prevS[p.a][p.b]+" "+s;
            System.out.println(dist[i_end][j_end]+"n"+s);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int i_start = in.nextInt();
        int j_start = in.nextInt();
        int i_end = in.nextInt();
        int j_end = in.nextInt();
        printShortestPath(n, i_start, j_start, i_end, j_end);
        in.close();
    }
    
    static class Pair {
        int a, b;
        Pair(int a, int b) {
            this.a=a;
            this.b=b;
        }
    }
}

Problem solution in C++.

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

using namespace std;

int dx[] = {-1, 1, 2, 1, -1, -2};
int dy[] = {-2, -2, 0, 2, 2, 0};

int from[210][210];
int N;
int yt, xt;
char moveNames[][5] = {"UL", "UR", "R", "LR", "LL", "L"};

queue<int> q;
stack<int> moves;

int main(){
	memset(from, -1, sizeof(from));
	int yf, xf;
	
	scanf("%d", &N);
	scanf("%d %d %d %d", &yf, &xf, &yt, &xt);
	
	q.push(yf*1000 + xf);
	from[yf][xf] = 10;
	
	while(!q.empty()){
		int now = q.front();
		q.pop();
		xf = now % 1000;
		yf = now / 1000;
		if(xf == xt && yf == yt) break;
		
		for(int i=0; i<6; i++){
			int nx = xf + dx[i];
			int ny = yf + dy[i];
			if(nx < 0) continue;
			if(ny < 0) continue;
			if(nx >= N) continue;
			if(ny >= N) continue;
			
			if(from[ny][nx] == -1){
				from[ny][nx] = i;
				q.push(ny*1000 + nx);
			}
		}
	}
	
	if(xf == xt && yf == yt){
		while(from[yf][xf] != 10){
			moves.push(from[yf][xf]);
			int ny = yf - dy[from[yf][xf]];
			int nx = xf - dx[from[yf][xf]];
			yf = ny;
			xf = nx;
		}
		
		printf("%dn", moves.size());
		while(!moves.empty()){
			int mo = moves.top();
			moves.pop();
			printf("%s", moveNames[mo]);
			if(moves.empty()) printf("n");
			else printf(" ");
		}
	}
	else{
		printf("Impossiblen");
	}
	return 0;
}

Problem solution in C.

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

typedef struct  s_action
{
    int         step;
    int         UL;
    int         UR;
    int         R;
    int         LR;
    int         LL;
    int         L;
}               t_action;

void    ft_impossible()
{
    printf("Impossible");
    exit(0);
}

void    init_action(t_action *action)
{
    action->step = 0;
    action->UL = 0;
    action->UR = 0;
    action->R = 0;
    action->LR = 0;
    action->LL = 0;
    action->L = 0;
}
void    UL(int *i_start, int *j_start, t_action *action, int n)
{
    *i_start -= 2;
    *j_start -= 1;
    if (*j_start < 0)
        ft_impossible();
    action->step += 1;
    action->UL += 1;
}

void    UR(int *i_start, int *j_start, t_action *action, int n)
{
    *i_start -= 2;
    *j_start += 1;
    if (*j_start >= n)
        ft_impossible();
    action->step += 1;
    action->UR += 1;
}

void    R(int *j_start, t_action *action, int n)
{
    *j_start += 2;
    if (*j_start >= n)
        ft_impossible();
    action->step += 1;
    action->R += 1;
}

void    LR(int *i_start, int *j_start, t_action *action, int n)
{
    *i_start += 2;
    *j_start += 1;
    if (*j_start >= n)
        ft_impossible();
    action->step += 1;
    action->LR += 1;
}

void    LL(int *i_start, int *j_start, t_action *action, int n)
{
    *i_start += 2;
    *j_start -= 1;
    if (*j_start < 0)
        ft_impossible();
    action->step += 1;
    action->LL += 1;
}

void    L(int *j_start, t_action *action, int n)
{
    *j_start -= 2;
    if (*j_start < 0)
        ft_impossible();
    action->step += 1;
    action->L += 1;
}

void    print_action(t_action action)
{
    printf("%dn", action.step);
    while (action.UL--)
        printf("UL ");
    while (action.UR--)
        printf("UR ");
    while (action.R--)
        printf("R ");
    while (action.LR--)
        printf("LR ");
    while (action.LL--)
        printf("LL ");
    while (action.L--)
        printf("L ");
}

void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) {
    //  Print the distance along with the sequence of moves.
    t_action    action;
    int         vertical;
    int         down_move;
   
    init_action(&action);
    vertical = (i_end - i_start > 0) ? i_end - i_start : i_start - i_end;
    if (vertical % 2 == 1)
        ft_impossible();
    while (i_end < i_start)
    {
        if (j_end <= j_start)
            UL(&i_start, &j_start, &action, n);
        else
            UR(&i_start, &j_start, &action, n);
    }
    down_move = vertical / 2 - action.step;
    while (j_end - down_move > j_start)
        R(&j_start, &action, n);
    while (i_end > i_start)
    {
        if (j_end >= j_start)
            LR(&i_start, &j_start, &action, n);
        else
            LL(&i_start, &j_start, &action, n);
    }
    while (j_end < j_start)
        L(&j_start, &action, n);
    if (j_end != j_start)
        ft_impossible();
    print_action(action);
}

int main() {
    int n;
    scanf("%i", &n);
    int i_start;
    int j_start;
    int i_end;
    int j_end;
    scanf("%i %i %i %i", &i_start, &j_start, &i_end, &j_end);
    printShortestPath(n, i_start, j_start, i_end, j_end);
    return 0;
}