BFS, Dijkstra’s and a chess board

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 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 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.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.