## Sunday, December 20, 2015

### Snake and Ladder using graph in Java

Hello guys, today I want to talk about the well known game of all times. Snake and ladders.

Let us think of creating the game in Java using Graph.

Before starting I have to clear some of the points.

1. I didn't entertained edge cases to the maximum.
2. Also I have created 2 different graph. one for ladders addresses and one for snakes addresses.
3. There are different approaches of solving this problem as well but I have used graph in order to do so.
4. Now lets see the program.
Full code is available here

Example code
```

import java.util.ArrayList;
import java.util.List;

import org.jgrapht.DirectedGraph;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;

public static void main(String[] args) {

Integer board[] = new Integer[101];

for(int i=1; i<100; i++){
board[i] = new Integer(i);
}

DirectedGraph<Integer, DefaultEdge> ladders = new DefaultDirectedGraph<Integer, DefaultEdge>(DefaultEdge.class);
/*
* 2 -> 32
* 14 -> 57
* 27 -> 78
* 34 -> 44
* 7 -> 98
*/
}

List<GroupInfo> snakesInfo = new ArrayList<GroupInfo>();

//Snake Configuration
DirectedGraph<Integer, DefaultEdge> snakes = new DefaultDirectedGraph<Integer, DefaultEdge>(DefaultEdge.class);
/*
* Snakes are at
* 99 -> 10
* 77 -> 22
* 62 -> 13
* 54 -> 8
* 42 -> 3
*/
for(GroupInfo gi : snakesInfo){
}

/*
* These are the current positions of the player, I am considering 1 players
*/
int player1 = 1;

//The game goes till he reaches 100
while(player1  != 100){
//get the value of dice and
int nextValue = getNextDiceValue();
System.out.println("Player is in " + player1 + " and got " + nextValue + " so next position is " + (player1 + nextValue));

if((player1 + nextValue) <= 100){

if((player1 + nextValue) == 100){
System.out.println("!!!Congratulations you won!!! ");
System.out.println("Bye, have a nice day");
break;
}

//Now this is the current position of the player
player1 += nextValue;

Integer boardCurrentValue = board[player1];

System.out.println("Congratulations, you got ladder to " + boardCurrentValue);
player1 = boardCurrentValue;
boardCurrentValue = snakes.getEdgeTarget(snakes.edgesOf(boardCurrentValue).iterator().next());
System.out.println("Oops, you get stung by snake and now you came to " + boardCurrentValue);
player1 = boardCurrentValue;
}
}
}
}

private static int getNextDiceValue(){
//here randomize the dice for value between 1 & 6 and return the value that comes back
int result = 0;

while(result == 0){
result = (int)(Math.random() * 10);

if(result > 6){
result -= 6;
}
}
return result;
}
}

class GroupInfo{
private Integer startIndex;
private Integer endIndex;

public GroupInfo(Integer startIndex, Integer endIndex) {
super();
this.startIndex = startIndex;
this.endIndex = endIndex;
}

public Integer getStartIndex() {
return startIndex;
}

public void setStartIndex(Integer startIndex) {
this.startIndex = startIndex;
}

public Integer getEndIndex() {
return endIndex;
}

public void setEndIndex(Integer endIndex) {
this.endIndex = endIndex;
}
}

```

## Tuesday, December 15, 2015

### Graph in Java

Hello all, today let's see something about the Graphs.

So technically speaking Graph is "A graph in this context is made up of vertices or nodes or points and edges or arcs or lines that connect them. A graph may be un-directed, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another. "- Wiki

So now we can say that we understand what a graph is. Right?

Ok let me try to rephrase the things in a different way. Graph is a data structure with Vertices and Edges. Now vertices are the nodes and edges are the connectors between these nodes. A graph can be directed or non directed with weights on edges.

Why is graph theory so important?
In real world, the graph theory is important in neural network, shortest path between 2 destinations and many more applications of graph are there.

Now coming to the Java, there are number of libraries available to use, but I have used JGraphT and found it pretty descent. The api is available here. You can incorporate it in your project via Maven or including it in the classpath after downloading the jar.

Let us take an example of Graph using JGraphT library.

Code can be found here.

Code snippet
```import java.net.MalformedURLException;
import java.net.URL;

import org.jgrapht.DirectedGraph;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;

public class DemoGraph {

public static void main(String[] args) {

UndirectedGraph<String, DefaultEdge> stringGraph = createStringGraph();

// note undirected edges are printed as: {<v1>,<v2>}
System.out.println(stringGraph.toString());

// create a graph based on URL objects
DirectedGraph<URL, DefaultEdge> hrefGraph = createHrefGraph();

DirectedGraph<Integer, DefaultEdge> ladder = new DefaultDirectedGraph<Integer, DefaultEdge>(DefaultEdge.class);

Integer two = new Integer(2);
Integer twentyOne = new Integer(21);

// note directed edges are printed as: (<v1>,<v2>)
System.out.println(hrefGraph.toString());
}

/**
* Creates a toy directed graph based on URL objects that represents link
* structure.
*
* @return a graph based on URL objects.
*/
private static DirectedGraph<URL, DefaultEdge> createHrefGraph() {
DirectedGraph<URL, DefaultEdge> g = new DefaultDirectedGraph<URL, DefaultEdge>(DefaultEdge.class);

try {
URL amazon = new URL("http://www.amazon.com");
URL yahoo = new URL("http://www.yahoo.com");
URL ebay = new URL("http://www.ebay.com");

} catch (MalformedURLException e) {
e.printStackTrace();
}

return g;
}

/**
* Create a toy graph based on String objects.
*
* @return a graph based on String objects.
*/
private static UndirectedGraph<String, DefaultEdge> createStringGraph() {
UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>(
DefaultEdge.class);

String v1 = "v1";
String v2 = "v2";
String v3 = "v3";
String v4 = "v4";

// add edges to create a circuit

return g;
}

}
```

## Wednesday, December 9, 2015

### Annotation in Java

Hello guys, today we will try to learn something about the Annotations.

Annotation:
"An annotation is a metadata (e.g. a comment, explanation, presentational markup) attached to text, image, or other data.Often, annotations make reference to a specific part of the original data." - Wiki

In other words, it is a kind of code that gives the user a way to pass some data from its code to the developer of the annotation who have given annotations to use in the code so that he knows that the user wants to do what.

Oh my God, what have I read there? :O

Well let us take an example like we have to get the data from the database. So for that we :
1. Have to create a connection
2. Open a connection
3. Get the data considering the exceptions and all
4. After getting the data, close the connection
5. Release the memory
Now these 5 steps are going to be happened all the times whenever we have to get the data from the database.

These type of codes which are to be executed number of times are termed as boiler plate codes. And in order to get rid of boiler plate codes Java have introduced the concept of Annotation.

Now the annotation is a very useful feature. If you have used the Spring, Hibernate or any framework you would have gone through it.

Lets take an example of reading and making the annotation in Java.

You can get  the project from here.

Its basically a simple project that works in the following way:
1. We first create an annotation that have the properties which would be available (TestAnnotation.java).
2. Then I have created the Java class where I used the annotation created in step no: 1(TestClassWithAnnotationUsed.java).
3. And lastly I have coded the class that will read all the functions that used our annotation(ClassThatReadsAnnotation.java)
TestAnnotation.java
```import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

@Retention(RetentionPolicy.RUNTIME)
@Target(ElementType.METHOD)
public @interface TestAnnotation {
public String name() default "";
}
```

```import java.lang.annotation.Annotation;
import java.lang.reflect.Method;

import com.av.demo.annotation.TestAnnotation;

public static void main(String[] args) {
System.out.println("Lets first create a normal object of the TestClassWithAnnotationUsed class");
TestClassWithAnnotationUsed obj = new TestClassWithAnnotationUsed();
System.out.println("Now call the method and see whether it works or not");
obj.functionWithAnnotationApplied_1();
System.out.println("Now we read the annotation and try to get the value that is passed in for the string. "
+ "\nThis is usually done by reading the annotation in the runtime. "
+ "\nAnd this is done by the concept called Reflection of Java. "
+ "\nBy the we can actually manipulate the classes and objects in runtime, "
+ "\nwhich is internally by the apis like spring and hibernate. ");

//Getting the reference of the class Object
Class<Testclasswithannotationused> testClassWithAnnotationUsedClass = TestClassWithAnnotationUsed.class;

for (Method method : testClassWithAnnotationUsedClass.getDeclaredMethods()) {
//Checking for the presence of the Annotation we have made
if(method.isAnnotationPresent(TestAnnotation.class)){
Annotation annotation = method.getAnnotation(TestAnnotation.class);
TestAnnotation test = (TestAnnotation) annotation;
System.out.println(test.name());
}
}

}

}
```

TestClassWithAnnotationUsed.java
```import com.av.demo.annotation.TestAnnotation;

public class TestClassWithAnnotationUsed {

@TestAnnotation(name="ACCEPTED_VALUE")
public void functionWithAnnotationApplied_1(){
System.out.println("I have applied the annotation TestAnnotation with value ACCEPTED_VALUE");
}

@TestAnnotation(name="NON_ACCEPTED_VALUE")
public void functionWithAnnotationApplied_2(){
System.out.println("I have applied the annotation TestAnnotation with value NON_ACCEPTED_VALUE");
}
}
```

## Wednesday, December 2, 2015

### Breadth First Traversal in Binary Trees

Hey guys, lets see the way of traversing the tree in a breadth first fashion.

So when the question comes for traversing the tree there are broadly two categories:

1. Depth First Approach
1. InOrder
2. PreOrder
3. PostOrder
In the first approach the style of traversing the tree is in a depth first fashion which means, that we keep on traversing the tree in a manner that goes vertically rather than horizontally.

In case of the breadth first approach we go layer by layer or in other words we go level by level.

So if I have a tree like:
then in this tree, we will say that the :
• 1 is at Level 0
• 2,3 is at level 1
• 4,5,6,7 is at level 2
• 10,11,8,9 is at level 3
• 12,13 is at level 4
So going forward with this approach we want to traverse the the tree in a level wise manner, and at the end the traversal would be : 1,2,3,4,5,6,7,10,11,8,9,12,13

Now coming to the code of this, it is very easy, if we uses queue in the code. We start by root and we keep pushing the children of the traversed node in to queue and keep on traversing the node taking from the queue.

Code here

```import java.util.Queue;

class BFS {

public static void main(String[] args) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
Node n7 = new Node(7);
Node n8 = new Node(8);
Node n9 = new Node(9);
Node n10 = new Node(10);
Node n11 = new Node(11);
Node n12 = new Node(12);
Node n13 = new Node(13);

n1.left = n2;
n1.right = n3;

n2.left = n4;
n2.right = n5;

n3.left = n6;
n3.right = n7;

n4.left = n4.right = null;

n5.left = n10;
n5.right = n11;

n6.left = n6.right = null;

n7.left = n8;
n7.right = n9;

n10.left = n12;
n10.right = n13;

n11.left = n11.right = null;

n8.left = n8.right = null;
n9.left = n9.right = null;

Node root = n1;

while(!queue.isEmpty()){
Node n = queue.poll();
if(n.left !=null){
}
if(n.right!=null){
}

System.out.print(n.info + ", ");
}
}

}

class Node{
public Node left;
public Node right;
public int info;

public Node(int info){
this.info = info;
this.left = null;
this.left = null;
}

public String toString(){
return "" + this.info;
}
}

```

## Tuesday, December 1, 2015

### Lowest Common Ancestor of a Tree

Hello guys, during one of my interview, the interviewer asked me something about the Lowest Common Ancestor. At first point it was a bit unusual thing as I never heard of it before, but when he explained me the stuff that what is a Lowest Common Ancestor, I found that it is quite good.

So here it goes lets suppose you have a tree like this:

The example is pretty clear. If you look closely you will find out that the lowest common ancestor is the common root for both the nodes. So:

• If  you take the case of the 4, 5 the first common root (or more preferably ancestor/parent) is 2
• If  you take the case of the 4, 6 the first common root (or more preferably ancestor/parent) is 1
Now the question arises how do we get to this using the program. So let me try to explain the simple solution what we can do for this to work:

First of all let us try to understand the basic traversing algos of the Trees (binary). These are as follows:
1. In-Order(Left-Node-Right)
2. Post-Order(Left-Right-Node)
3. Pre-Order(Node-Left-Right)

So considering the above example, let us try to take out the In-Order and Pre-Order:
• In-Order will be 4, 2, 12, 10, 13, 5, 11, 1, 6, 3, 8, 7, 9
• Post-Order will be 4, 12, 13, 10, 11, 5, 2, 6, 8, 9, 7, 3, 1
Now after this we can say some of the key points, those are:
1. The left subtree of any node is available in Inorder
2. Now take all the subnodes of two nodes for which we have to find the LCA
3. Now if you select the node at the maximum index in Post-order among all the nodes of step (2) list you will find the LCA.
Explanation:
The reason is very clear the Inorder gives you all the possible in between nodes of the 2 nodes for which you want to find the LCA. Now out of these nodes the root of these in between nodes, i.e LCA in other terms would be at last in Post order because by definition of Post order we always have the Node at the last. So considering this, if we want to get the LCA for Node 6 and Node 9 then the answer would be 3.

Note:
• I have considered the above example for my reference and have created the code according to the above scenario, so please update it according to your needs.
• The overall example and logic will remain the same only the creation of the tree will change. So the left and right might change in a tree.
• I have just coded the basic one, didn't covered the edge cases and all the checks.
Working code here:

Java Code
```package com.test.tree;

import java.util.ArrayList;
import java.util.List;

public class TreeTraversal {

public static final List<Node> inOrderList = new ArrayList<>();
public static final List<Node> preOrderList = new ArrayList<>();
public static final List<Node> postOrderList = new ArrayList<>();

public static void main(String[] args) {

Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
Node n7 = new Node(7);
Node n8 = new Node(8);
Node n9 = new Node(9);
Node n10 = new Node(10);
Node n11 = new Node(11);
Node n12 = new Node(12);
Node n13 = new Node(13);

n1.left = n2;
n1.right = n3;

n2.left = n4;
n2.right = n5;

n3.left = n6;
n3.right = n7;

n4.left = n4.right = null;

n5.left = n10;
n5.right = n11;

n6.left = n6.right = null;

n7.left = n8;
n7.right = n9;

n10.left = n12;
n10.right = n13;

n11.left = n11.right = null;

n8.left = n8.right = null;
n9.left = n9.right = null;

inOrder(n1);
System.out.println("Inorder traversal is " + inOrderList);
postOrder(n1);
System.out.println("Postorder traversal is " + postOrderList);

/*
* 1. we take the list of nodes that are in between them
* 2. then we take the address of each node of the above found list
* 3. the node that is in the farthest position, will be the LCA
*/
Node fn = n6;
Node sn = n9;
System.out.println("We are gonna find the LCA between " + fn + " & " + sn);
List<Node> inBetweenList = inBetween(inOrderList, fn, sn);
System.out.println("The nodes in between " + fn + " and " + sn + " are as follows " + inBetweenList);
System.out.println("LCA of " + fn + " & " + sn + " is " + lca(inBetweenList, postOrderList));
}

public static List inBetween(List<node> inOrder, Node fn, Node sn){
int i1 = inOrder.indexOf(fn);
int i2 = inOrder.indexOf(sn);
List<Node> result = i1 > i2 ? inOrder.subList(i2, i1 + 1) :  inOrder.subList(i1, i2 + 1);
return result;
}

public static Node lca(List<node> inBetweenList, List<node> postOrderList){
Node result = null;
int maxIndex = 0;
for(Node node : inBetweenList){
maxIndex = postOrderList.indexOf(node) > maxIndex ? postOrderList.indexOf(node) : maxIndex;
}

result = postOrderList.get(maxIndex);
return result;
}

public static void inOrder(Node root){
if(root == null){
return;
}
inOrder(root.left);
inOrder(root.right);
}

public static void preOrder(Node root){
if(root == null){
return;
}
preOrder(root.left);
preOrder(root.right);

}

public static void postOrder(Node root){
if(root == null){
return;
}
postOrder(root.left);
postOrder(root.right);
}

}

class Node{
public Node left;
public Node right;
public int info;

public Node(int info){
this.info = info;
this.left = null;
this.left = null;
}

public String toString(){
return "" + this.info;
}
}
```