Coding Recipies: 2014

4 Oct 2014

Algo #116: Square Root (using Newton Ralpson Method)

Problem Statement:
Calculate the square root of a number using Newton Raphson's Method .

Download Source Code
Solution:

Newton Raphson's method is used for finding successive better approximate roots of a functions, at every successive iteration , the result tends towards the root of the function.

In this technique we use the logic of approximation by calculating the tangent line of the function f(x), derivative of the function f(x) represents the tangent line to the function curve f(x).

Geometrical Interpretation:
Let r be a root of f(x), that is f(r) =0. Assume that $f'(r) \neq 0$ . Let x₁ be a number close to r (which may be obtained by looking at the graph of f(x)). The tangent line to the graph of f(x) at (x₁,f(x₁)) has x₂ as its x-intercept

Fig1: Representing f(x) and f '(x) and r being the root f(r)=0

From the above picture, we see that x₂ is getting closer to r. Successive iterations will lead to results closer to 'r'. x1 was the intial guess which lead to a better result x2.

Now,

here Er represent the percentage error.

Lets calculate the square root of 44.89,
we will assume out initial guess to be 44.89, using the formula

Now code up our logic for calculating the square root.

float squareRoot(float num)
 {
  float x1 = num,x2=0,temp=num,e=0.001f;
  do 
  {
   x1 = temp;
   x2 = 0.5f * (x1 + num/x1);
   temp=x2;
   
  }while(Math.abs(x2-x1)> e);
  
  System.out.println(num + " ----> " + x2);
  return x2;
 }

Rare Scenarios which might happen when using Newton Raphson Method:

1. If the initial estimate is not close enough to the root, the Newton Method may not converge, or may converge to the wrong root.

2. The successive estimates of the Newton Method may converge to the root too slowly, or may not converge at all.

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

References:
1. http://www.sosmath.com/calculus/diff/der07/der07.html
2. https://www.math.ubc.ca/~anstee/math104/104newtonmethod.pdf
3. http://www.codecogs.com/eqnedit.php
4. Wiki

Algo #115: Reverse words in a character array

Problem Statement:
Reverse Words of the String given in the form of Character array without additional space.

Fig 1

Download Source Code
Solution:

1st Approach:
Our first approach will require K-1 iterations inorder to get the desired result , where K is the number of words, in each iteration we will move the first word to the end.

Fig 2

At every iteration we will have to hold 1 word in temp memory. Since this approach requires memory equal to 1 word, we will move to our in-place approach.

Time Complexity : O(KN) , where K is number of words and N is the Size of character array.

2nd Approach :
We can divide this approach in two steps.
1. Reverse the character array completely.
2. Reverse each word in the reverse array.

Lets show this by the diagram.

Fig 3

Lets implement the above logic.

/**Reverse Words in an array
  */
 private static void reverseWords(char[] str) {
  if(str==null || str.length==0)
   return ;
  
  String temp = new String(str);
  int len = str.length, l=0,r=0;

  //Reverse the input array
  reverseArr(str, 0, str.length-1);
  
  while(r<len && str[r] == ' ') //Skip initial Spaces, if any
   r++;
  
  while(r<len)
  {
   l=r; //l hold the start character of the word
   while(r== len-2 || (r<len-1 && str[r+1] != ' ')) //Get the last character of the word in r
    r++;
      
   reverseArr(str,l,r++);

   while(r<len && str[r] == ' ') //Find the next character using r
    r++; 
  }
  System.out.println(temp +" ----> " +new String(str));
 }
 
 
 /**
  * Reverse the character array between i and j (inclusive)
  */
 private static void reverseArr(char[] s,int i, int j) {
  int len=i+(j-i)/2;  //look carefully this line, when i is not 0
  for(;i<=len;i++,j--)
   swap(s,i,j);
 }

 /**
  * Swaps the ith and jth indices
  */
 private static void swap(char[] arr,int i, int j) {
  char temp  = arr[i];
  arr[i] = arr[j];
  arr[j]=temp;
 }
 
 public static void main(String[] args) {
  String s1 = "  Coding    Recipes is Super   Cool  ";
  String s2 = "I live to code";
  String s3 = "Recursion is Recursion";
  //reverseWords1(s.toCharArray());
  reverseWords(s1.toCharArray());
  reverseWords(s2.toCharArray());
  reverseWords(s3.toCharArray());
  reverseWords("   ".toCharArray());
  reverseWords(null);
 }

Output is :

 Coding    Recipes is Super   Cool   ---->   Cool   Super is Recipes    Coding  
I live to code ----> code to live I
Recursion is Recursion ----> Recursion is Recursion

Time Complexity: O(n)
Space Complexity: O(1)

Please post your comments , queries or any suggestions.
Happy Coding !! :)

Algo #114: Rotate Array

Problem Statement:
Rotate array by K with constraints
Time Complexity: O(n)
Space Complexity : O(1)

For K=3

Notice that 1 is poped out and pushed at the back of 10 , similar thing happened for 2 and 3 as well.

Solution:

Our approach will consist of three steps.
1. Reverse (0 to K )
2. Reverse (K+1 to len-1)
3. Reverse Entire array.

Lets See this by fig.

Fig : Step wise transformation of array.

Implementation of the above approach:

/**
  * Rotate array by k
  */
  void rotate2(int[] arr, int k) {
  if(k<=0 || arr==null || arr.length==0)
   return ;
  int[] old = Arrays.copyOf(arr, arr.length);
  k--;
  
  int i=0,j=k,len=arr.length;
  for (; i <=k/2 ; i++,j--)
   swap(arr, i, j);
  
  int temp=  i + (len-i)/2;
  for (i=k+1,j= arr.length-1; i <= temp ; i++,j--)
   swap(arr, i, j);
  
  
  for (i=0,j= len-1; i "+ Arrays.toString(arr));
 }

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

Algo #113: Inverse of a number (without division)

Problem Statement:
Calculate Inverse of number without using '/ ' operator.

Solution:
There could be multiple techniques for solving this problem but in this post i will solve this problem using Newton Raphson's Method. Refer to my earlier post on Newton Raphson for Square Roots.

Lets code up our logic.

public static void main(String[] args) {

  inverse(0.2f);
  inverse(0.3f);
  inverse(3.3f);
 }

 private static float inverse(float num) {
  float x1= num,x2=0,temp=num,e=0.001f;
  do 
  {
   x1 = temp;
   x2 = x1 * (2 - num*x1);
   temp=x2;
  }while(Math.abs(x2-x1)> e);
  
  System.out.println(num + " ----> " + x2);
  return x2;
 }

PS: The choice of the initial value may or may not converge the function and thus may not give correct result which is drawback of Newton Raphson's method

References:
1. http://www.sosmath.com/calculus/diff/der07/der07.html
2. https://www.math.ubc.ca/~anstee/math104/104newtonmethod.pdf
3. http://www.codecogs.com/eqnedit.php
4. Wiki

Algo #112: Number to Words

Problem Statement:
Given a number convert it to words.

e.g. 1327 as One thousand three hundred twenty seven

Solution:

Implementation:

/**
 * Convert a given number to a word
 * @author PRATEEK
 */
public class NumberToWord {

 private static String ones[] = { " ", " one", " two", " three", " four",
   " five", " six", " seven", " eight", " Nine", " ten", " eleven",
   " twelve", " thirteen", " fourteen", "fifteen", " sixteen",
   " seventeen", " eighteen", " nineteen" };

 private static String tens[] = { " ", " ", " twenty", " thirty", " forty",
   " fifty", " sixty", "seventy", " eighty", " ninety" };

 
 private static void word(StringBuilder result , int val, String place) {
  if (val > 19)
   result.append(tens[val / 10] + " " + ones[val % 10]);
  else
   result.append(ones[val]);
  if (val > 0)
   result.append(place);
 }

 public static String convertToWord(int num)
 {
  if (num <= 0)
   return "";
  
  StringBuilder result = new StringBuilder("");
  word(result, num / 1000000000, " Hundred");
  word(result, (num / 10000000) % 100, " crore");
  word(result ,(num / 100000) % 100, " lakh");
  word(result, (num / 1000) % 100, " thousand");
  word(result,(num / 100) % 10, " hundred");
  word(result,num % 100, " ");
  System.out.println(num + " --> "+result.toString().trim());
  return result.toString().trim();
 }
 
 public static void main(String[] args) {
  convertToWord(117);
  convertToWord(1327);
 }
}

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

2 Oct 2014

Algo #111: Nth Fibbonacci Number in log(n) complexity

Problem Statement:
Find the Nth Fibbonaci number in log(n) complexity.

Download Source Code
Solution:

The recurrence Relation for the Fibonacci series given by
f(n) = f(n-1) + f(n-2)

We can code up the Recursive and DP (Dynamic programming) Solution for the above equation, these techniques gives us a exponential complexity and O(n) complexity respectively.

Recursive Solution:

int fib1(int n) {
   if(n<=1)
    return n;
   return fib1(n-1) + fib(n-2);
  }

Time Complexity: Exponential

Dynamic Programming Approach:

int fib2(int n)
 {
  if(n==0)
   return 0;
  int old1=0 , old2=1 , curr,i=2;
  for(;i<=n;i++)
  {
   curr = old1 + old2;
   old1= old2;
   old2 = curr;
  }
  return old2;
 }

Time Complexity: O(n)

Now we will discuss an approach which is of the order of O(n) and is called as Matrix Exponentiation.

Matrix Exponentiation is used to find the nth element of a series which can be represented in the form of a recurrence equation.

Now our recurrence equation can be represented in the form of Matrix multiplication

f(n) = f(n-1) + f(n-2)

which can be represented as

| f(n)  |  =  I x  | f(n-1) |
| f(n-1)|          | f(n-2) |

where I = | a  b |
          | c  d |

Expanding and solving, we get

f(n) = a*f(n-1) + b*f(n-2)
and 
f(n-1) = c*f(n-1) + d*f(n-2)

solving we get,

I = | a  b |  =  | 1  1 |
    | c  d |     | 1  0 |

Our goal is to find [ f(n) f(n-1)] , from bottom to top by recursive doubling (Matrix exponentiation)

To get 
| f(n)   | = I x | f(n-1) |  , where I = | 1 1 |
| f(n-1) |       | f(n-2) |              | 1 0 |

We start with 

| f(2) | =  I x | f(1) |   , where | f(1) | = | 1 |
| f(1) |        | f(0) |           | f(0) |   | 1 |
then, 
| f(3) | =  I x | f(2) | = I^2 x | f(1) |
| f(2) |        | f(1) |         | f(0) |
then
| f(4) | =  I x | f(3) | = I^3 x | f(1) |
| f(3) |        | f(2) |         | f(0) |
...
...
...
| f(n)   | =  I x | f(n-1) | = I^(n-1) x | f(1) |
| f(n-1) |        | f(n-2) |             | f(0) |

You can observe that now we are left out with calculating I^(n-1) this is where matrix exponentiation will yield its result in O(log N) time.

Lets understand logic behind recursive doubling, which reduces the computation time to O(log N)

Now lets suppose we have to calulate I^n , 
If n is odd 
             I^n = I^((n-1)/2)  * I^((n-1)/2) * I 
If n is even 
             I^n = I^(n/2) * I^(n/2)

example 
   1. n = 9 (odd)
            I^9 = I^4 * I^4 * I

   2. n=12 (even)
             I^12 = I^6 * I^6

Now lets code up our logic.

private static int[][] F = { { 1, 1 }, { 1, 0 } }; // will change , capture rsult here
private static int[][] I = { { 1, 1 }, { 1, 0 } }; //will remain fixed
 
 public static int fib(int n){
  if(n==0)
   return 0;
  power(F,n-1);
  
  return F[0][0];
 }
 
 /**
  * Calculates F to the power n
  * @param F
  * @param n
  */
 private static void power(int[][] F, int n) {
  if(n==0 || n==1)
   return;
  
  power(F,n/2);
  multiplyMatrix(F,F);
  
  if(n%2!=0)
   multiplyMatrix(F, I);
 }
 
 /**
  * Multiples Matrixes of size 2X2
  */
 public static int[][] multiplyMatrix(int[][] A, int[][] B)
 {
    int x =  A[0][0]*B[0][0] + A[0][1]*B[1][0];
    int y =  A[0][0]*B[0][1] + A[0][1]*B[1][1];
    int z =  A[1][0]*B[0][0] + A[1][1]*B[1][0];
    int w =  A[1][0]*B[0][1] + A[1][1]*B[1][1];
   
    A[0][0] = x;
    A[0][1] = y;
    A[1][0] = z;
    A[1][1] = w;
    
    return A;
 }
 
 public static void main(String[] args) {
  //1,1,2,3,5,8,13,21,34,55,89...
  int n = 8;
  System.out.println(n + "--->" + fib(n));
 }

References:
1. CodeChef
2. Wikipedia

Please comment and post your suggestions.
Happy Coding !!

31 Jul 2014

Add Numbers

Problem Statement:
Add two given numbers without '+' operator.

Download Source Code
Solution:
We will be adding two given numbers using 'AND' and 'XOR' logical operators.

Fig: Half Adder , S: Sum and C: Carry

Sum of two number can be achieved with Half adder, if carry is greater than 0 , then it the process is repeated again. This is half adder implementation.

and as per full adder implementation :
Sum = 2*C + S

Below are the different ways of getting the sum using XOR and AND logical operators.

Method 1 :

int add(int a, int b) {
  while (b != 0) {
   int carry = a & b;
   a = a ^ b;
   b = carry << 1;
  }
  return a;
 }

Method 2:

 int add(int a, int b) {
  if (b == 0)
   return a;
  else
   return add2(a ^ b, (a & b) << 1);
 }

Method 3:

  int add(int a,int b){
  int carry= a & b;
  int sum= a ^ b;
  
  carry = 2* carry;
  
  sum = sum ^ carry;
  
  return sum;
 }

Method 4:

 int add(int a,int b){
  return ( 2*( a & b) ) ^ (a ^ b);
 }

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

References:
Wikipedia

TV remote

Problem Statement:

Download Problem Statement
Download Solution

Gaurav has fractured his leg in a bicycle accident.He keeps himself busy by watching television on his Tata Sky DTH. While watching the television, one day he decided to play a small game, where
he has to identify the minimum number of clicks required to surf a given set of channels in a

sequence.
WAP with given instructions:

Instructions

There are 13 buttons on his remote: 10 buttons for the numbers (0-9), an "Up Channel" button,
a "Down Channel" button, and a "Back" button:

● The number buttons allow you to jump directly to a specific channel. (Ex: to go to
channel 63 by typing “6”, “3”.)
● The "Up Channel" button increments the current channel to the next higher viewable
channel, unless the current channel is the highest viewable channel, in which case it
rolls over to the lowest viewable channel.
● The "Down Channel" button decrements to the next lower viewable channel, unless the
current channel is the lowest viewable channel, in which case it rolls over to the highest
viewable channel.
● The "Back" button reverts to whatever channel was on the television before the current
channel. (Ex: If channel 1 is viewed, then channel 100, then when Back is pressed, the
television will go to channel 1.)

Gaurav can get from one channel to the next in one of the two ways:
● Clicking any combination of "Up Channel", "Down Channel", and "Back" buttons.
● Keying in the numbers to the channel. Gaurav will never combine "Back" and number
buttons when moving from one channel to the next.

Gaurav’s parents have set some parental control on some channels on Gaurav's television.
These channels are not viewable, so they are skipped by the "Up Channel" and "Down
Channel" buttons.

Given a list of channels to view, the lowest channel, the highest channel, and a list of blocked
channels, your program should return the minimum number of clicks necessary to get
through all the shows that Gaurav would like to watch.

Constraints

● The sequence that Gaurav must view contains between 1 and 50 elements, inclusive. All

channels in this sequence are not in the blocked list and are between lowest channel

and highest channel, inclusive.

14 Jul 2014

Pattern Matching: Rabin Karp

Problem Statement:
Implement Rabin Karp hashing based Pattern-Matching Algorithm.

Example:
Text (T): rabing karp uses hashing technique
Pattern (P) : hashing

n : length of text
m : length of pattern

Download Source Code
Solution:
Rabin Karp Algorithm finds a match of the pattern in the text by using hashing. Match is found only if hash of Pattern and hash of text of m characters gives same result.

Our objective is to reduce complexity from O(m x n ) as was in case of Brute force. We will have to desigyn a hash function which take O(1) complexity for finding hash of the pattern.

We will consider Horner's rule to calculate the hash of the pattern and hash of text of 'm' length.

Let us denote pattern as polynomial

here we will call 'x' as radix , and above polynomial can also be represented as

So this was about calculating hash by iterative method using the simplified equation.

Now,

The pattern 'P' will match Text 'T' iff T[i , i+1 , .....i+m-1] = P [0,1,......, m-1 ]

ti : represents the hash value from T[i , .....i+m-1]

and ti+1 : represents the hash value from T[i+1 , .....i+m-1 , i+m]

Lets consider a Text containing all numbers as characters , i.e. Character set is {1,2,3,4,5,6,7,8,9,0} and

lets say radix = 10, therefore calculating the numerical value of "35678" which will be 35,678.

Therefore, p = P[m-1] + 10 { P[m-2] + 10 { P[m-3] + 10 { ...... + 10 { P[1] + 10 * P[0] } } } }

for "35678"

p = 8 + 7*10 + 6*102 + 5*103 + 3 *104

= 8 + 10 { 7 + 10 { 6 + 10 { 5 + 10 {3 + 10 * 0} } } }

we assume that to calculate this hash takes O(1) complexity , assume if ti is the hash code value of Text Window does not match with pattern P, we will have to calculate T(i +1 ) next , here we can leverage ti to calculate ti+1.

ti = T[i+m-1] + 10 { T[i+m-2] + 10 { T[i+m-3] +10 { ...... + 10 { T[i+1] + 10 * T[i] } } } }

Now,

ti+1 = 10 (ti – 10m-1 T[i]) + T[i+m]

N.B.: 10m-1 value can also be pre-computed.

Now consider 35678 does not match and next digit to be considered is 4, then

Remove Most Significant digit 35678 - 3 * 10000 = 5678
Multiply above value by 10 and add 4 , 5678*10 + 4 = 56784

Below is the implementation:

/**
 * Rabin Karp uses hashing technique to search for Strings 
 * @author PRATEEK Rathore
 */
public class RabinKarp {
 
 //Contant prime number
 private static final int CONSTANT_PRIME = 101;
 //Hash Value of the pattern which will remain constant through out the problem
 private long pathash;
 private int radix;
 //Input pattern
 private String pat;
 //Pattern Length
 private int patLen;
 
 //Its the place value of Most Significant bit
 private long RM1;

 //Preprocessing of pattern in the constructor
 public RabinKarp( String pat) {
  radix = 256;
  patLen = pat.length();
  this.pat = pat;

  RM1 = 1;
  for (int i = 1; i < patLen; i++)
   RM1 = (radix * RM1) % CONSTANT_PRIME;

  //return hash value of pattern
  pathash = hash(pat, patLen);
 }

 //Return hash value of given string from 0 to the input length
 private long hash(String pat, int len) {
  long h = 0;
  for (int j = 0; j < len; j++)
   h = (radix * h + pat.charAt(j)) % CONSTANT_PRIME;
  return h;
 }

 /**
  * Sub-routine called when hash-function is equal,
  * character by character comparison is done.
  */
 private boolean doesMatch(String text, int currIndex) {
  for (int j = 0; j < patLen; j++)
   if (pat.charAt(j) != text.charAt(currIndex + 1 + j))
    return false;
  return true;
 }

 /**
  * Search for the pattern in the input string
  * @param text
  * @return: index where pattern is found in text
  */
 public int search(String text) {
  int textLen = text.length();
  if (patLen > textLen)
   return -1;

  long textHash = hash(text, patLen);

  for (int i = 0; i < textLen - patLen; i++) {
   textHash = radix * (textHash - RM1 * text.charAt(i))% CONSTANT_PRIME   +   
       CONSTANT_PRIME + text.charAt(i + patLen) % CONSTANT_PRIME;
   if (textHash == pathash && doesMatch(text, i))
    return i;
  }
  return -1;
 }

 public static void main(String[] args) {

  String pat = "prateek";
  String txt = "Welcome prateek to Bangalore";
  
  RabinKarp rabin = new RabinKarp( pat);
  int index= rabin.search(txt);
  System.out.println("Text found at "+ index + ": " + txt.substring(index, index+ pat.length()+1));
 }
}

Time Complexity:
Worst Case is : O(m ( n- m+1 ))
Best and Average Case is : O (m + n )

References:
1. http://en.wikipedia.org/wiki/Horner's_method

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

29 Jun 2014

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 !! :)

28 Jun 2014

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 !! :)

9 Jun 2014

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:

 /**
  * 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

 /**
  * 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 !! :)

8 Jun 2014

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.

/**
  * 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.

/**
  * 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 !! :)