Word Chain

Problem Statement:
               Count the number of minimum jumps required  from the starting word to ending word by changing only one character at each jump.

Start word:  cat    
End word: bay
Dictionary: rat , mat , ray , may , bal , ram , lay

Transition: cat - > mat - > may - > bay
Therefore hops = 3

Solution:

For the given problem we need to find the minimum hops required to reach the end word, the problem is very similar to searching for a node in a tree from the root , and at each level words differ from previous level by 1 character. For such problem we would require BFS (Breadth First Search) .

We start with the root and search for the next word by changing one character and which is also available in the dictionary. This process is repeated until end word is found and hop count is returned, if the word is not reachable by 1 character change then -1 is returned.

Below is the dictionary initialization.

private static Set dict = new HashSet();

 private static void init() 
 {
  dict.add("rat");
  dict.add("mat");
  dict.add("ray");
  dict.add("may");
  dict.add("bal");
  dict.add("ram");
  dict.add("lay");
 }

Now the sub-routine to calculate to the hop count.

/**
  * Word Chain Sub-routine, using BFS
  * @param src: start word
  * @param dst: end word
  * @return : number of hops
  */
 public static int wordChain(String src, String dst)
 {
  int level = 0;

  Queue queue = new LinkedList();
  queue.add(src);
  //used as level separator
  queue.add(null);

  while (!queue.isEmpty()) 
  {
   String popedItem = queue.poll();

   //if null found , then all elements at current level are processed
   if (popedItem == null) 
   {
    queue.offer(null);
    level++;
    continue;
   }

   //Destination word found
   if (popedItem.equalsIgnoreCase(dst))
    return level;

   //Change each character of word from 'a' to 'z', if found in dictionary add to queue, 
   // and remove from dictionary
   int i = 0;
   while (i < popedItem.length()) 
   {
    StringBuilder temp = new StringBuilder(popedItem);
    for (char j = 'a'; j <= 'z'; j++) 
    {
     temp.setCharAt(i, j);

     if (temp.toString().equalsIgnoreCase(dst))
      return level;

     if (dict.contains(temp.toString())) 
     {
      queue.add(temp.toString());
      dict.remove(temp.toString());
     }

    }
    i++;
   }
  }
  return -1;
 }

Please comment and suggestions.
Happy Coding !! :)

Minimum Window Containing all words

Problem Statement:
   Find the minimum window in which all the words of the pattern string are present in the input string.

Text  "Shopping with xyz.com is an awesome experience"
Pattern : "awesome with xyz.com"

Output : "with  xyz.com  is  an  awesome"

The output window contains all words of pattern in text.

Download Source Code
Solution:

The approach to solve the problem is to have two pointers of the window , as left and right.
The right pointer is moved to the right until all words in the text are found, once all the required words are found the left pointer is moved to its right to discard  the words on the left hand of the window.

The approach used is based on Sliding Window. In this approach we take pointers at extreme left and extreme right. The right pointer is moved to its right in search of required words, once the window contains all required words, the left pointer tries to decrease size of the window with all the required words.
If the current window length is smaller smaller than previous one , it is recorded or updated.

Complexity: O(n) + O(n)  = O(n)

Below is the implementation

private static int minWindow = 9999; // length of minimum window
 private static int startWord = 0; // start position
 private static int endWord = 0; // end position
 /**
  * Sub-routine to minumum window in which all words of pattern are found in
  * the given string
  * @param str : input String
  * @param pat : pattern
  */
 public static void minWindow(String str, String pat)
 {

  // words to be found
  Map toFind = new HashMap(); 
  // the set of  words  which are found
  Map found = new HashMap(); 

  int foundCount = 0;
  // left pointer of the window, which is moved when all required wrds are
  // found,
  // and is moved until any word from required word is found
  int tempStart = 0;

  // Tokenising Text
  String[] words = str.split(" ");
  int sLen = words.length;

  // Tokenising Pattern
  String[] patTokens = pat.split(" ");
  int pLen = patTokens.length;

  // filling the 'toFind' map
  for (String val : patTokens)
   toFind.put(val, toFind.get(val) == null ? 1 : toFind.get(val) + 1);

  // traversing over text length
  for (int index = 0; index < sLen; index++)
  {
   String word = words[index];

   if (!toFind.containsKey(word))
    continue;

   found.put(word, found.get(word) == null ? 1 : found.get(word) + 1);

   if (toFind.get(word) >= found.get(word))
    foundCount++;

   if (foundCount == pLen) 
   {
    // reduce window size until conditions are violated
    word = words[tempStart];
    while (!toFind.containsKey(word)
      || toFind.get(word) < found.get(word)) 
    {
     // Discard excess count of the given word
     if (toFind.containsKey(word))
      found.put(word, found.get(word) - 1);

     // get next word, to check if it can be discarded
     word = words[++tempStart];
    }

    // Updating Min Window
    if (minWindow > index - tempStart + 1)
    {
     minWindow = index - tempStart + 1;
     startWord = tempStart;
     endWord = index;
    }
   }
  }
 }

Please comment and post your suggestions.
Happy Coding !! :)

Soduku

Problem Statement:
      Solve the given Soduku

Fig Soduku

Download Source Code
Solution: 
      For optimally solving the above soduku, we would require the technique of Backtracking.

Back-Tracking is a technique which incrementally builds candidates to a solution, and it rejects the candidate as soon as it determines the choosing that particular candidate will not lead to valid solution.
Back-Tracking takes the advantage of choosing and rejecting a candidate in a solution with the help of combined effect of Tail and Head Recursion.

In this problem , backtracking fills up a valid cell with the number , and moves the to the next cell and assumes the same set of conditions as was with the previous cell. At any cell if all numbers from '1' to '9' are invalid, then we back track to the previous cell and fill that with another valid number, then we move to the next cell and continue the process until all cells are filled which will give the solution or the first cell is tried with all numbers fro  1 to 9 and still soduku was not solved, then soduku is unsolvable.

The Backtracking sub-routine is shown below: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

/** * Subroutine to solve the Soduku * @return true if soduku is solvable */ public boolean solve(int row, int col) { if (soduku[row][col] != BLANK) nextCell(row, col); else { // Try the vacant cell with every Number for (int num = 1; num <= size; num++) { // check if current number can fit the cell with the given // constraints if (isValid(row, col, num)) { soduku[row][col] = num; // Assuming to be true if (row == size - 1 && col == size - 1) { printSoduku(); return true; } if (solve(row, col)) // will be called again and other cells return true; // will be processed // printSoduku(); soduku[row][col] = BLANK; // Reverting } } } return false; // will be reached if for any cell none of the number(1-9) // fit } /** * Find the next free cell * @return , true if free cell found and currentRow and currentColumn are set */ private void nextCell(int row, int col) { if (col < size - 1) solve(row, col + 1); else if (row < size - 1) solve(row + 1, 0); }

To Check if a cell is valid is shown below, for a number to be valid in a cell it should not appear in 
1. the row of that cell
2. the column of that cell
3. the box, the cell belongs to

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

/** * check validity of number at the given position, combining the result of 3 * conditions * @return true, if the number can fit at the current position */ private boolean isValid(int row, int col, int num) { return checkRow(row, col, num) && checkCol(row, col, num) && checkBox(row - row % boxSize, col - col % boxSize, num); } /** * Check particular for the existance of given number (in a particular row) * @return true if the number does not exist */ private boolean checkRow(int row, int col, int num) { for (int c = 0; c < size; c++) if (soduku[row][c] == num) return false; return true; } /** * Check particular for the existance of given number (in a particular col) * @return true if the number does not exist */ private boolean checkCol(int row, int col, int num) { for (int r = 0; r < size; r++) if (soduku[r][col] == num) return false; return true; } /** * Check particular for the existance of given given BOX * @return true if the number does not exist */ private boolean checkBox(int row, int col, int num) { for (int r = 0; r < boxSize; r++) { for (int c = 0; c < boxSize; c++) { if (soduku[r + row][c + col] == num) return false; } } return true; }

Happy Coding !! :)

Combinations of Coin Change

Problem Statement:
   Print all unique combinations of Coin change for a given amount.

Combinations for Amount 5 , from the given denominations

Fig: Change for Amount 5

Download Source Code
Solution:
      For finding the optimal solution of the given problem, we will use Backtracking.
Below is the sub-routine implementation.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

/** * Prints all comninations of the coin change */ public static void coinCombinations(int amount,int index,LinkedList<Integer> list) { if(amount==0) { count++; System.out.println(list.toString()); return ; } if(amount < 0) return ; for(int i=index ; i < coins.size();i++) { int coin = coins.get(i); if(amount >= coin) { list.add(coin); coinCombinations(amount - coin ,i,list ); list.removeLast(); } } }

Please post your comments and suggestions.
Happy Coding !! :)   
     

Knight's Tour

Problem Statement:
      Find the sequences of the Knight on a chess board, such that Knight visits every square only once.

Fig: Knight's Tour on 5x5 Board

Download Source Code
Solution:

Knight's tour problem dates back to 9th Century AD, the procedure for completing Knight's tour was first described by Warnsdorff in 1823.

The optimal approach for solving this problem is using back-tracking.
Back-Tracking is a technique which incrementally builds candidates to a solution, and it rejects the candidate as soon as it determines the choosing that particular candidate will not lead to valid solution.
Back-Tracking takes the advantage of choosing and rejecting a candidate in a solution with the help of combined effect of Tail and Head Recursion.

Below is the figure demonstrating the possible moves of Knight placed a given square.

Fig: Possible Moves

Below is the implementation of the logic used in the problem with Back-tracking approach.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

/** * Recursive Sub-routine for Knight's Tour */ private static void knightTour(int[][] board, int row , int col , int curr) { count++; if(isValid(board,row,col)) { board[row][col]=curr; if(curr == (rowLen * colLen - 1)) { printSol(board); System.exit(0); } else { // All Coordinates from given (row,col) knightTour(board,row + 2 , col + 1, curr+1 ); knightTour(board,row + 1 , col + 2, curr+1 ); knightTour(board,row - 1 , col + 2, curr+1 ); knightTour(board,row - 2 , col + 1, curr+1 ); knightTour(board,row - 2 , col - 1, curr+1 ); knightTour(board,row - 1 , col - 2, curr+1 ); knightTour(board,row + 1 , col - 2, curr+1 ); knightTour(board,row + 2 , col - 1, curr+1 ); board[row][col]=BLANK; } } } /** * Checks if for given row and col, the move is Valid or not * @return true: Valid Mode, false: Invalid Move */ private static boolean isValid(int[][] board, int row, int col) { if(row >= 0 && row < colLen && col>=0 && col < rowLen && board[row][col]==BLANK) return true; return false; } /** * Prints the Chessboard having the hops * @param board */ private static void printSol(int[][] board) { for(int i=0;i<colLen;i++) { for(int j=0;j<rowLen;j++) { System.out.print(board[i][j]+ "\t"); } System.out.println(); } System.out.println("recursive Function called " + count + " times"); }

Note: the order in which coordinates are given , gives the least number of  failed back-track-paths.

Please post your comments and feedback
Happy Coding !! :)

Knight's Shortest Path

Problem Statement:
          Given a Source and Destination , find the minimum number of moves required to move a knight from Source to Destination.

Fig: Movement of Knight from Source to Destination

Download Source Code
Solution: 

To find the minimum moves from Source to Destination, I have used the BFS ( Breadth First Search) technique, once the Destination is reached print the Solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

/** * BFS to find the minimum moves to reach the destination * @return return number of hops if solution is availale else -1 */ public static int path(int[][] board, int startRow, int startCol, int endRow, int endCol) { queue = new LinkedList<Coordinate>(); queue.add(new Coordinate(startRow, startCol)); queue.add(null); //this acts a delimiter board[startRow][startCol] = 0; int hops=0; while (!queue.isEmpty()) { Coordinate popedItem = queue.poll(); if (popedItem == null) { hops++; queue.offer(null); //System.out.println("======"); continue; } int r = popedItem.row; int c = popedItem.col; board[r][c] = hops; //System.out.println(hops + " " + r + " " + c); if(r==endRow && c==endCol) { printSol(board); return hops; } Coordinate[] points = validCoordinates(board, r, c); for (Coordinate o : points) { if (o != null) queue.add(o); } } return -1; } private static boolean isValid(int[][] board, int row, int col) { if (row >= 0 && row < colLen && col >= 0 && col < rowLen && board[row][col] == BLANK) return true; return false; } public static Coordinate[] validCoordinates(int[][] board, int row, int col) { Coordinate[] points = new Coordinate[8]; if (isValid(board, row + 2, col + 1)) points[0] = new Coordinate(row + 2, col + 1); if (isValid(board, row + 1, col + 2)) points[1] = new Coordinate(row + 1, col + 2); if (isValid(board, row - 1, col + 2)) points[2] = new Coordinate(row - 1, col + 2); if (isValid(board, row - 2, col + 1)) points[3] = new Coordinate(row - 2, col + 1); if (isValid(board, row - 2, col - 1)) points[4] = new Coordinate(row - 2, col - 1); if (isValid(board, row - 1, col - 2)) points[5] = new Coordinate(row - 1, col - 2); if (isValid(board, row + 1, col - 2)) points[6] = new Coordinate(row + 1, col - 2); if (isValid(board, row + 2, col - 1)) points[7] = new Coordinate(row + 2, col - 1); return points; } private static void printSol(int[][] board) { for(int i=0;i<colLen;i++) { for(int j=0;j<rowLen;j++) { System.out.print(board[i][j]+ " "); } System.out.println(); } }

Please post your suggestions and comments.
Happy Coding !! :)