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

package com.av.demosnakeladder;

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

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

public class DemoSnakeLadder {

 public static void main(String[] args) {
  
  Integer board[] = new Integer[101];
  
  for(int i=1; i<100; i++){
   board[i] = new Integer(i);
  }
  
  List<GroupInfo> laddersInfo = new ArrayList<GroupInfo>();
   laddersInfo.add(new GroupInfo(board[2], board[32]));
   laddersInfo.add(new GroupInfo(board[14], board[57]));
   laddersInfo.add(new GroupInfo(board[27], board[78]));
   laddersInfo.add(new GroupInfo(board[34], board[44]));
   laddersInfo.add(new GroupInfo(board[7], board[98]));
  //Ladder Configuration
  DirectedGraph<Integer, DefaultEdge> ladders = new DefaultDirectedGraph<Integer, DefaultEdge>(DefaultEdge.class);
  /*
   * Ladders are at 
   * 2 -> 32
   * 14 -> 57
   * 27 -> 78
   * 34 -> 44
   * 7 -> 98
   */
  for(GroupInfo gi : laddersInfo){
   ladders.addVertex(gi.getStartIndex());
   ladders.addVertex(gi.getEndIndex());
   ladders.addEdge(gi.getStartIndex(), gi.getEndIndex());
  }
  
  
  List<GroupInfo> snakesInfo = new ArrayList<GroupInfo>();
   snakesInfo.add(new GroupInfo(board[99], board[10]));
   snakesInfo.add(new GroupInfo(board[77], board[22]));
   snakesInfo.add(new GroupInfo(board[62], board[13]));
   snakesInfo.add(new GroupInfo(board[54], board[8]));
   snakesInfo.add(new GroupInfo(board[42], board[3]));
  
  //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){
   snakes.addVertex(gi.getStartIndex());
   snakes.addVertex(gi.getEndIndex());
   snakes.addEdge(gi.getStartIndex(), gi.getEndIndex());
  }
  
  /*
   * 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];
    
    if(ladders.containsVertex(boardCurrentValue)){
     boardCurrentValue = ladders.getEdgeTarget(ladders.edgesOf(boardCurrentValue).iterator().next());
     System.out.println("Congratulations, you got ladder to " + boardCurrentValue);
     player1 = boardCurrentValue;
    }else if(ladders.containsVertex(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);
  
  ladder.addVertex(two);
  ladder.addVertex(twentyOne);
  
  ladder.addEdge(two, twentyOne);
  
  System.out.println(ladder.getEdgeTarget(ladder.edgesOf(two).iterator().next()));
  
  // 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");

   // add the vertices
   g.addVertex(amazon);
   g.addVertex(yahoo);
   g.addVertex(ebay);

   // add edges to create linking structure
   g.addEdge(yahoo, amazon);
   g.addEdge(yahoo, ebay);
  } 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 the vertices
  g.addVertex(v1);
  g.addVertex(v2);
  g.addVertex(v3);
  g.addVertex(v4);

  // add edges to create a circuit
  g.addEdge(v1, v2);
  g.addEdge(v2, v3);
  g.addEdge(v3, v4);
  g.addEdge(v4, v1);

  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 "";
}

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

import com.av.demo.annotation.TestAnnotation;

public class ClassThatReadsAnnotation {

 
 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");
 }
}

Embedding log4j in the Java project

Hello all, today I am going to discuss about the log4j.

Log4j is a Java library that offers Java logging. This means that it is useful to write the logs in your code and that too it is highly configurable that makes it much more popular.

Now as we know that log4j is pretty useful so we should now see how it works.

I will try to explain the things for two different versions i.e. log4j 2.x and 1.x.

Let us first take an example of Log4j 1.x version.

FYI, I  am actually working with Maven but log4j can be downloaded as a standalone api and added in your classpath to work with your Java project.

  1. Create an maven eclipse project, give the groupid and artifactid for your project and finish it.
  2. Edit the pom.xml and add the following
    log4j
    log4j
    1.2.17

  • As soon as you save your pom.xml, your log4j.jar gets downloaded in to Maven dependencies folder.
      



  • 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
    2. Breadth First Approach
    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;
    import java.util.concurrent.LinkedBlockingQueue;
    
    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; 
      Queue<Node> queue = new LinkedBlockingQueue<Node>();
      queue.add(root);
      
      while(!queue.isEmpty()){
       Node n = queue.poll();
       if(n.left !=null){
        queue.add(n.left);
       }
       if(n.right!=null){
        queue.add(n.right);
       }
       
       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);
      inOrderList.add(root);
      inOrder(root.right);
     }
     
     public static void preOrder(Node root){
      if(root == null){
       return;
      }
      preOrderList.add(root);
      preOrder(root.left);
      preOrder(root.right);
      
     }
     
     public static void postOrder(Node root){
      if(root == null){
       return;
      }
      postOrder(root.left);
      postOrder(root.right);
      postOrderList.add(root);
     }
     
    }
    
    
    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;
     }
    }
    

    Monday, November 30, 2015

    Getting the Prime numbers using the Sieve of Eratosthenes method

    Hello Guys, today we are going to look the method by which the large number of prime numbers can be calculated.

    The definition of the Sieve of Eratosthenes method goes this way:
    "Mark the first presence of the number as prime and mark all its multiples as non primes." - Wiki


    Looking at the diagram its pretty clear to understand that the first presence of number is considered to be prime and all the multiples of it (increasing order) is marked non prime also, we will check for the prime only if the number is not marked as non prime before, like in case of 6, the number would be marked as non prime before while we run the thing for the number 2 so it is skipped in case of 3.

    Now lets see the program as well, running link here

    Here is the code:

    import java.util.*;
    import java.lang.*;
    import java.io.*;
    
    class Solution {
        public static void main(String[] args) {
      int MAX = 1000000;
      int T = 0;
      boolean isPrime[] = new boolean[MAX];
      for(int i=2; i<isPrime.length; i++)
       isPrime[i] = true;
      
      int primes[] = new int[MAX];
      int p = 0;
      for(int i=2;i<MAX;i++){
       if(isPrime[i]){
        primes[p++] = i;
        for(int j=2*i; j<MAX; j+=i)
         isPrime[j] = false;
       }
      }
      System.out.println("All your prime numbers are calculated, just for example I am taking out the 10101th prime number");
      T = 10101;
      System.out.println(primes[T]);
        }
    }