Tuesday, September 24, 2013

Reading Flat files seperated by | symbol

Often I have seen that there are files having lines seperated by a de-limiter |.
I thought of making a class that could easily iterate over each of the line one by one..

This class PipedString represents a string which has elements seperated by a | symbol.
This is an iterable class

Create a class PipedString as follows

package flatfilereader;

import java.util.Iterator;

public class PipedString implements Iterable<String> {
    private String line;
    private int index = 0;
    @Override
    public String toString()
    {
        return line;
    }
    public PipedString(String x) {
        this.line = x;
    }
    @Override
    public Iterator<String> iterator() {
        return new Iterator<String>()
        {
            private String _currentElement;
            String[] symbols=null;
            @Override
            public boolean hasNext() {
                try {
                     if(symbols==null) 
                     {
                         symbols = line.split("\\|");
                     }
                    _currentElement = symbols[index];
                } catch (Exception ex) {
                    line = null;
                }

                return (index < symbols.length);
            }

            @Override
            public String next() {
                index++;
                return _currentElement;
            }

            @Override
            public void remove() {
            }
        };
    }
}

Now create a Flat File Reader using this PipedString

package flatfilereader;
import java.util.*;
import java.io.*;
  
public class FlatFileReader implements Iterable<PipedString>
{
    private BufferedReader _reader;
  
    public FlatFileReader(String filePath) throws Exception
    {
        _reader = new BufferedReader(new FileReader(filePath));
    }
  
    public void Close()
    {
        try
        {
            _reader.close();
        }
        catch (Exception ex) {}
    }
  
    public Iterator<PipedString> iterator()
    {
        return new PipedStringIterator();
    }
    private class PipedStringIterator implements Iterator<PipedString>
    {
        private PipedString _currentLine;
  
        public boolean hasNext()
        {
            try
            {
                String cl = _reader.readLine();
                if(cl==null) return false;
                _currentLine = new PipedString(cl);
            }
            catch (Exception ex)
            {
                _currentLine = null;
            }
  
            return _currentLine != null;
        }
  
        @Override
        public PipedString next()
        {
            return _currentLine;
        }
  
        public void remove()
        {
        }
    }
}

How to use this FlatFileReader class

    public static void main(String[] s) throws Exception
    {
        FlatFileReader f= new FlatFileReader("D:/test/x.txt");
        for(PipedString pps : f)
        {
            for(String eachElement : pps)
            {
                System.out.println(eachElement);
            }
        }
        f.Close();
    }


Saturday, September 14, 2013

A generic problem solver from State to Goal

I thought of making a generic problem solver, which could solve any problem which has an initial state and a final state and a set of possible moves.

Though my program is not perfect, but still it is able to give some learning and if you guys have suggestions to make it better, please feel free to write in comments.

I have tried to use Template Design pattern here.. Where an algorithm is implemented in the abstract class with some parts left out to be implemented by the user.

Create a State interface

package mystate;
import java.util.ArrayList;
import java.util.List;
public abstract class State
{
    // Define a state that'll hold reference to predecessor.
    public State predecessor = null;    
    public abstract boolean isGoal();
    @Override
    public abstract boolean equals(Object xx);
    @Override
    public abstract int hashCode();
    public abstract List<State> getChildren() ;
    @Override
    public abstract String toString();

    public State getPredecessor() {
        return this.predecessor;
    }

    public void setPredecessor(State s) {
        this.predecessor = s;
    }
    public void printResult()
    {
        List<State> result =  new ArrayList<State>();
        State c = this;
        while(c.getPredecessor() !=null)
        {
            result.add(c.getPredecessor());
            c=c.getPredecessor();
        }      
        for(int i=result.size()-1;i>=0;i--)
        {
            State curr = result.get(i);
            System.out.println(curr);
        }   
        System.out.print(this);
    }
}


Now implement this abstract class and create a custom class that defines the state of your problem.
Please make sure that you override all the methods given in the interface very correctly.
Do make member variables that can signify your state.
For example, let me take an example of 15-squred number puzzle

Implement the abstract class and create SlidingState class

package mystate;

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

/**
 *
 * @author Yogi
 */
public class SlidingState extends State {

    int[][] currentState = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12},{0,13,14,15}};  
    public SlidingState()
    {

    }    
    // Provide constructors to initialize the state.
    public SlidingState(int[][] state)
    {
        this.currentState = state;
    }
    @Override
    public int hashCode()
    {
        return Arrays.deepHashCode(currentState);
    }
    // Be double sure that you override equals method correctly
    // else you'll end up in infinite loop.
    @Override
    public boolean equals(Object xx)
    {
        if(xx==null) return false;
        if(!(xx instanceof SlidingState))
        {
            return false;
        }
        return Arrays.deepEquals(this.currentState, ((SlidingState)xx).currentState);
    }
    @Override
    public boolean isGoal() {
        int[][] goalState = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,0}};
        return Arrays.deepEquals(currentState, goalState);
    }

    @Override
    public List<State> getChildren() {
        List<State> children = new ArrayList<State>();
        // First find where is the 0 in the grid
        boolean found0=false;
        int i=0;
        int j=0;
        for(i=0;i<4;i++)
        {
            for(j=0;j<4;j++)
            {
                if(currentState[i][j]==0)
                {
                    found0=true;
                    break;
                }
            }
            if(found0) break;
        }
        List<Integer> moves = findMoves(i,j);
        for(Integer m : moves)
        {
            int[][] newPosition = exchange(currentState, m);
            State t = new SlidingState(newPosition);
            t.setPredecessor(this);
            children.add(t);
        }
        return children;
        
    }
    @Override 
    public String toString()
    {
        StringBuilder s = new StringBuilder("");
        s.append("{\n");
        for(int i=0;i<4;i++)
        {
            s.append("{");
            for(int j=0;j<4;j++)
            {
                s.append(currentState[i][j]);
                if(j!=3) s.append(",");
            }
            s.append("}");            
        }
        s.append("\n}");    
        return s.toString();
    }
    private List<Integer> findMoves(int i, int j) {
        List<Integer> moves = new ArrayList<Integer>();
        try
        {
            moves.add(currentState[i+1][j]);
        }
        catch(Throwable t)
        {
            
        
        }         
        try
        {
            moves.add(currentState[i][j+1]);
        }
        catch(Throwable t)
        {
            
        } 
        try
        {
            moves.add(currentState[i][j-1]);
        }
        catch(Throwable t)
        {
            
        }   
        
        try
        {
            moves.add(currentState[i-1][j]);
        }
        catch(Throwable t)
        {
            
        }
 
           
        return moves;
        
    }

    private int[][] exchange(int[][] currentState, Integer m) {
        int i=0;
        int j=0;
        int mi=0;
        int mj=0;        
        int[][] newPos = new int[4][4];
        for(i=0;i<4;i++)
        {
            for(j=0;j<4;j++)
            {
                newPos[i][j]=currentState[i][j];
            }
        }
        boolean find0 = false;

        for(i=0;i<4;i++)
        {
            for(j=0;j<4;j++)
            {
                if(newPos[i][j]==0)
                {
                    find0=true;
                    break;
                }
            }
            if(find0) break;
        }                
        boolean findm=false;
        for(mi=0;mi<4;mi++)
        {
            for(mj=0;mj<4;mj++)
            {
                if(newPos[mi][mj]==m.intValue())
                {
                    findm=true;
                    break;
                }
            }
            if(findm) break;
        }    
        newPos[i][j]=m.intValue();
        newPos[mi][mj]=0;
        return newPos;        
    }

}

Create a SolveProblem abstract class as follows

SolveProblem Abstract class

package solution;


import mystate.State;
import java.util.Set;
import java.util.List;

public abstract class SolveProblem {
    private java.util.Set<State> visitedStates;

    public Set<State> getStateQueue() {
        return stateQueue;
    }

    public void setStateQueue(Set<State> stateQueue) {
        this.stateQueue = stateQueue;
    }

    public java.util.Set<State> getVisitedStates() {
        return visitedStates;
    }

    public void setVisitedStates(java.util.Set<State> visitedStates) {
        this.visitedStates = visitedStates;
    }
    private Set<State> stateQueue;  
    public abstract State getStateObject();
    public SolveProblem()
    {
        // For visitedState, HashSet did work, because we are never
        // retrieving from visitedStates, but checking only contains method.
        visitedStates=new java.util.HashSet<State>();
        // You have to use LinkedHashSet here, because, retrieval order must 
        // be same as insertion order... otherwise, it'll go into an infinite
        // loop.
        stateQueue = new java.util.TreeSet<State>();  
        
    }
    public void bfs()
    {
        State currentState = getStateObject();
        // Add current state to state Queue.
        stateQueue.add(currentState);
        do
        {
            // Get the first Element from Queue.
            //Collections.sort(stateQueue);
            State firstElementInQueue = stateQueue.iterator().next();//stateQueue.peek();
            // If the first Element is the Goal
            // We are done.
            if(firstElementInQueue.isGoal())
            {
                firstElementInQueue.printResult();
                // There is no recursion here, so simple return would do.
                return;
            }
            else
            {
                // Add firstElement to visited States
                visitedStates.add(firstElementInQueue);    
                // Get the children of first element
                List<State> children = firstElementInQueue.getChildren();
                for(State v : children)
                {
                    if(v.isGoal())
                    {
                        v.printResult();
                        return;
                    }
                    if(!visitedStates.contains(v))
                    {
                        stateQueue.add(v);
                    }
                            
                }
                // Remove the first element from state queue.
                stateQueue.remove(firstElementInQueue);
                
            }
            long sz=stateQueue.size();
            if(sz%1000==0)
            System.out.println(sz);
            // do this till state queue is empty.
        }while(!stateQueue.isEmpty());
    }
    public void dfs(State currentState, java.util.Set<State> vStates)
    {
        // if we pass vStates as null. i.e. in the beginning.
        if(vStates==null) vStates = visitedStates;
        // if visisted state contains currentState, then just return.
        // This is the wrong branch, and we need not traverse it further.
        if(vStates.contains(currentState))
            return;
        
        // if it is GOAL
        if(currentState.isGoal())
        {
            // That's it we are done.
            currentState.printResult();
            System.exit(0);            
        }
        else
        {
            System.out.println("Number of nodes checked = " + vStates.size());
        }
        
        
        // Add current state to visited states.
        vStates.add(currentState);        
        
        // Find the set of possible children of current state.
        List<State> children = currentState.getChildren();
        for(State c : children)
        {
            // if a children C is not in the visited states 
            // again call DFS on current child and visited States.
            if(!vStates.contains(c))
            {
                // Make clone of visited states.
                java.util.Set<State> clonedVStates = new java.util.HashSet<State>(vStates);
                dfs(c, clonedVStates);
            }
        }
        vStates=null;
    }
}


Now extend the SolveProblem class and override the abstract method to give your implementation as follows
And use the methods to solve your problem:

Extend SolveProblem class and use

package solution;

import mystate.SlidingState;
import mystate.State;

/**
 *
 * @author Yogi
 */
public class Solve15Puzzle extends SolveProblem {

    public static void main(String[] args)
    {
        //Get the jvm heap size.
        long heapSize = Runtime.getRuntime().totalMemory();
         
        //Print the jvm heap size.
        System.out.println("Heap Size = " + heapSize/(1024*1024) + " MB");        
        SolveProblem n = new Solve15Puzzle();
        n.bfs();
    }

    @Override
    public State getStateObject() {
//    int[][] currentState = {{8,5,0,6}, {2,1,9,4}, {14,10,7,11},{13,3,15,12}};    
    int[][] currentState = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12},{0,13,14,15}};    
//    int[][] currentState = {{1,2,3,4}, {5,6,7,8}, {9,0,10,12},{13,14,11,15}}; 
    // The following problem needs minimum 6 moves to solve. But DFS algo takes around 40 moves...
//    int[][] currentState = {{1,2,3,4}, {5,6,11,7}, {9,10,0,8},{13,14,15,12}};        
//        int[][] currentState = {{1,2,3,4}, {5,6,7,8}, {9,0,10,12},{13,14,11,15}};         
//        int[][] currentState = {{8,5,0,6}, {2,1,9,4}, {14,10,7,11},{13,3,15,12}};
        return new SlidingState(currentState);
    }
}

Tuesday, September 10, 2013

Real time examples of Design patterns being used by Java

I am very keen to learn what all design patterns are being used by java code.

So here I am going to list them one by one.. I'll keep on updating this article as and when I learn more about design patterns...

To begin with.. Lets learn something about strategy design pattern.

Strategy Design Pattern Examples

  • There are common situations when classes differ only in their behavior. For this cases is a good idea to isolate the algorithms in separate classes in order to have the ability to select different algorithms at runtime.
    Intent
  • Define a family of algorithms, encapsulate each one, and make them interchangeable. Strategy lets the algorithm vary independently from clients that use it.
You must have seen how we create threads in Java... We make a class implement Runnable and override its run method. And then use that class's object as an argument to Thread class constructor.
class xx implements Runnable  
{  
       @Override
       public void run()  
       {  
               System.out.println("Running xx thread...");  
       }  
}  
class MyThread extends Thread
{
    @Override
    public void run()
    {
        System.out.println("mythread");
    }
}
public class Main
{ 
    public static void main(String args[])
    {
        xx r = new xx(); 
        // Encapsulate what varies.. Note that 
        // Here the behavior of the run method varies...
        // That is why it has been moved out of the Thread class.. 
        Thread t = new Thread(r);  
        // Now that we have overridden the run method of Runnable interface
        // and passed the object of class implementing it to the constructor of 
        // Thread class...  
        // In this case, the run method of r object will get invoked 
        // by the start method.
        t.start();  

        Thread s = new MyThread();
        // As we have now overriden the method of the Thread
        // class itself, the start method will invoke the overridden
        // run method.
        // Here polymorphysm is attained by inheritance and not by
        // encapsulation.. This is a weaker strategy than the first one.
        s.start();


    }
}
Well, if you see the definition of run() method in Thread class I think you'll agree to what I have tried to explain above... Here is the definition in Thread class
/**
* If this thread was constructed using a separate 
* <code>Runnable</code> run object, then that 
* <code>Runnable</code> object's <code>run</code> method is called; 
* otherwise, this method does nothing and returns. 
* <p>
* Subclasses of <code>Thread</code> should override this method. 
*
* @see     #start()
* @see     #stop()
* @see     #Thread(ThreadGroup, Runnable, String)
*/
public void run() 
{
    if (target != null) 
    {
        target.run();
    }
}
And if you look at the second way of creating a Thread, i.e. extending a Thread class... In that case the start method just invokes the run method... And because we have overridden the run method of Thread class, the default implementation of Thread's run method will not get invoked, instead the implementation that we have given in the child class will get invoked.
/**
     * Causes this thread to begin execution; the Java Virtual Machine 
     * calls the <code>run</code> method of this thread. 
     * <p>
     * The result is that two threads are running concurrently: the 
     * current thread (which returns from the call to the 
     * <code>start</code> method) and the other thread (which executes its 
     * <code>run</code> method). 
     * <p>
     * It is never legal to start a thread more than once.
     * In particular, a thread may not be restarted once it has completed
     * execution.
     *
     * @exception  IllegalThreadStateException  if the thread was already
     *               started.
     * @see        #run()
     * @see        #stop()
     */
    public synchronized void start()
    {
       ..... 
    }
Collections.sort(myCollections, myComparator);
This is another example of strategy design pattern, which I can think of.. As we are passing the behavior of comparison at run-time.

Sunday, September 8, 2013

The water jug problem

We have three water jugs, and each can hold 3oz., 5oz., and 8oz. of water, respectively.
Without the possibility of water spilling when poured from one jug to another, and given that the jugs have no calibration, how do we divide the 8oz. of water equally among two jugs?


We will define a class named State holding the capacity of A and B jars.
It should be noted that only 2 jars are sufficient to define a state, as water held in third jar can be calculated by subtracting the sum of two from the total.

Define class State like this...

package mystate;
import bfs.threejugproblem.NotSupportedException;
import java.util.ArrayList;
import java.util.List;
public class State
{
    int a=0;//3
    int b=0;//5
    int c=8;//8

    public State(int a, int b)
    {
        this.a=a;
        this.b=b;
        this.c=8-a-b;
    }
    public boolean isGoal()
    {
        return (b==4 && c==4);
    }
    public boolean equals(Object xx)
    {
        State x = (State) xx;
        if(this.a==x.a && this.b==x.b && this.c==x.c)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    public int hashCode()
    {
        return 8;
    }
    public List<State> getChildren() 
    {
        List<State> children = new ArrayList<State>();
        // a -> b
        if(a!=0 && b!=5)// if a is not empty
        {
            if(a+b<=5)
            {
                children.add(new State(0, a+b));
            }
            else
            {
                children.add(new State(a+b-5,5));
            }
        }
        //a->c
        if(a!=0 && c!=8)
        {
            // We are pouring completely from a to c
            // a will be 0
            // b will be 8-a-c
            // c will be a+c
            children.add(new State(0, 8-a-c));
        }
        //b->a
        if(b!=0 && a!=3)
        {
            if(a+b<=3)
            {
                children.add(new State(a+b, 0));
            }
            else
            {
                children.add(new State(3, a+b-3));
            }
        }
        // b->c
        if(b!=0 && c!=8)
        {
            // We are pouring completely from b to c
            // a will be 8-b-c
            // b will be 0
            // c will be b+c
            children.add(new State(8-b-c, 0));            
        }
        //c->a
        if(c!=0 && a!=3)
        {
            if(c+a<=3)
            {
                children.add(new State(c+a, 8-c-a));
            }
            else
            {
                    // a will be full i.e. 3 liters
                    // b will be 8-c-a
                    // c will be c+a-3
                    children.add(new State(3, 8-c-a));
                
            }
        }
        // c->b
        if(c!=0 && b!=5)
        {
            if(c+b<=5)
            {
                children.add(new State(8-c-b , c+b));
            }
            else
            {
                children.add(new State(8-c-b, 5));
            }
        }
        return children;
    }
    @Override
    public String toString()
    {
        return "{"+a+","+b+","+c+"}";
    }
}

Depth First Search Algorithm

public class DFSThreeJugProblem 
{
    public static void main(String[] args)
    {
        State currentState = new State(0,0);
        List<State> visitedStates=new ArrayList<State>();  
        // Check if the current State has a solution
        // given a set of visited States.
        dfs(currentState, visitedStates);
    }
    public static void dfs(State currentState, List<State> vStates)
    {
        // if it is GOAL
        if(currentState.isGoal())
        {
            // That's it we are done.
            for(State v : vStates)
            {
                System.out.println(v);
                System.out.println(currentState);
            }
            System.exit(0);            
        }
        
        // if visisted state contains currentState, then just return.
        // This is the wrong branch, and we need not traverse it further.
        if(vStates.contains(currentState))
            return;
        
        // Add current state to visited states.
        vStates.add(currentState);        
        
        // Make clone of visited states.
        List<State> clonedVStates = new ArrayList<State>(vStates);
        // Find the set of possible children of current state.
        List<State> children = currentState.getChildren();
        for(State c : children)
        {
            // if a children C is not in the visited states 
            // again call DFS on current child and visited States.
            if(!clonedVStates.contains(c))
            {
                dfs(c, clonedVStates);
            }
        }
    }
}

Breadth First Search algorithm...

public class BFSThreeJugProblem 
{
    private static List<State> visitedStates=new ArrayList<State>();
    private static Queue<State> stateQueue = new LinkedList<State>();
    public static void main(String[] args) throws NotSupportedException 
    {
        State currentState = new State(0,0);
        // Add current state to state Queue.
        stateQueue.add(currentState);
        do
        {
            // Get the first Element from Queue.
            State firstElementInQueue = stateQueue.peek();
            // If the first Element is the Goal
            // We are done.
            if(firstElementInQueue.isGoal())
            {
                for(State p : visitedStates)
                {
                    System.out.println(p.toString());
                }
                // There is no recursion here, so simple return would do.
                return;
            }
            else
            {
                // Add firstElement to visited States
                visitedStates.add(firstElementInQueue);    
                // Get the children of first element
                List<State> children = firstElementInQueue.getChildren();
                for(State v : children)
                {
                    // if children has not already been visited.
                    if(!visitedStates.contains(v))
                    {
                        // add the child to state Queue.
                        stateQueue.add(v);
                    }
                }
                // Remove the first element from state queue.
                stateQueue.remove(firstElementInQueue);
            }
            // do this till state queue is empty.
        }while(!stateQueue.isEmpty());
    }
}