This post talks about the coding challenge, Castle on the Grid, on HackerRank. For those that don’t know, HackerRank provides programming puzzles of varying difficulty in a wide range of areas including data structures, algorithms and machine learning. You can solve these problems in (almost) any chosen language, and discuss the problems with other members in forums. I would highly recommend it for learning topics, becoming more familiar with a language, improving your programming problem solving skills or simply to have fun.

Okay, so lets take a look at the problem. Simply stated: there is a n x n grid, with a castle (think chess piece) on one cell (equivalent to a square on a chess board). There are a number of forbidden cells that the castle can’t move on or over. There is a goal cell. You must return the minimum number of moves it would take for the castle to get to the goal, whilst avoiding any forbidden cells. Oh, and the castle moves like a castle moves in chess – any number of squares at a time either up, down, left or right.

So in the example below, where the castle is c, forbidden cells are x, and the goal cell is g, the minimum number of moves would be 3, as illustrated.

And in this other example below, it would be 4.

The inputs you receive are: integer, *n*, denoting the height/width of the grid; a size *n *array of strings, *grid* denoting the grid (e.g. in our second example grid[0] would be “….” and grid[1] would be “…X”); and finally, 4 integers representing the (x,y) coordinates of the castle and goal cell respectively.

If you like, have a think about how you might go about solving this problem before reading on.

It took me a while to figure this one out, and I really enjoyed the problem. It was in the data structures, queue category so I figured I better use some kind of queue. Similar to Dijkstra’s algorithm, for finding the minimum distance between nodes in a graph, we can imagine the grid as a graph, where each cell is connected to all others that can be reached from it in a single move. From this, we can calculate the minimum number of moves to each cell from the starting castle cell, giving us the minimum number of moves to the goal cell. Of course we aren’t supplied with a graph of connected cells so we will have to create it on the fly. Easy, right?

*Now to implement our solution…*

The main algorithm is in the method *minimumMoves(), *and we are provided with a skeleton for this method – it is called from *main().* Here, we first create a 2D int array of size *n *x *n* called* **minMovesToCell* which will hold the minimum number of moves required to reach each cell. We initialise each cell in *minMovesToCell* with Integer.MAX_VALUE, and any forbidden cells are set to -1. The starting cell of the castle is set to 0 as we are already here. We also create another 2D int array the same size called *settledCells* with values set to 0. If the minimum number of moves to a cell has been found, we change its respective value in *settledCells* to 1, this is helpful when we encounter cells we have already dealt with.

Now to use that queue; we create a queue in the form of a linked list, *cellsToCheck*, and add our starting castle cell to it. Bear in mind that in our algorithm, we don’t need to use a priority queue (as we would in the standard Dijkstra’s) as the distance between connected nodes is always 1, because if they are connected they can be reached in one move. While there are cells to be checked, we remove them from the front of *cellsToCheck *and update *settledCells *accordingly. We then find any cells that can be reached from this cell using the method *getCellsThatCanBeReachedFrom(Cell)*, and update the minimum values for each of them in *minMovesToCell. *Any unsettled cells that can be reached are added to *cellsToCheck *and this continues until the minimum number of moves to every cell has been determined. Finally, we simply return the minimum number of moves to the goal cell using *getMinMovesTo(goalCell).*

The code is below; I’ve tried to make it as self explanatory as possible.

Anyway, I hope you’ve enjoyed the read, and if you’re a programmer and haven’t had a look at HackerRank before, give it a shot, it’s a lot of fun.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 |
import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; class Cell { int x; int y; Cell(int x, int y) { this.x = x; this.y = y; } } public class Solution { static int gridSize; static int[][] minMovesToCell; static int[][] settledCells; public static int minimumMoves(String[] grid, int startX, int startY, int goalX, int goalY) { Cell startCell = new Cell(startX, startY); Cell goalCell = new Cell(goalX, goalY); createMinMovesToCellsGrid(grid); setMinMovesTo(startCell, 0); LinkedList<Cell> cellsToCheck = new LinkedList<>(); cellsToCheck.add(startCell); while (cellsToCheck.size() > 0) { Cell cellToCheck = cellsToCheck.remove(); addToSettled(cellToCheck); cellsToCheck.addAll(getCellsThatCanBeReachedFrom(cellToCheck)); } return getMinMovesTo(goalCell); } public static void addToSettled(Cell cell) { settledCells[cell.x][cell.y] = 1; } public static int getMinMovesTo(Cell cell) { return minMovesToCell[cell.x][cell.y]; } public static void setMinMovesTo(Cell cell, int minMoves) { minMovesToCell[cell.x][cell.y] = minMoves; } public static boolean isForbidden(Cell cell, String[] grid) { if (grid[cell.x].charAt(cell.y) == 'X') return true; else return false; } public static boolean isForbidden(Cell cell) { if (getMinMovesTo(cell) == -1) return true; else return false; } public static boolean isSettled(Cell cell) { if (settledCells[cell.x][cell.y] == 1) return true; else return false; } public static boolean isOutsideGrid(Cell cell) { if (cell.x >= gridSize || cell.x < 0 || cell.y >= gridSize || cell.y < 0) return true; else return false; } public static void createMinMovesToCellsGrid(String[] grid) { minMovesToCell = new int[gridSize][gridSize]; for (int x=0; x<gridSize; x++) { for (int y=0; y<gridSize; y++) { Cell currentCell = new Cell(x, y); if (isForbidden(currentCell, grid)) setMinMovesTo(currentCell, -1); else setMinMovesTo(currentCell, Integer.MAX_VALUE); } } } public static LinkedList<Cell> getCellsThatCanBeReachedFrom(Cell startCell) { LinkedList<Cell> cellsThatCanBeReached = new LinkedList<>(); int[][] directions = { {1,0}, {0,1}, {-1,0}, {0,-1} }; for (int direction=0; direction<=3; direction++){ int distance = 1; while(true){ Cell cellToCheck = new Cell(startCell.x + (directions[direction][0] * distance), startCell.y + (directions[direction][1] * distance)); if (isOutsideGrid(cellToCheck) || isForbidden(cellToCheck) || isSettled(cellToCheck)) { break; } int numOfMovesToCell = getMinMovesTo(startCell) + 1; if (numOfMovesToCell < getMinMovesTo(cellToCheck)) { setMinMovesTo(cellToCheck, numOfMovesToCell); cellsThatCanBeReached.add(cellToCheck); } distance++; } } return cellsThatCanBeReached; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); String[] grid = new String[n]; for(int grid_i = 0; grid_i < n; grid_i++){ grid[grid_i] = in.next(); } int startX = in.nextInt(); int startY = in.nextInt(); int goalX = in.nextInt(); int goalY = in.nextInt(); in.close(); gridSize = grid.length; settledCells = new int[gridSize][gridSize]; int result = minimumMoves(grid, startX, startY, goalX, goalY); System.out.println(result); } } |