In this HackerRank Castle on the Grid Interview preparation kit problem you have Given a grid, a start, and a goal, determine the minimum number of moves to get to the goal.


HackerRank Castle on the Grid Interview preparation kit solution


Problem solution in Python programming.

import numbers
import math
from collections import namedtuple,deque
class point(namedtuple("point", "i j")):
    def __eq__(self,o):
        return self.i == o.i and self.j == o.j
    def __ne__(self, o):
        return self.i != o.i or self.j != o.j
    def __lt__(self, o):
        return self.i < o.i or self.j < o.j
    def __gt__(self, o):
        return self.i > o.i or self.j > o.j
    def __le__(self, o):
        return self.i <= o.i or self.j <= o.j
    def __ge__(self, o):
        return self.i >= o.i or self.j >= o.j
    def __rshift__(self,o):
        return self.i >= o.i and self.j >= o.j
    def __lshift__(self,o):
        return self.i <= o.i and self.j <= o.j
    def __hash__(self):
        return hash((self.i, self.j))
    def __repr__(self):
        return 'p(%r, %r)' % self
    def __add__(self,o):
        if isinstance(o, point):
            return point.__new__(point,self.i+o.i,self.j+o.j)
        if isinstance(o, numbers.Number):
            return point.__new__(point,self.i+o,self.j+o)
        return NotImplemented
    def __iadd__(self,o):
        return self.__add__(o)
    def __sub__(self,o):
        if isinstance(o, point):
            return point.__new__(point,self.i-o.i,self.j-o.j)
        if isinstance(o, numbers.Number):
            return point.__new__(point,self.i-o,self.j-o)
        return NotImplemented
    def inbound(self,a,b=None):
        if b is None:
            a,b = point(0,0),a
        im,ix = sorted([a.i,b.i])
        jm,jx = sorted([a.j,b.j])
        return im <= self.i and self.i < ix and jm <= self.j and self.j < jx
    def distance(self,o):
        return abs(self.i-o.i)+abs(self.j-o.j)
        #return math.sqrt((self.i-o.i)**2+(self.j-o.j)**2)
    def __isub__(self,o):
        return self.__sub__(o)
    def __neg__(self):
        return point.__new__(point,-self.i,-self.j)
    def I():
        return point.__new__(point,1,0)
    def J():
        return point.__new__(point,0,1)

class grid(list):
    def __getitem__(self, *args, **kwargs):
        if isinstance(args[0], point):
            return self[args[0].i][args[0].j]
        else:
            return list.__getitem__(self, *args, **kwargs)
    def __setitem__(self, *args, **kwargs):
        if isinstance(args[0], point):
            self[args[0].i][args[0].j] = args[1]
        else:
            return list.__setitem__(self, *args, **kwargs)
    def __repr__(self):
        return "\n".join(["".join(map(lambda x:str(x)[-1],a)) for a in self])

around = (-point.I(),-point.J(),point.J(),point.I())
n = int(input())
b = grid([list(input()) for _ in range(n)])
_ = list(map(int,input().split()))
p = point(_[0],_[1])
f = point(_[2],_[3])
b[p] = "#"
b[f] = "E"
q = deque([(p,0)])



vg = grid([[False for _ in range(len(b[0]))] for _ in range(len(b))])
while len(q):
    
    c,d = q.popleft()

    vg[c] = True
    #print(c,b[c.i][c.j])
    if c == f:
        break
    if b[c] == ".":
        b[c] = "="

    for di in around:
        pt = c
        while True:
            pt += di
            if pt.inbound(point(0,0) ,point(len(b),len(b[0]))) and (b[pt] == "." or b[pt] == "E") :
                q.append((pt,d+1))
                vg[pt] = True
                if b[pt] == ".":
                    b[pt] = d+1
            else:
                break
    
    #print(c,ar)
    #print(q)

#print(b)    
print(d)


Problem solution in Java Programming.

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

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        scanner.useDelimiter("\n");
        int n = scanner.nextInt();

        char[][] grid = new char[n][n];

        for (int i = 0; i < n; i++) {
            String str = scanner.next();
            grid[i] = str.toCharArray();
        }

        String coords = scanner.next();
        String[] split = coords.split(" ");
        XY start = new XY(Integer.parseInt(split[0]), Integer.parseInt(split[1]));
        XY end = new XY(Integer.parseInt(split[2]), Integer.parseInt(split[3]));

        Set<XY> visited = new HashSet<XY>();

        System.out.println(minSteps(grid, start, end, visited));
    }

    private static int minSteps(char[][] grid, XY curr, XY end, Set<XY> visited) {
        Queue<XY> queue = new LinkedList<XY>();
        queue.add(curr);
        visited.add(curr);

        Queue<Integer> step = new LinkedList<Integer>();
        step.add(0);

        while (!queue.isEmpty()) {
            XY nextXY = queue.remove();
            int hop = step.remove();

            if (nextXY.equals(end)) return hop;

            List<XY> next = getNext(grid, nextXY, visited);
            visited.addAll(next);
            queue.addAll(next);

            for (int i = 0; i < next.size(); i++) {
                step.add(hop + 1);
            }
        }

        return Integer.MAX_VALUE;
    }

    private static List<XY> getNext(char[][] grid, XY curr, Set<XY> visited) {
        List<XY> next = new ArrayList<XY>();

        if (curr.dir == null || curr.dir == Dir.Y) {
            int x = curr.x;
            for (int i = x - 1; i >= 0; i--) {
                if (grid[i][curr.y] == 'X') break;

                final XY xy = new XY(i, curr.y, Dir.X);
                if (!visited.contains(xy)) next.add(xy);
            }

            for (int i = x + 1; i < grid.length; i++) {
                if (grid[i][curr.y] == 'X') break;

                final XY xy = new XY(i, curr.y, Dir.X);
                if (!visited.contains(xy)) next.add(xy);
            }
        }

        if (curr.dir == null || curr.dir == Dir.X) {
            int y = curr.y;

            for (int i = y - 1; i >= 0; i--) {
                if (grid[curr.x][i] == 'X') break;

                final XY xy = new XY(curr.x, i, Dir.Y);
                if (!visited.contains(xy)) next.add(xy);
            }

            for (int i = y + 1; i < grid.length; i++) {
                if (grid[curr.x][i] == 'X') break;

                final XY xy = new XY(curr.x, i, Dir.Y);
                if (!visited.contains(xy)) next.add(xy);
            }
        }

        return next;
    }


    private static class XY {
        int x, y;
        Dir dir;


        public XY(int x, int y) {
            this.x = x;
            this.y = y;
            dir = null;
        }

        public XY(int x, int y, Dir dir) {
            this.x = x;
            this.y = y;
            this.dir = dir;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            XY xy = (XY) o;
            return x == xy.x && y == xy.y;

        }

        @Override
        public int hashCode() {
            return 31 * x + y;
        }

        @Override
        public String toString() {
            return "XY{" +
                    "x=" + x +
                    ", y=" + y +
                    ", dir=" + dir +
                    '}';
        }
    }

    private enum Dir {
        X, Y;
    }
}


Problem solution in C++ programming.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <deque>
using namespace std;

// -1 for break; 0 for continue; 1 for OK
int func(vector<vector<char>>& vlist, deque<int>& pst, vector<vector<int>>& visited, int tx, int ty, int x1, int y1)
 {
    int n = vlist.size();
    
    if(tx < 0 || tx >= n || ty < 0 || ty >= n)
        return -1;
    
    if(vlist[tx][ty] == 'X')
          return -1;

    if(visited[tx][ty] == 1)
        return 0;
    visited[tx][ty] = 1;
    
    pst.push_back(tx  + ty *n);
    if(tx == x1 && ty == y1)
        return 1;
    
    return 0;
}   

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
   
    int n;
    cin >> n;
    

    vector<vector<char>> vlist;
    vector<vector<int>> vvst;
    vlist.resize(n);
    vvst.resize(n);
    
    for(int i = 0; i < n; i ++)
    {
        for(int j =0; j < n; j ++)
        {
            char c;
            cin >> c;
            vlist[i].push_back(c);
            vvst[i].push_back(0);
        }    
    }    
    
    int x0, y0, x1, y1;
    cin >> x0 >> y0 >> x1 >> y1;  
    
    deque<int> pst;
    pst.push_back(x0 + n * y0);
    int level = 0;
    
    bool found = false;
    deque<int> tempst;
    
    while(true)
    {
        if(pst.empty())
        {
            pst = tempst;
            tempst.clear();
         }
        if(pst.empty() || found)
            break;
        level ++;
        while(!pst.empty())
        {
            if(found)
                break;          

            int v = pst.front();
            pst.pop_front();

            int tx = v % n;
            int ty = v / n;

            for(int k = tx - 1; k >=0; k --)
            {
                int rn = func(vlist, tempst, vvst, k, ty, x1, y1);
                if(rn == -1)
                    break;
                else if(rn == 1)
                 {
                    found = true;
                    break;
                  }               
            }
             for(int k = tx + 1; k < n; k ++)
            {
                int rn = func(vlist, tempst, vvst, k, ty, x1, y1);
                if(rn == -1)
                    break;
                else if(rn == 1)
                 {
                    found = true;
                    break;
                  }               
            }

            for(int k = ty - 1; k >=0; k --)
            {
                int rn = func(vlist, tempst, vvst, tx, k, x1, y1);
                if(rn == -1)
                    break;
                else if(rn == 1)
                 {
                    found = true;
                    break;
                  }               
            }
            for(int k = ty + 1; k < n; k ++)
            {
                int rn = func(vlist, tempst, vvst, tx, k, x1, y1);
                if(rn == -1)
                    break;
                else if(rn == 1)
                 {
                    found = true;
                    break;
                  }               
            }
        }    
    }
    cout << level << endl;
    return 0;
}


Problem solution in C programming.

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

typedef struct {
    int x;
    int y;
} Gridpoint;

int insertGrid(Gridpoint *queue, int x, int y, int wr_ptr) {
    queue[wr_ptr].x = x;
    queue[wr_ptr].y = y;
    wr_ptr += 1;
    return wr_ptr;
}

int MovePath(int **grid, int x, int y, int N, int wr_ptr, Gridpoint *queue) {
    int step = grid[x][y] + 1;
    //printf("(%d, %d). step = %d\n", x, y, step);
    

    // move up
    for (int i=x-1;i>=0;i--) {
        if (grid[i][y] == -1) {
            break;
        }
        if (grid[i][y] == 0) {
            grid[i][y] = step;
            wr_ptr = insertGrid(queue, i, y, wr_ptr);
        }
    }

    // move down
    for (int i=x+1;i<N;i++) {
        if (grid[i][y] == -1) {
            break;
        }
        if (grid[i][y] == 0) {
            grid[i][y] = step;
            wr_ptr = insertGrid(queue, i, y, wr_ptr);
        }
    }    
    // move right
    for (int i=y+1;i<N;i++) {
        if (grid[x][i] == -1) {
            break;
        }
        if (grid[x][i] == 0) {
            grid[x][i] = step;
            wr_ptr = insertGrid(queue, x, i, wr_ptr);
        }
    }       
    // move left
    for (int i=y-1;i>=0;i--) {
        if (grid[x][i] == -1) {
            break;
        }
        if (grid[x][i] == 0) {
            grid[x][i] = step;
            wr_ptr = insertGrid(queue, x, i, wr_ptr);
        }
    }    

    return wr_ptr;
}
int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    int N;
    scanf("%d\n", &N);
    int **grid = (int **)malloc(sizeof(int *)*N);
    char tmp;
    for (int i = 0;i<N;i++) {
        grid[i] = (int *)malloc(sizeof(int)*N);
        for (int j = 0;j<N;j++) {
            scanf("%c\n", &tmp);
            if (tmp == 'X') {
                grid[i][j] = -1;
            } else {
                grid[i][j] = 0;
            }
        }
    }
    
    int cur_x, cur_y, end_x, end_y;
    scanf("%d %d %d %d", &cur_x, &cur_y, &end_x, &end_y);
    
    
    Gridpoint *queue = (Gridpoint *)malloc(sizeof(Gridpoint) *100);
    int wr_ptr = 0;
    int rd_ptr = 0;

    //printf("(%d, %d) (%d, %d)\n", cur_x, cur_y, end_x, end_y);
    // BFS iteratively on all nodes
    while (rd_ptr <= wr_ptr) {
        wr_ptr = MovePath(grid, cur_x, cur_y, N, wr_ptr, queue);
        //printf("wr_ptr = %d\n", wr_ptr);
        cur_x = queue[rd_ptr].x;
        cur_y = queue[rd_ptr].y;
        rd_ptr++;
        //printf("(%d, %d). rd_ptr = %d\n", cur_x, cur_y, rd_ptr);
    }
    
    printf("%d", grid[end_x][end_y]);
    return 0;
}


Problem solution in JavaScript programming.

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

// Complete the minimumMoves function below.
function minimumMoves(grid, startRow, startCol, goalRow, goalCol) {
    // initialize a 2d matrix to track visited nodes and its parents
    const visited = Array(grid.length).fill(false).map(_ => Array(grid[0].length).fill(false).map(_ => ({visited: false, parent: null})));

    visited[startRow][startCol].visited = true;
    console.log(visited);


    const rowQueue = [startRow];
    const colQueue = [startCol];

    let moves = 0;
    let parent = null;
    while  (rowQueue.length !== 0) {
        const row = rowQueue.shift();
        const col = colQueue.shift();
        if (row === goalRow && col === goalCol) {
            parent = visited[row][col].parent;
            break;
        }
        exploreNeighbours(row, col);
    }

    console.log(visited);
    while (parent !== null) {
        console.log(parent);
        moves++;
        parent = visited[parent[0]][parent[1]].parent;
    }

    return moves;

    function exploreNeighbours(row, col) {
        // north, south, east, west directon vectors
        const dc = [0, 0, -1, +1];
        const dr = [-1, +1, 0, 0];

        for (let i = 0; i < 4; i++) {
            let cc = col;
            let rr = row;
            while (true) {
                cc += dc[i];
                rr += dr[i];

                // stop at out of bounds
                if (cc < 0 || rr < 0) break;
                if (rr > grid.length - 1 || cc > grid[0].length - 1) break;

                // stop visited or blocked cells
                if (visited[rr][cc].visited) continue;
                if (grid[rr][cc] === 'X') break;

                colQueue.push(cc);
                rowQueue.push(rr);
                visited[rr][cc].visited = true;
                visited[rr][cc].parent = [row, col]; 
            }
        }
    }
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const n = parseInt(readLine(), 10);

    let grid = [];

    for (let i = 0; i < n; i++) {
        const gridItem = readLine();
        grid.push(gridItem);
    }

    const startXStartY = readLine().split(' ');

    const startX = parseInt(startXStartY[0], 10);

    const startY = parseInt(startXStartY[1], 10);

    const goalX = parseInt(startXStartY[2], 10);

    const goalY = parseInt(startXStartY[3], 10);

    const result = minimumMoves(grid, startX, startY, goalX, goalY);

    ws.write(result + '\n');

    ws.end();
}