Thursday, November 20, 2014

Coding Interview Question : Given a string (for example: "a?bc?def?g"), write a program to generate all the possible strings by replacing ? with 0 and 1.

Question: Given a string (for example: "a?bc?def?g"), write a program to generate all the possible strings by replacing ? with 0 and 1.

Example:

Input : a?b?c?
Output: a0b0c0, a0b0c1, a0b1c0, a0b1c1, a1b0c0, a1b0c1, a1b1c0, a1b1c1.

Algorithm:
1. Count the number of '?'s in the string.
2. Initialize a char [] of that size.
3. Insert the possible sequences of 0s and 1s in the array.
4. Everytime when the array is filled, replace ?s in the string with the contents of the filled array.

Source:

public class Code{ 
    public static void print(String s, char[] a){ 
        System.out.println();
        
        int j = 0;
        for(int i=0;i<s.length();++i)
            if(s.charAt(i)=='?')System.out.print(a[j++]);
            else System.out.print(s.charAt(i)); 
    }
    
    public static void process(String string, char[] a, int len, int cIndex){
        if(cIndex == len) {print(string, a); return;} 
    
        a[cIndex] = '0';
        process(string, a, len, cIndex+1);
        a[cIndex] = '1';
        process(string, a, len, cIndex+1);
    }
    
    public static void input(String string){
        int l = 0;
        for(int i = 0;i<string.length(); ++i)
            if(string.charAt(i)=='?') l++;
        char a[] = new char[l]; 
        process(string, a, l, 0);
    }
    
    public static void main(String[] args){
        String s = "?c?o?d?e??";
        input(s); 
        s = "???";
        input(s);
    }
}

Output:

000
001
010
011
100
101
110
111

0c0o0d0e00
0c0o0d0e01
0c0o0d0e10
0c0o0d0e11
0c0o0d1e00
0c0o0d1e01
0c0o0d1e10
0c0o0d1e11
0c0o1d0e00
0c0o1d0e01
0c0o1d0e10
0c0o1d0e11
0c0o1d1e00
0c0o1d1e01
0c0o1d1e10
0c0o1d1e11
0c1o0d0e00
0c1o0d0e01
0c1o0d0e10
0c1o0d0e11
0c1o0d1e00
0c1o0d1e01
0c1o0d1e10
0c1o0d1e11
0c1o1d0e00
0c1o1d0e01
0c1o1d0e10
0c1o1d0e11
0c1o1d1e00
0c1o1d1e01
0c1o1d1e10
0c1o1d1e11
1c0o0d0e00
1c0o0d0e01
1c0o0d0e10
1c0o0d0e11
1c0o0d1e00
1c0o0d1e01
1c0o0d1e10
1c0o0d1e11
1c0o1d0e00
1c0o1d0e01
1c0o1d0e10
1c0o1d0e11
1c0o1d1e00
1c0o1d1e01
1c0o1d1e10
1c0o1d1e11
1c1o0d0e00
1c1o0d0e01
1c1o0d0e10
1c1o0d0e11
1c1o0d1e00
1c1o0d1e01
1c1o0d1e10
1c1o0d1e11
1c1o1d0e00
1c1o1d0e01
1c1o1d0e10
1c1o1d0e11
1c1o1d1e00
1c1o1d1e01
1c1o1d1e10
1c1o1d1e11

Saturday, November 15, 2014

Determination of Day of the Week for a given Date

Input: Given a date in DD-MM-YYYY format, determine the day of the week for this date.

Input: 15-11-2014
Output: Saturday

Algorithm:

I. Assign 

0 to Sunday
1 to Monday
2 to Tuesday
3 to Wednesday
4 to Thursday
5 to Friday
6 to Saturday

II. 
The number of days which do not form a week are called odd days.
For example in a month of 30 days, 30/7 = 4 weeks and 2 odd days. [30 = 4*7+2]

A leap year has 366 days, odd days = 2
A non leap year has 365 days, odd days = 1

100 years have 5 odd days.
200 years have 3 odd days.
300 years have 1 odd days.
400 years have 0 odd days.

III.
Lets say we are given a date 31st March 1789.
First we find the number of odd days in 1788 years. Then we find the number of odd days from 1st Jan to 31st March of 1789. Add the results to get the total number of odd days. Next take oddDays % 7 to get the day of the week on 31st March 1789.

Given an year say 2014, try to break 2013 like

2013 = 400*5 + 13
         = 0*5 odd days + (3 leap years * 2 + 10 non-leap years * 1) odd days
         = 16 odd days

Now lets say we want to calculate the day for 4th March 2014

January has 31 days.
February has 29 days if the year is leap (2014 is not). So we take 28 days for February.

Total number of days before March 1, = 59

Current date = 4th
Total number of days = 59+4 = 63 days

Number of odd days in 63 days = 0 days

So total number of odd days = 16+0 = 16.
Day of the week = 16 % 7 = 2.

2 is for Tuesday.
The day is Tuesday.

Source:

public class DayofTheWeek {
    
    public static boolean isLeap(int year){
        if(year % 4 == 0){
            if(year % 100 == 0){
                return year%400==0; 
            }else return true;
        }else return false;
    }
    
    public static int getDays(int day, int month, int year){
        int days=0; 
        for(int i=1;i<month;++i){
            if(i==2){ if(isLeap(year)) days+= 29; else days+=28;}
            else if(i%2==0){ if(i<7)days += 30; else days+= 31;}
            else if(i%2==1){ if(i<=7)days += 31; else days+=30;}
        }
        days+=day;   
        return days;
    }
    
    public static int returnDay(int day, int month, int year){
        //Get number of days between the start of the year and the current date
        int daysInCurrentYear = getDays(day, month, year); 
        
        int oddDays = 0;
        year--;
        
        int n400s = year/400;
        
        if(n400s >= 1)
            year -= 400 * n400s; 
          
        if(year/300 == 1){
            year -= 300;
            oddDays += 1;
        }else if(year/200 == 1){
            year -= 200;
            oddDays += 3;
        }else if(year/100 > 0){
            year -= 100;
            oddDays += 5;
        } 
        
        int leapYears = year/4;
        int nonLeapYears = year-leapYears;
        
        oddDays += (leapYears * 2 + nonLeapYears);   
        oddDays += (daysInCurrentYear % 7);   
        
        return oddDays % 7;
    }
    
    public static void main(String[] args){   
        System.out.println(returnDay(4, 3, 2014));
    }
}

Output:
2

Sunday, November 9, 2014

Spiral Printing of 2-D Array Contents

This program prints a 2-D array's contents spirally.

Input:

            {1, 2, 3, 4,},
            {3, 4, 5, 5,},
            {2, 7, 6, 6,},
            {1, 9, 8, 7,}

Output:

1234567891234567

Algorithm:

1.  Four variables top, bottom, left and right keep track of the index to print.
2. Print top row, increment top.
3. Print the rightmost column, decrement right.
4. Print the bottom row, decrement bottom.
5. Print the first column, decrement increment left.
6. Of course, avoiding the common index.
7. And checking some constraints at each print loop.

Code:

public class SpiralPrint {

    static void printSpiral(int[][] array) {
        System.out.println();
        int top = 0;
        int bottom = array.length - 1;
        int left = 0;
        int right = array[0].length - 1;
      
        while (bottom >= top || right >= left) {
            for (int i = left; i <= right && bottom >= top; ++i) {
                System.out.print(array[top][i]);
            }
            top++;
            for (int i = top; i <= bottom && left <= right; ++i) {
                System.out.print(array[i][right]);
            }
            right--;
            for (int i = right; i >= left && bottom >= top; --i) {
                System.out.print(array[bottom][i]);
            }
            bottom--;
            for (int i = bottom; i >= top && left <= right; --i) {
                System.out.print(array[i][left]);
            }
            left++;
        }
        System.out.println();
    }

    public static void main(String[] args) {

        //test 1
        int[][] array = {{0, 1, 2, 3, 4},
                         {9, 8, 7, 6, 5}};
        printSpiral(array);
        
        //test 2
        array = new int[][]{
            {1, 2, 3, 4, 5},
            {0, 9, 8, 7, 6},
            {1, 2, 3, 4, 5},};
        printSpiral(array);
        
        //test 3
        array = new int[][]{
            {1, 0, 1},
            {2, 9, 2},
            {3, 8, 3},
            {4, 7, 4},
            {5, 6, 5}};
        printSpiral(array);
        
        //test 4
        array = new int[][]{
            {1},
            {2},
            {3},
            {4}
        };
        printSpiral(array);
        
        //test 5
        array = new int[][]{
            {1, 2, 3, 4}
        };
        printSpiral(array);

        //test 6
        array = new int[][]{
            {1, 2, 3, 4,},
            {3, 4, 5, 5,},
            {2, 7, 6, 6,},
            {1, 9, 8, 7,},
        };
        printSpiral(array);
        
        //test 7
        array = new int[][]{
            {1, 2, 3, 4,},
            {3, 4, 5, 5,},
            {2, 7, 6, 6,},
            {1, 9, 8, 7,},
            {0, 0, 0, 0,},
        };
        printSpiral(array);
        
        //test 8
        array = new int[][]{
            {1, 2, 3, 4,},
            {3, 4, 5, 5,},
        };
        printSpiral(array);
        
        //test 9
        array = new int[][]{
            {1, 2},
            {2, 3},
            {3, 4},
            {4, 5}
        };
        printSpiral(array);
    }  
}

Output:

0123456789

123456543210987

101234565432987

1234

1234

1234567891234567

12345670000123456897

12345543

12345432

Saturday, November 8, 2014

Alpha Beta pruning - Minimax Algorithm for Tic Tac Toe [Java]

I found this tutorial very helpful for understanding alpha-beta pruning:


What needs to be done:

1. Initially alpha and beta variables are set to Integer.MIN_VALUE and Integer.MAX_VALUE respectively to represent -infinity and +infinity

2. Traverse (Depth First) the whole tree (you can also set the depth in the code by setting the value of uptoDepth variable.

3. Traverse to the left (DFS) (intially from the root) until either leaf node (with or without the depth constraint) has been reached.

4. After every child node's evaluation, update parent's alpha or beta if required.

5. Evaluate other sibling only of beta > alpha. If that is not the case, we need to do pruning.

6. If beta <= alpha : We must return a value from the function alphaBetaMinimax(params) that sets the score value for a node-
    return Integer.MIN_VALUE if parent node (of the node being pruned) is a Max. Max will always     select the highest, so we  assign -infinity to the node we do not want to evaluate further. 

    return Integer.MAX_VALUE if parent node is a Min. Min will always select the minimum, so we       assign +infinity to the node we do not want to evaluate further so that it doesn't interfere with the       optimal result we've already found previously.

7. If Integer.MIN_VALUE or Integer.MAX_VALUE has been returned for a node, we know that pruning has been done and we don't want to evaluate more siblings, so we break out of the evaluation loop for that parent.

8. Beta for the root of the tree remains Infinity while the children are being evaluated. 

I've written this code in Java for Tic-Tac-Toe (Minimax + Alpha Beta pruning) :

Source:

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

class Point {

    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + x + ", " + y + "]";
    }
}

class PointsAndScores {

    int score;
    Point point;

    PointsAndScores(int score, Point point) {
        this.score = score;
        this.point = point;
    }
}

class Board {

    List<Point> availablePoints;
    Scanner scan = new Scanner(System.in);
    int[][] board = new int[3][3]; 

    List<PointsAndScores> rootsChildrenScore = new ArrayList<>();

    public int evaluateBoard() {
        int score = 0;

        //Check all rows
        for (int i = 0; i < 3; ++i) {
            int blank = 0;
            int X = 0;
            int O = 0;
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == 0) {
                    blank++;
                } else if (board[i][j] == 1) {
                    X++;
                } else {
                    O++;
                }

            } 
            score+=changeInScore(X, O); 
        }

        //Check all columns
        for (int j = 0; j < 3; ++j) {
            int blank = 0;
            int X = 0;
            int O = 0;
            for (int i = 0; i < 3; ++i) {
                if (board[i][j] == 0) {
                    blank++;
                } else if (board[i][j] == 1) {
                    X++;
                } else {
                    O++;
                } 
            }
            score+=changeInScore(X, O);
        }

        int blank = 0;
        int X = 0;
        int O = 0;

        //Check diagonal (first)
        for (int i = 0, j = 0; i < 3; ++i, ++j) {
            if (board[i][j] == 1) {
                X++;
            } else if (board[i][j] == 2) {
                O++;
            } else {
                blank++;
            }
        }

        score+=changeInScore(X, O);

        blank = 0;
        X = 0;
        O = 0;

        //Check Diagonal (Second)
        for (int i = 2, j = 0; i > -1; --i, ++j) {
            if (board[i][j] == 1) {
                X++;
            } else if (board[i][j] == 2) {
                O++;
            } else {
                blank++;
            }
        }

        score+=changeInScore(X, O);

        return score;
    }
    private int changeInScore(int X, int O){
        int change;
        if (X == 3) {
            change = 100;
        } else if (X == 2 && O == 0) {
            change = 10;
        } else if (X == 1 && O == 0) {
            change = 1;
        } else if (O == 3) {
            change = -100;
        } else if (O == 2 && X == 0) {
            change = -10;
        } else if (O == 1 && X == 0) {
            change = -1;
        } else {
            change = 0;
        } 
        return change;
    }
    
    //Set this to some value if you want to have some specified depth limit for search
    int uptoDepth = -1;
    
    public int alphaBetaMinimax(int alpha, int beta, int depth, int turn){
        
        if(beta<=alpha){ System.out.println("Pruning at depth = "+depth);if(turn == 1) return Integer.MAX_VALUE; else return Integer.MIN_VALUE; }
        
        if(depth == uptoDepth || isGameOver()) return evaluateBoard();
        
        List<Point> pointsAvailable = getAvailableStates();
        
        if(pointsAvailable.isEmpty()) return 0;
        
        if(depth==0) rootsChildrenScore.clear(); 
        
        int maxValue = Integer.MIN_VALUE, minValue = Integer.MAX_VALUE;
        
        for(int i=0;i<pointsAvailable.size(); ++i){
            Point point = pointsAvailable.get(i);
            
            int currentScore = 0;
            
            if(turn == 1){
                placeAMove(point, 1); 
                currentScore = alphaBetaMinimax(alpha, beta, depth+1, 2);
                maxValue = Math.max(maxValue, currentScore); 
                
                //Set alpha
                alpha = Math.max(currentScore, alpha);
                
                if(depth == 0)
                    rootsChildrenScore.add(new PointsAndScores(currentScore, point));
            }else if(turn == 2){
                placeAMove(point, 2);
                currentScore = alphaBetaMinimax(alpha, beta, depth+1, 1); 
                minValue = Math.min(minValue, currentScore);
                
                //Set beta
                beta = Math.min(currentScore, beta);
            }
            //reset board
            board[point.x][point.y] = 0; 
            
            //If a pruning has been done, don't evaluate the rest of the sibling states
            if(currentScore == Integer.MAX_VALUE || currentScore == Integer.MIN_VALUE) break;
        }
        return turn == 1 ? maxValue : minValue;
    }  

    public boolean isGameOver() {
        //Game is over is someone has won, or board is full (draw)
        return (hasXWon() || hasOWon() || getAvailableStates().isEmpty());
    }

    public boolean hasXWon() {
        if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 1) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 1)) {
            //System.out.println("X Diagonal Win");
            return true;
        }
        for (int i = 0; i < 3; ++i) {
            if (((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 1)
                    || (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 1))) {
                // System.out.println("X Row or Column win");
                return true;
            }
        }
        return false;
    }

    public boolean hasOWon() {
        if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 2) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 2)) {
            // System.out.println("O Diagonal Win");
            return true;
        }
        for (int i = 0; i < 3; ++i) {
            if ((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 2)
                    || (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 2)) {
                //  System.out.println("O Row or Column win");
                return true;
            }
        }

        return false;
    }

    public List<Point> getAvailableStates() {
        availablePoints = new ArrayList<>();
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == 0) {
                    availablePoints.add(new Point(i, j));
                }
            }
        }
        return availablePoints;
    }

    public void placeAMove(Point point, int player) {
        board[point.x][point.y] = player;   //player = 1 for X, 2 for O
    }

    public Point returnBestMove() {
        int MAX = -100000;
        int best = -1;

        for (int i = 0; i < rootsChildrenScore.size(); ++i) {
            if (MAX < rootsChildrenScore.get(i).score) {
                MAX = rootsChildrenScore.get(i).score;
                best = i;
            }
        }

        return rootsChildrenScore.get(best).point;
    }

    void takeHumanInput() {
        System.out.println("Your move: ");
        int x = scan.nextInt();
        int y = scan.nextInt();
        Point point = new Point(x, y);
        placeAMove(point, 2);
    }

    public void displayBoard() {
        System.out.println();

        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();

        }
    } 
    
    public void resetBoard() {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                board[i][j] = 0;
            }
        }
    } 
}

public class AlphaBetaMinimaxTTT {
 
    public static void main(String[] args) { 
        Board b = new Board();
        Random rand = new Random();

        b.displayBoard();

        System.out.println("Who's gonna move first? (1)Computer (2)User: ");
        int choice = b.scan.nextInt();
        if (choice == 1) {
            Point p = new Point(rand.nextInt(3), rand.nextInt(3));
            b.placeAMove(p, 1);
            b.displayBoard();
        }

        while (!b.isGameOver()) {
            System.out.println("Your move: ");
            Point userMove = new Point(b.scan.nextInt(), b.scan.nextInt());

            b.placeAMove(userMove, 2); //2 for O and O is the user
            b.displayBoard();
            if (b.isGameOver()) break;
            
            b.alphaBetaMinimax(Integer.MIN_VALUE, Integer.MAX_VALUE, 0, 1);
            for (PointsAndScores pas : b.rootsChildrenScore) 
                System.out.println("Point: " + pas.point + " Score: " + pas.score);
            
            b.placeAMove(b.returnBestMove(), 1);
            b.displayBoard();
        }
        if (b.hasXWon()) {
            System.out.println("Unfortunately, you lost!");
        } else if (b.hasOWon()) {
            System.out.println("You win!");
        } else {
            System.out.println("It's a draw!");
        }
    }
}

Output:

0 0 0
0 0 0
0 0 0
Who's gonna move first? (1)Computer (2)User:
2
Your move:
2 2

0 0 0
0 0 0
0 0 2
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 5
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 5
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 4
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 5
Pruning at depth = 7
Pruning at depth = 5
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 4
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 4
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 4
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 5
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 5
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 5
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 5
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 6
Pruning at depth = 4
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 7
Pruning at depth = 5
Pruning at depth = 7
Pruning at depth = 5
Pruning at depth = 7
Pruning at depth = 6
Pruning at depth = 7
Pruning at depth = 5
Pruning at depth = 6
Pruning at depth = 7
... more
Point: [0, 0] Score: -90
Point: [0, 1] Score: -90
Point: [0, 2] Score: -90
Point: [1, 0] Score: -91
Point: [1, 1] Score: 0
Point: [1, 2] Score: 0
Point: [2, 0] Score: 0
Point: [2, 1] Score: 0

0 0 0
0 1 0
0 0 2
Your move:
0 0

2 0 0
0 1 0
0 0 2
Pruning at depth = 5
Pruning at depth = 5
Pruning at depth = 5
Pruning at depth = 5
Pruning at depth = 4
Pruning at depth = 5
Pruning at depth = 4
Pruning at depth = 5
Pruning at depth = 5
Pruning at depth = 3
Pruning at depth = 5
Pruning at depth = 3
Pruning at depth = 5
Pruning at depth = 5
Pruning at depth = 5
Pruning at depth = 4
Pruning at depth = 5
Pruning at depth = 5
Pruning at depth = 5
Pruning at depth = 5
Pruning at depth = 5
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 5
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 3
Pruning at depth = 5
Pruning at depth = 4
Pruning at depth = 3
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 2
Pruning at depth = 5
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 3
Pruning at depth = 4
Pruning at depth = 5
Pruning at depth = 4
Pruning at depth = 5
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 2
Pruning at depth = 5
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 5
Pruning at depth = 5
Pruning at depth = 3
Pruning at depth = 4
Pruning at depth = 5
Pruning at depth = 4
Pruning at depth = 5
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 2
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 2
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 4
Pruning at depth = 2
Point: [0, 1] Score: 0
Point: [0, 2] Score: 0
Point: [1, 0] Score: 0
Point: [1, 2] Score: 0
Point: [2, 0] Score: -90
Point: [2, 1] Score: 0

2 1 0
0 1 0
0 0 2
Your move:
2 1

2 1 0
0 1 0
0 2 2
Pruning at depth = 3
Pruning at depth = 3
Point: [0, 2] Score: -109
Point: [1, 0] Score: -100
Point: [1, 2] Score: -100
Point: [2, 0] Score: 0

2 1 0
0 1 0
1 2 2
Your move:
0 2

2 1 2
0 1 0
1 2 2
Point: [1, 0] Score: -100
Point: [1, 2] Score: 0

2 1 2
0 1 1
1 2 2
Your move:
1 0

2 1 2
2 1 1
1 2 2
It's a draw!

Monday, November 3, 2014

Listing all the Constructors and Methods of a Class/Interface using Reflection API (Java)

The reflection API can be used to list all the available public methods and constructors of a class/interface.

We will use java.util.regex package to display

public int indexOf(String,int)

instead of 

public int java.lang.String.indexOf(java.lang.String,int)

1. Declare a Class variable (say c).
2. Assign to it the result of Class.forName("Fully.Qualified.ClassName")

3. Call c.getDeclaredConstructors() to get an array of Constructor objects.
4. Apply regex filter to shorten class names.
5. Display results to the user.

6. Call c.getDeclaredMethods() to get an array of Method objects.
7. Apply regex filter to shorten class names.
8. Display results to the user. 

c.getConstructors() only provides you the public constructors whereas c.getDeclaredConstructors() provides you all (public, private, protected, package(default access)) constructors.

Same goes with c.getMethods() and c.getDeclaredMethods()

Source:

import java.lang.reflect.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class ReflectionMethods {
    public static void main(String[] args)throws Exception{
        
        Class c = Class.forName("java.lang.String");
        
        //Printing Constructors
        System.out.println("Listing contructors: ");
        
        Constructor[] constructors = c.getDeclaredConstructors(); 
        
        //Clipping off "java.lang." etc.  (Full class name prefixes)
        Pattern p1 = Pattern.compile(" ([a-zA-Z]+\\.)+");  
        //Clipping off "(java.lang." etc. (Full class name prefixes in arguments)
        Pattern p2 = Pattern.compile("\\(([a-zA-Z]+\\.)+");  
        //Clipping off ",java.lang." etc. (Commas in multiple arguments)
        Pattern p3 = Pattern.compile(",([a-zA-Z]+\\.)+");    
        Matcher m;
        
        for(Constructor constructor:constructors){
            String constructorString = constructor.toString();
            m = p1.matcher(constructorString);  
            constructorString = m.replaceAll(" ");
            m = p2.matcher(constructorString);
            constructorString = m.replaceAll("(");
            m = p3.matcher(constructorString);
            constructorString = m.replaceAll(", ");
            System.out.println(constructorString);
        }
        
        Method[] methods = c.getDeclaredMethods(); 
        p1 = Pattern.compile(" ([a-zA-Z]+\\.)+");
        p2 = Pattern.compile("\\(([a-zA-Z]+\\.)+"); 
        p3 = Pattern.compile(",([a-zA-Z]+\\.)+");
        
        
        //Printing Methods
        System.out.println("\n\nListing Class Methods: ");
        for(Method method:methods){
            String methodString = method.toString();
            m = p1.matcher(methodString);  
            methodString = m.replaceAll(" ");
            m = p2.matcher(methodString);
            methodString = m.replaceAll("(");
            m = p3.matcher(methodString);
            methodString = m.replaceAll(", ");
            System.out.println(methodString);
        } 
    }
}

Output:

Listing contructors: 
public String(byte[],int,int)
public String(byte[], Charset)
public String(byte[], String) throws UnsupportedEncodingException
public String(byte[],int,int, Charset)
public String(byte[],int,int, String) throws UnsupportedEncodingException
java.lang.String(char[],boolean)
public String(StringBuilder)
public String(StringBuffer)
public String(byte[])
public String(int[],int,int)
public String()
public String(char[])
public String(String)
public String(char[],int,int)
public String(byte[],int)
public String(byte[],int,int,int)


Listing Class Methods: 
public boolean equals(Object)
public String toString()
public int hashCode()
public int compareTo(String)
public int compareTo(Object)
public int indexOf(String,int)
public int indexOf(String)
public int indexOf(int,int)
public int indexOf(int)
static int indexOf(char[],int,int,char[],int,int,int)
static int indexOf(char[],int,int, String,int)
public static String valueOf(int)
public static String valueOf(long)
public static String valueOf(float)
public static String valueOf(boolean)
public static String valueOf(char[])
public static String valueOf(char[],int,int)
public static String valueOf(Object)
public static String valueOf(char)
public static String valueOf(double)
public char charAt(int)
private static void checkBounds(byte[],int,int)
public int codePointAt(int)
public int codePointBefore(int)
public int codePointCount(int,int)
public int compareToIgnoreCase(String)
public String concat(String)
public boolean contains(CharSequence)
public boolean contentEquals(CharSequence)
public boolean contentEquals(StringBuffer)
public static String copyValueOf(char[])
public static String copyValueOf(char[],int,int)
public boolean endsWith(String)
public boolean equalsIgnoreCase(String)
public static String format(Locale, String, Object[])
public static String format(String, Object[])
public void getBytes(int,int,byte[],int)
public byte[] getBytes(Charset)
public byte[] getBytes(String) throws UnsupportedEncodingException
public byte[] getBytes()
public void getChars(int,int,char[],int)
void getChars(char[],int)
private int indexOfSupplementary(int,int)
public native String intern()
public boolean isEmpty()
public static String join(CharSequence, CharSequence[])
public static String join(CharSequence, Iterable)
public int lastIndexOf(int)
public int lastIndexOf(String)
static int lastIndexOf(char[],int,int, String,int)
public int lastIndexOf(String,int)
public int lastIndexOf(int,int)
static int lastIndexOf(char[],int,int,char[],int,int,int)
private int lastIndexOfSupplementary(int,int)
public int length()
public boolean matches(String)
private boolean nonSyncContentEquals(AbstractStringBuilder)
public int offsetByCodePoints(int,int)
public boolean regionMatches(int, String,int,int)
public boolean regionMatches(boolean,int, String,int,int)
public String replace(char,char)
public String replace(CharSequence, CharSequence)
public String replaceAll(String, String)
public String replaceFirst(String, String)
public String[] split(String)
public String[] split(String,int)
public boolean startsWith(String,int)
public boolean startsWith(String)
public CharSequence subSequence(int,int)
public String substring(int)
public String substring(int,int)
public char[] toCharArray()
public String toLowerCase(Locale)
public String toLowerCase()
public String toUpperCase()
public String toUpperCase(Locale)
public String trim()

Sunday, November 2, 2014

File Transfer using TCP [Java]

This program sends a file from server to client using the Transmission Control Protocol (TCP).

Server:

import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.OutputStream;
import java.net.InetAddress;
import java.net.ServerSocket;
import java.net.Socket;

public class FileTransferServer { 
    
    public static void main(String[] args) throws Exception {
        //Initialize Sockets
        ServerSocket ssock = new ServerSocket(5000);
        Socket socket = ssock.accept();
        
        //The InetAddress specification
        InetAddress IA = InetAddress.getByName("localhost"); 
        
        //Specify the file
        File file = new File("e:\\data1.bin");
        FileInputStream fis = new FileInputStream(file);
        BufferedInputStream bis = new BufferedInputStream(fis); 
          
        //Get socket's output stream
        OutputStream os = socket.getOutputStream();
                
        //Read File Contents into contents array 
        byte[] contents;
        long fileLength = file.length(); 
        long current = 0;
         
        long start = System.nanoTime();
        while(current!=fileLength){ 
            int size = 10000;
            if(fileLength - current >= size)
                current += size;    
            else{ 
                size = (int)(fileLength - current); 
                current = fileLength;
            } 
            contents = new byte[size]; 
            bis.read(contents, 0, size); 
            os.write(contents);
            System.out.print("Sending file ... "+(current*100)/fileLength+"% complete!");
        }   
        
        os.flush(); 
        //File transfer done. Close the socket connection!
        socket.close();
        ssock.close();
        System.out.println("File sent succesfully!");
    }
}

Client:

import java.io.BufferedOutputStream;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.net.InetAddress;
import java.net.Socket;


public class FileTransferClient { 
    
    public static void main(String[] args) throws Exception{
        
        //Initialize socket
        Socket socket = new Socket(InetAddress.getByName("localhost"), 5000);
        byte[] contents = new byte[10000];
        
        //Initialize the FileOutputStream to the output file's full path.
        FileOutputStream fos = new FileOutputStream("e:\\data2.bin");
        BufferedOutputStream bos = new BufferedOutputStream(fos);
        InputStream is = socket.getInputStream();
        
        //No of bytes read in one read() call
        int bytesRead = 0; 
        
        while((bytesRead=is.read(contents))!=-1)
            bos.write(contents, 0, bytesRead); 
        
        bos.flush(); 
        socket.close(); 
        
        System.out.println("File saved successfully!");
    }
}