HackerRank Castle on the Grid problem solution

In this HackerRank Castle on the Grid problem solution, You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal.

Function Description
Complete the minimumMoves function in the editor.

minimumMoves has the following parameter(s):

• string grid[n]: an array of strings that represent the rows of the grid
• int startX: starting X coordinate
• int startY: starting Y coordinate
• int goalX: ending X coordinate
• int goalY: ending Y coordinate

Returns

• int: the minimum moves to reach the goal

HackerRank Castle on the Grid problem solution in Python.

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)

Castle on the Grid problem solution in Java.

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 = %dn", 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("%dn", &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("%cn", &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 = %dn", wr_ptr);
        cur_x = queue[rd_ptr].x;
        cur_y = queue[rd_ptr].y;
        rd_ptr++;
        //printf("(%d, %d). rd_ptr = %dn", 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();
}