So I’ve decided to take off some rust of my algorithmic
skills the other day. And started to practice with codility. As a word of remark
, I really hate Codility , it makes me feel stupid J .
Nevertheless , as I progressed through a horror of brain
teasers , I’ve encounter a problem that took me quite a while to solve.
After a google search I've realized that even though problem has been addressed several time there is no ready to use solution.Even
though every computer science student should be able to solve this problem
within a reasonable time , I found it difficult. So that is why after finally
solving it , I decided to share my solution with the community.
Disclaimer !
I do not claim this solution to be the best or
the most efficient , neither I am taking any legal responsibility for people
using it in their own purposes.But yeah , feel free to use it on your own risk.
Problem Definition :
Given an infinite NxN chessboard , find a number of turns required for a knight to reach a destination square knowing that he is starting his path form the origin (0,0).
Example :
What is the minimal amount of turns it will take for a Knight to reach (0,2) ?
Answer :
He will move from (0,0) to (2,1) , and then from (2,1) to (0,2).
Bonus objective :
Print a shortest path from the origin to destination.
So first of all I must say that my solution can be found here .
That's all :)Let me know what you think , and if I have mistakes or typos don't hesitate to notify me ;)
Print a shortest path from the origin to destination.
So first of all I must say that my solution can be found here .
Being a Java guy , of course I’ve implemented it as plain
java console application.
My approach in 3 steps :
- Imagine chessboard as a graph . Each square is a node . Each legit knight move is an edge.
- Create an adjacency list starting from a root node (0,0).
- Use BFS algorithm to find a shortest path from origin node to destination node.
Step 1
Nothing really complicated. We will look at the chessboard :
Imagine that the left most bottom white square is an origin of a cartesian plane . As we know , in cartesian plane we have 2 axises : x and y. X positive direction is right and Y positive direction is up.
We will give each square a unique index representing it on cartesian plane . Index will consist of simply x and y coordinates in cartesian plane. Like this : (x,y).
Hence , we will label our very first node in the chess graph (root node) a "(0,0)".
In that manner we will have 36 squares (8x8 chess board) labeled from (x=0,y=0) to (x=7,y=7).
Note : Solution provided in this post is not limited to standard 36 squares size .
Now if each square is a node of a graph , we need also define edges that connect those nodes.
We will start from a root node (0,0) and try to identify all squares our Knight chess piece can reach within one turn. As a matter of fact only 2 squares are reachable (1,2) and (2,1). We will take each reachable square and create an edge between our root node to the reachable square.Something like this diagram :
*
(0,0)
/ \
(1,2) (2,1)
In such manner we will go over all squares in our field and try to identify all other reachable squares within one turn by our knight. At the end each node will have a label and associated list of nearest nodes that can be reachable within one turn away from it.
Step 2
Now that is rather simple step too. In fact I've explained it already in previous step. For each node in our graph we need to store list of reachable nodes. That list is actually an adjacency list.
Step 3
Now when we can define our problem as a "Graph search problem" , we are opening a way to plethora of classic solutions. As a simplest of all , lets focus on BFS algorithm . This is one of many other algorithms that provided a graph and a destination node , can return us a shortest path .
Now as soon as you understand my approach , the solution might seem easy. This is were many of nifty details can ruin your day. The exact implementation of BFS algorithm can vary and should be tailored to your needs. Not to forget that we need to build an adjacency list dynamically , which can prove also to be tedious. But no worries , I've got you covered :)
Let's just dive right in and see the code!
/**
* Created by yan.braslavski on 1/24/16.
*
* Represents a graph node
*/
public class Vertex {
private final int mX;
private final int mY;
private String mName;
private boolean visited;
private LinkedList<Vertex> mAdjVertices = new LinkedList<>();
public Vertex(int x, int y) {
mName = "(" + x + "," + y + ")";
mX = x;
mY = y;
}
@Override
public String toString() {
return mName;
}
public int getX() {
return mX;
}
public int getY() {
return mY;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Vertex vertex = (Vertex) o;
if (mX != vertex.mX) return false;
return mY == vertex.mY;
}
@Override
public int hashCode() {
int result = mX;
result = 31 * result + mY;
return result;
}
public LinkedList<Vertex> getAdjVertices() {
return mAdjVertices;
}
public String getName() {
return mName;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public void addAdjVertex(Vertex v) {
mAdjVertices.add(v);
}
}
*********************************************************************************
/**
* Created by yan.braslavski on 1/24/16.
*
* To have some degree of freedom I've encapsulated some problem related
* conditions in order to scale the problem with ease.
*/
public class ProblemConditions {
private final int mSizeOfBoardNxN;
private final int mNearestMove;
private final int mFareMostMove;
/**
* When Knight moves , he moves 2 squares and then 1 square perpendicularly.
* To generify this , I am saying it moves a "big" distance and then smaller distance perpendicularly.
* @param sizeOfBoardNxN standard board is 8x8 , but yours can be different
* @param nearestMove the smaller part of knight step
* @param fareMostMove the bigger part of knight step
*/
public ProblemConditions(int sizeOfBoardNxN, int nearestMove, int fareMostMove) {
mSizeOfBoardNxN = sizeOfBoardNxN;
mNearestMove = nearestMove;
mFareMostMove = fareMostMove;
}
/**
* @return true if the position within bounds of chessboard
*/
public boolean isPositionOnChessBoard(int x,int y) {
return (x <= mSizeOfBoardNxN && y <= mSizeOfBoardNxN
&& x >= 0 && y >= 0);
}
public int getFareMostMove() {
return mFareMostMove;
}
public int getNearestMove() {
return mNearestMove;
}
public int getChessBoardSize() {
return mSizeOfBoardNxN;
}
}
*********************************************************************************
/**
* Created by yan.braslavski on 1/24/16.
*
* Algorithm encapsulated into a class , for easier interchangeability.
*/
public class BfsAlgorithm {
/**
* Running multi purpose bfs algorithm
* @param vert root node
* @param action defines actions to take on each node traversal
*/
public void run(Vertex vert, BfsAction action) {
List<Vertex> trackVisitedList = new ArrayList<>();
Queue q = new LinkedList();
q.add(vert);
vert.setVisited(true);
trackVisitedList.add(vert);
while (!q.isEmpty()) {
Vertex n = (Vertex) q.poll();
//we are breaking if needed
if (action.onVisitParent(n))
break;
for (Vertex adj : n.getAdjVertices()) {
if (!adj.isVisited()) {
adj.setVisited(true);
trackVisitedList.add(adj);
q.add(adj);
//we are breaking if needed
if (action.onVisitChild(adj)) {
//we are emptying the quee to break from the loop
q = new LinkedList();
break;
}
}
}
}
//reset vertexes state
for (Vertex v : trackVisitedList) {
v.setVisited(false);
}
}
/**
* That interface will help us to generify BFS Algorithm usage
* for different purposes
*/
public interface BfsAction {
/**
* @return true if want to interrupt traversal
*/
boolean onVisitParent(Vertex vertex);
/**
* @return true if want to interrupt traversal
*/
boolean onVisitChild(Vertex vertex);
}
}
*********************************************************************************
public class Main {
public static final int SIZE_OF_CHESS_BOARD = 8;
public static final Vertex DESTINATION_VERTEX = new Vertex(0, 2);
private static final BfsAlgorithm bfs = new BfsAlgorithm();
private static final ProblemConditions problemConditions = new ProblemConditions(SIZE_OF_CHESS_BOARD, 1, 2);
/**
* Creates chess board as a graph represented as adjacency list
*
* @return root node of the graph
*/
private static Vertex createChessboardGraph() {
//first we are creating all possible nodes in the graph
//without associating any adjacent nodes to them
final ArrayList<Vertex> vertexes = new ArrayList<>();
for (int i = 0; i <= problemConditions.getChessBoardSize(); i++) {
for (int j = 0; j <= problemConditions.getChessBoardSize(); j++) {
vertexes.add(new Vertex(i, j));
}
}
//and now we are actually associating adjacent nodes
//to each created node
for (Vertex v : vertexes) {
if (v.getAdjVertices().isEmpty())
createAdjListForVertex(v, vertexes);
}
//we return the root node as it will represent the entire graph
return vertexes.get(0);
}
/**
* Creates adjacency list for provided node , according to problem definition
*
* @param vertexes are used to define connections between one another
*/
private static void createAdjListForVertex(Vertex v, ArrayList<Vertex> vertexes) {
//Here we are just trying to create adjacent nodes in all possible directions
int xRightFull = v.getX() + problemConditions.getFareMostMove();
int xRightHalf = v.getX() + problemConditions.getNearestMove();
int xLeftFull = v.getX() + -problemConditions.getFareMostMove();
int xLeftHalf = v.getX() + -problemConditions.getNearestMove();
int yUpFull = v.getY() + problemConditions.getFareMostMove();
int yUpHalf = v.getY() + problemConditions.getNearestMove();
int yDownFull = v.getY() + -problemConditions.getFareMostMove();
int yDownHalf = v.getY() + -problemConditions.getNearestMove();
//full right half up
createAdjVertexIfInBounds(v, xRightFull, yUpHalf, vertexes);
//half right Full up
createAdjVertexIfInBounds(v, xRightHalf, yUpFull, vertexes);
//half left Full up
createAdjVertexIfInBounds(v, xLeftHalf, yUpFull, vertexes);
//full left half up
createAdjVertexIfInBounds(v, xLeftFull, yUpHalf, vertexes);
//full left half down
createAdjVertexIfInBounds(v, xLeftFull, yDownHalf, vertexes);
//half left full down
createAdjVertexIfInBounds(v, xLeftHalf, yDownFull, vertexes);
//half right full down
createAdjVertexIfInBounds(v, xRightHalf, yDownFull, vertexes);
//full right half down
createAdjVertexIfInBounds(v, xRightFull, yDownHalf, vertexes);
}
/**
* adds adjacent nodes according to constrains in problem definition
*
* @param vertexes will be used to define connections between one another
*/
private static void createAdjVertexIfInBounds(Vertex v, int x, int y, ArrayList<Vertex> vertexes) {
//check problemConditions
if (problemConditions.isPositionOnChessBoard(x, y)) {
//we don't want to assign new instances of Vertexes
//as adjacent nodes , that will not work.
//we need to reuse the same instances and assign
//connections between them
final int indexOf = vertexes.indexOf(new Vertex(x, y));
final Vertex reusedVertex = vertexes.get(indexOf);
v.addAdjVertex(reusedVertex);
}
}
/**
* Finds a shortest path from source to destination
*
* @param from source node
* @param to destination node
* @return string complete representation of solved problem
*/
private static String solveProblem(final Vertex from, final Vertex to) {
final List<Vertex> path = new ArrayList<>();
final HashMap<Vertex, Vertex> parentToChild = new HashMap<>();
bfs.run(from, new BfsAlgorithm.BfsAction() {
private Vertex currParent;
@Override
public boolean onVisitParent(Vertex parent) {
currParent = parent;
return false;
}
@Override
public boolean onVisitChild(Vertex vertex) {
parentToChild.put(vertex, currParent);
if (vertex.equals(to)) return true;
else return false;
}
});
path.add(to);
Vertex par = parentToChild.get(to);
while (par != null) {
path.add(par);
par = parentToChild.get(par);
}
Collections.reverse(path);
return "Turns Required to reach destination: " + (path.size() - 1) + "\nPath : "
+ pathToString(path);
}
/**
* Converts a list of nodes that represents a path
* to simple string representation
*
* @param path list of nodes
*/
private static String pathToString(List<Vertex> path) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < path.size(); i++) {
Vertex v = path.get(i);
if (i != 0)
sb.append("->");
sb.append(v.getName());
}
return sb.toString();
}
/**
* Prints the graph as adjacency list
*
* @param graph root node
*/
private static void printGraph(Vertex graph) {
List<Vertex> list = graphToList(graph);
Collections.sort(list, new Comparator<Vertex>() {
public int compare(Vertex o1, Vertex o2) {
if (o1.getX() == o2.getX()) return o1.getY() - o2.getY();
else return o1.getX() - o2.getX();
}
});
StringBuilder sb = new StringBuilder();
for (Vertex vert : list) {
sb.append(vert + "->");
for (Vertex adjV : vert.getAdjVertices()) {
sb.append(" " + adjV);
}
sb.append("\n");
}
System.out.println(sb.toString());
}
/**
* Uses bfs internally to convert a graph to list of
* distinct nodes
*
* @param vert root node
* @return list of all child nodes
*/
private static List<Vertex> graphToList(Vertex vert) {
final List<Vertex> list = new ArrayList<>();
bfs.run(vert, new BfsAlgorithm.BfsAction() {
@Override
public boolean onVisitParent(Vertex v) {
list.add(v);
return false;
}
@Override
public boolean onVisitChild(Vertex vertex) {
return false;
}
});
return list;
}
public static void main(String[] args) {
//we are representing available moves on NxN chessboard
//by vertex adjacency list
Vertex root = createChessboardGraph();
//printing the graph for visualisation
System.out.println("Graph adjacency list :\n");
printGraph(root);
//printing the solution
System.out.println(solveProblem(root, DESTINATION_VERTEX));
}
}
*********************************************************************************
That's all :)Let me know what you think , and if I have mistakes or typos don't hesitate to notify me ;)
final HashMap parentToChild = new HashMap<>();
ReplyDeleteI guess, you mean childToParent based on your logic, not parentToChild