Tic-Tac-Toe Game using Java.......

Features - 1.This program always takes constant time for playing a move and       evaluating winning condition.

2.Game can be played on board of any size ,currently I've configured it for max Board size of 10 .

3.Currently only multiplayer mode is implemented ,single player with bot will be implemented soon .

NOTE-  Conventions to play Tic-Tac-Toe game are as follows...
1.When it asked for size of the board enter single digit number for e.g -if you want to play on 3*3 then just enter "3" (without quotes of course) and press "enter".
         
 2.When you want to play a move enter the row and column index of the position separated by a space .
 e.g - If you want to enter a move on first column of first row then just                     enter "1 1" ( without double quotes ) and then press "enter".  

here is the code ...............

       

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.*;

public class TicTacToeProblem {
 static int size;
 static int mode;
 static HashMap < String, ArrayList < String >> player1RowsAndDiagonals = new HashMap < String, ArrayList < String >> (); //to keep track of rows and diagonal formation for player 1 
 static HashMap < String, ArrayList < String >> player2RowsAndDiagonals = new HashMap < String, ArrayList < String >> (); //to keep track of rows and diagonal formation for player 2
 static HashMap < String, ArrayList < String >> player1Columns = new HashMap < String, ArrayList < String >> (); //to keep track of column formation for player 1 
 static HashMap < String, ArrayList < String >> player2Columns = new HashMap < String, ArrayList < String >> (); //to keep track of column formation for player 2 
 static HashSet < String > filledPositions = new HashSet < String > ();

 public static void main(String[] args) throws NumberFormatException,
  IOException {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.println("Please enter the size of board in numeral");
   size = Integer.parseInt(br.readLine());

   while ((size > 10) == true) {
    System.out.println("Max size allowed is 10");
    System.out.println("please re enter the size");
    size = Integer.parseInt(br.readLine());
   }
   System.out.println("please enter playing mode number");
   System.out.println("1.two player");
   System.out.println("2.with bot");
   mode = Integer.parseInt(br.readLine());
   while (mode != 1 && mode != 2) {
    System.out.println("Please enter appropriate choice of mode 1 or 2");
    mode = Integer.parseInt(br.readLine());
   }
   if (mode == 1) {
    System.out.println("Initializing Setup..........");
    multiplayer(size);
   } else
    withBot(size);
   br.close();
  }

 public static void multiplayer(int size) throws IOException {
  String[] playerMove = null;
  String move = null;
  int coordinateX;
  int coordinateY;
  int player;
  int secondDiagonalSum = size + 1;
  int maxMoves = size * size;

  for (int i = 1; i <= size; i++) { //here just initializing arrayLists for each rows and each columns for both players
   ArrayList < String > rowList1 = new ArrayList < String > ();
   ArrayList < String > rowList2 = new ArrayList < String > ();
   ArrayList < String > columnList1 = new ArrayList < String > ();
   ArrayList < String > columnList2 = new ArrayList < String > ();
   player1RowsAndDiagonals.put((new Integer(i).toString()), rowList1);
   player2RowsAndDiagonals.put((new Integer(i).toString()), rowList2);
   player1Columns.put((new Integer(i).toString()), columnList1);
   player2Columns.put((new Integer(i).toString()), columnList2);
  }

  ArrayList < String > player1diag1 = new ArrayList < String > (); //here initializing arrayLists to keep track of both the diagonals for both players
  ArrayList < String > player1diag2 = new ArrayList < String > ();
  ArrayList < String > player2diag1 = new ArrayList < String > ();
  ArrayList < String > player2diag2 = new ArrayList < String > ();

  player1RowsAndDiagonals.put("diag1", player1diag1);
  player1RowsAndDiagonals.put("diag2", player1diag2);
  player2RowsAndDiagonals.put("diag1", player2diag1);
  player2RowsAndDiagonals.put("diag2", player2diag2);

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

  System.out.println("OK,now start playing enter your choices alternatively");

  for (int i = 0; i < maxMoves; i++) {
   if (i % 2 == 0) {
    System.out.println("player 1 turn");
    player = 1;
   } else {
    System.out.println("player 2 turn");
    player = 2;
   }
   move = br.readLine();
   while (filledPositions.contains(move) == true) { //check for already played Move
    System.out.println("this move has been already played please enter another move");
    move = br.readLine();
   }
   filledPositions.add(move);
   playerMove = move.split(" ");
   coordinateX = Integer.parseInt(playerMove[0]);
   coordinateY = Integer.parseInt(playerMove[1]);

   switch (player) {
    case 1:
     if (playerMove[0].equals(playerMove[1])) { //condition for one of the position in diagonal one
      player1RowsAndDiagonals.get("diag1").add(playerMove[1]);
      player1RowsAndDiagonals.get(playerMove[0]).add(playerMove[1]);
      player1Columns.get(playerMove[1]).add(playerMove[0]);

      if ((coordinateX + coordinateY) == secondDiagonalSum) //condition for one of the position in diagonal two 
       player1RowsAndDiagonals.get("diag2").add(playerMove[1]);

      if ((player1Columns.get(playerMove[1]).size() == size) || (player1RowsAndDiagonals.get("diag1").size() == size) || (player1RowsAndDiagonals.get(playerMove[0]).size() == size) || (player1RowsAndDiagonals.get("diag2").size() == size)) {
       System.out.println("Player 1 wins game is finished");
       return;
      }
     } else {
      player1RowsAndDiagonals.get(playerMove[0]).add(playerMove[1]);
      player1Columns.get(playerMove[1]).add(playerMove[0]);

      if ((coordinateX + coordinateY) == secondDiagonalSum)
       player1RowsAndDiagonals.get("diag2").add(playerMove[1]);

      if ((player1Columns.get(playerMove[1]).size() == size) || (player1RowsAndDiagonals.get("diag1").size() == size) || (player1RowsAndDiagonals.get(playerMove[0]).size() == size) || (player1RowsAndDiagonals.get("diag2").size() == size)) {
       System.out.println("Player 1 wins game is finished");
       return;
      }
     }
     break;
    case 2:
     if (playerMove[0].equals(playerMove[1])) {
      player2RowsAndDiagonals.get("diag1").add(playerMove[1]);
      player2RowsAndDiagonals.get(playerMove[0]).add(playerMove[1]);
      player2Columns.get(playerMove[1]).add(playerMove[0]);

      if ((coordinateX + coordinateY) == secondDiagonalSum)
       player2RowsAndDiagonals.get("diag2").add(playerMove[1]);

      if ((player2Columns.get(playerMove[1]).size() == size) || (player2RowsAndDiagonals.get("diag1").size() == size) || (player2RowsAndDiagonals.get(playerMove[0]).size() == size) || (player2RowsAndDiagonals.get("diag2").size() == size)) {
       System.out.println("Player 1 wins game is finished");
       return;
      }
     } else {
      player2RowsAndDiagonals.get(playerMove[0]).add(playerMove[1]);
      player2Columns.get(playerMove[1]).add(playerMove[0]);

      if ((coordinateX + coordinateY) == secondDiagonalSum)
       player2RowsAndDiagonals.get("diag2").add(playerMove[1]);

      if ((player2Columns.get(playerMove[1]).size() == size) || (player2RowsAndDiagonals.get("diag1").size() == size) || (player2RowsAndDiagonals.get(playerMove[0]).size() == size) || (player2RowsAndDiagonals.get("diag2").size() == size)) {
       System.out.println("Player 2 wins game is finished");
       return;
      }
     }
     break;
    default:
     break;
   }
  } //end of loop 
  System.out.println("Match Tie NO one Wins");
 }



 public static void withBot(int size) {
  System.out.println("Working on it, this mode will be added soon till then keep playing multiplayer mode");
  return;
 }
}

       
 

Java Program to find Minimum steps to make an integer from two variables by repeatedly adding them ......

Problem Statement- Harsh just loves numbers and loves to have fun with them . Apparently he has two numbers with him , say X and Y . Both of them are integers . Now from these numbers he wants another number , say L . But he doesn’t know how to derive it and needs your help . Given the two numbers you can add one to another , and you can do this any number of times . For example, you can add X to Y , or Y to X , and this can be done until any combination makes either X equal toL or Y equal to L .

“Well , this might actually lead to a solution”, said Harsh, ”but can you do it in a minimum number of operations ?”.

Just to make this problem a little simple let’s assume both the values of X and Y is 1 .

Input Format:

The first line contains T, the number of test cases. For each test case, the first line contains L ,the value that Harsh wants .

Output Format:

For each test case, output the required minimum number of operations .

Problem Link- ( https://www.hackerearth.com/problem/algorithm/simple-addition )

here is the code ....

       
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class TestClass {
 static int evaluateStrings(int a, int b) {
  if (b == 0 && a != 1) return 100000000;
  if (b == 0 && a == 1) return -1;
  else return (a / b + evaluateStrings(b, a % b));
 }

 public static void main(String[] args) throws IOException {

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String line = br.readLine();
  int N = Integer.parseInt(line);
  for (int i = 1; i <= N; i++) {

   int x = Integer.parseInt(br.readLine());
   int ans = 100000000;
   for (int j = 1; j <= x; j++) {
    int tmp = evaluateStrings(x, j);

    if (tmp < ans) ans = tmp;
   }
   System.out.println(ans);
  }


 }
}

       
 

Longest common subsequence between two strings using Java ..............

here is  the code........

NOTE:- Here the program is printing the length of the longest common           

              subsequence and also the evaluated sequence. 

       
public class LCS {

 public static void main(String[] args) throws Exception {

  Object[] arr = new Object[2];
  arr = evaluateLCS("suman", "paras");
  int t = arr[1].toString().length() - 1;
  System.out.println("length of longest common subsequence is " + Integer.parseInt(arr[0].toString()));
  System.out.println("the required longest subsequence is " + recursion_string(arr[1].toString(), t));
 }

 public static Object[] evaluateLCS(String first, String second) {
  Object[] arr = new Object[2];
  StringBuffer sequence = new StringBuffer();
  int length = 0;
  if (first.length() == 0 || second.length() == 0) {
   arr[0] = new Integer(0);
   arr[1] = "";
   return arr;
  } else {
   if (first.charAt(first.length() - 1) == second.charAt(second
     .length() - 1)) {
    arr = evaluateLCS(first.substring(0, first.length() - 1),
     second.substring(0, second.length() - 1));
    arr[0] = new Integer(1 + Integer.parseInt(arr[0].toString()));
    arr[1] = (Object) sequence.append(
     first.charAt(first.length() - 1)).append(arr[1]);
    return arr;
   } else {
    Object[] arr1 = new Object[2];
    arr = evaluateLCS(first.substring(0, first.length() - 1),
     second);
    arr1 = evaluateLCS(first,
     second.substring(0, second.length() - 1));
    if (Integer.parseInt(arr[0].toString()) >= Integer
     .parseInt(arr1[0].toString()))
     return arr;
    else
     return arr1;
   }

  }

 }

 public static int max(Object[] arr1, Object[] arr2) {
  int max1 = Integer.parseInt(arr1[0].toString());
  int max2 = Integer.parseInt(arr2[0].toString());

  if (max1 >= max2)
   return max1;
  else
   return max2;
 }

 public static String recursion_string(String name, int t) throws Exception {

  if (name.length() == 0) {
   return "";
  }
  if (name.length() == 1) {
   return name;
  }

  String start = name.substring(t);

  String remainder = name.substring(0, t);
  t--;

  return (start + recursion_string(remainder, t));


 }
}

       
 

Breadth First Search of a graph using Java....

NOTE :- while giving input to the adjacency matrix just put "1" against the entry of a[ i ][ j ] if there                  is a path exist between node " i " and " j " or put " 0 " otherwise .

Enter the number of nodes in the graph
4
Enter the adjacency matrix
0 1 0 1
0 0 1 0
0 1 0 1
0 0 0 1
Enter the source for the graph
1
The BFS traversal of the graph is 
1 2 4 3

so here is the code .....

       
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class BFS {
 private Queue < Integer > queue;
 public BFS() {
  queue = new LinkedList < Integer > ();
 }
 public void bfs(int adjacency_matrix[][], int source) {
  int number_of_nodes = adjacency_matrix[source].length - 1;
  int[] visited = new int[number_of_nodes + 1];
  int i, element;
  visited[source] = 1;
  queue.add(source);
  while (!queue.isEmpty()) {
   element = queue.remove();
   i = element;
   System.out.print(i + "\t");
   while (i <= number_of_nodes) {
    if (adjacency_matrix[element][i] == 1 && visited[i] == 0) {
     queue.add(i);
     visited[i] = 1;
    }
    i++;
   }
  }
 }
 public static void main(String[] arg) {
  int number_no_nodes, source;
  Scanner scanner = null;
  try {
   System.out.println("Enter the number of nodes in the graph");
   scanner = new Scanner(System.in);
   number_no_nodes = scanner.nextInt();
   int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1];
   System.out.println("Enter the adjacency matrix");
   for (int i = 1; i <= number_no_nodes; i++)
    for (int j = 1; j <= number_no_nodes; j++)
     adjacency_matrix[i][j] = scanner.nextInt();
   System.out.println("Enter the source for the graph");
   source = scanner.nextInt();
   System.out.println("The BFS traversal of the graph is ");
   BFS bfs = new BFS();
   bfs.bfs(adjacency_matrix, source);
  } catch (InputMismatchException inputMismatch) {
   System.out.println("Wrong Input Format");
  }
  scanner.close();
 }
}

       
 

Java program to find two numbers in an integer array such that their sum is greater than some integer in O(n) linear time....

problem -find two number 'a' and 'b' such that a+b>sum where sum can be any given integer value...

here is the code ......

logic =you have to execute two passes of bubble sort and then pick the last two elements ...

       
public class findElements {

 public static void main(String[] args) {
  int[] arr = {
   45,
   4,
   23,
   56,
   87,
   27,
   34,
   89
  };
  int temp;
  int sum = 100;
  for (int y = 0; y < 2; y++) {
   for (int i = 0; i < arr.length - y - 1; i++) {

    if (arr[i] > arr[i + 1]) {
     temp = arr[i];
     arr[i] = arr[i + 1];
     arr[i + 1] = temp;
    }
   }
  }
  if (arr[arr.length - 1] + arr[arr.length - 2] > sum)
   System.out.println("required elements are" + arr[arr.length - 1] + " and " + arr[arr.length - 2]);
  else System.out.println("elements not found");
  //for(int s:arr) { System.out.print(s); System.out.print(" ");}
 }

}

time complexity = 2(first loop) + n(second loop) = O(n)

       
 

Dining philosopher's synchronization problem implemented using Java........

here is the code .....

       

public class DiningPhilosopherProblem {
 // Makes the code more readable.
 public static class ChopStick {
  // Make sure only one philosopher can have me at any time.
  Lock up = new ReentrantLock();
  // Who I am.
  private final int id;

  public ChopStick(int id) {
   this.id = id;
  }

  public boolean pickUp(Philosopher who, String where) throws InterruptedException {
   if (up.tryLock(10, TimeUnit.MILLISECONDS)) {
    System.out.println(who + " picked up " + where + " " + this);
    return true;
   }
   return false;
  }

  public void putDown(Philosopher who, String name) {
   up.unlock();
   System.out.println(who + " put down " + name + " " + this);
  }

  @Override
  public String toString() {
   return "Chopstick-" + id;
  }
 }

 // One philosoper.
 public static class Philosopher implements Runnable {
  // Which one I am.
  private final int id;
  // The chopsticks on either side of me.
  private final ChopStick leftChopStick;
  private final ChopStick rightChopStick;
  // Am I full?
  volatile boolean isTummyFull = false;
  // To randomize eat/Think time
  private Random randomGenerator = new Random();
  // Number of times I was able to eat.
  private int noOfTurnsToEat = 0;

  /**
   * **
   *
   * @param id Philosopher number
   *
   * @param leftChopStick
   * @param rightChopStick
   */
  public Philosopher(int id, ChopStick leftChopStick, ChopStick rightChopStick) {
   this.id = id;
   this.leftChopStick = leftChopStick;
   this.rightChopStick = rightChopStick;
  }

  @Override
  public void run() {

   try {
    while (!isTummyFull) {
     // Think for a bit.
     think();
     // Make the mechanism obvious.
     if (leftChopStick.pickUp(this, "left")) {
      if (rightChopStick.pickUp(this, "right")) {
       // Eat some.
       eat();
       // Finished.
       rightChopStick.putDown(this, "right");
      }
      // Finished.
      leftChopStick.putDown(this, "left");
     }
    }
   } catch (Exception e) {
    // Catch the exception outside the loop.
    e.printStackTrace();
   }
  }

  private void think() throws InterruptedException {
   System.out.println(this + " is thinking");
   Thread.sleep(randomGenerator.nextInt(1000));
  }

  private void eat() throws InterruptedException {
   System.out.println(this + " is eating");
   noOfTurnsToEat++;
   Thread.sleep(randomGenerator.nextInt(1000));
  }

  // Accessors at the end.
  public int getNoOfTurnsToEat() {
   return noOfTurnsToEat;
  }

  @Override
  public String toString() {
   return "Philosopher-" + id;
  }
 }
 // How many to test with.
 private static final int NO_OF_PHILOSOPHER = 50;
 //private static final int SIMULATION_MILLIS = 1000 * 60 * 8;
 private static final int SIMULATION_MILLIS = 1000 * 10;

 public static void main(String args[]) throws InterruptedException {
  ExecutorService executorService = null;

  Philosopher[] philosophers = null;
  try {

   philosophers = new Philosopher[NO_OF_PHILOSOPHER];

   //As many forks as Philosophers
   ChopStick[] chopSticks = new ChopStick[NO_OF_PHILOSOPHER];
   // Cannot do this as it will fill the whole array with the SAME chopstick.
   //Arrays.fill(chopSticks, new ReentrantLock());
   for (int i = 0; i < NO_OF_PHILOSOPHER; i++) {
    chopSticks[i] = new ChopStick(i);
   }

   executorService = Executors.newFixedThreadPool(NO_OF_PHILOSOPHER);

   for (int i = 0; i < NO_OF_PHILOSOPHER; i++) {
    philosophers[i] = new Philosopher(i, chopSticks[i], chopSticks[(i + 1) % NO_OF_PHILOSOPHER]);
    executorService.execute(philosophers[i]);
   }
   // Main thread sleeps till time of simulation
   Thread.sleep(SIMULATION_MILLIS);
   // Stop all philosophers.
   for (Philosopher philosopher: philosophers) {
    philosopher.isTummyFull = true;
   }

  } finally {
   // Close everything down.
   executorService.shutdown();

   // Wait for all thread to finish
   while (!executorService.isTerminated()) {
    Thread.sleep(1000);
   }

   // Time for check
   for (Philosopher philosopher: philosophers) {
    System.out.println(philosopher + " => No of Turns to Eat =" + philosopher.getNoOfTurnsToEat());
   }
  }
 }
}
       
 

Java program to print reverse number triangle pattern......

Output Pattern-

              123456787654321
                1234567654321
                  12345654321
                    123454321  
                      1234321  
                        12321    
                          121    
                            1      

here is the code .....

       
class printPattern {
 public static void main(String[] args) {
  int ad = 8;
  for (int i = 0; i < 8; i++, ad--) {

   for (int r = 0; r < i; r++) {
    System.out.print(" ");
   }
   for (int k = 1,
    var = ad; k <=
    var; k++) {
    System.out.print(k);

   }
   for (int j = (ad - 1); j >= 1; j--) {
    System.out.print(j);
   }
   for (int r = 0; r < i; r++) {
    System.out.print(" ");
   }

   System.out.println(" ");
  }

 }
}