Solve the Rat In A Maze problem using backtracking.

This is one of the classical problems of computer science. There is a rat trapped in a maze. There are multiple paths in the maze from the starting point to the ending point. There is some cheese at the exit. The rat starts from the entrance of the maze and wants to get to the cheese.

This problem can be attacked as follows.
Have a m*m matrix which represents the maze.

For the sake of simplifying the implementation, have a boundary around your matrix and fill it up with all ones. This is so that you know when the rat is trying to go out of the boundary of the maze. In the real world, the rat would know not to go out of the maze, but hey! So, initially the matrix (I mean, the maze) would be something like (the ones represent the "exra" boundary we have added). The ones inside specify the obstacles.


111111111111111111111
100000000000000000001
100000010000000000001
100000010000000000001
100000000100001000001
100001000010000000001
100000000100000000001
100000000000000000001
111111111111111111111



The rat can move in four directions at any point in time (well, right, left, up, down). Please note that the rat can't move diagonally. Imagine a real maze and not a matrix. In matrix language



Moving right means adding {0,1} to the current coordinates.

Moving left means adding {0,-1} to the current coordinates.

Moving up means adding {-1,0} to the current coordinates.

Moving right means adding {1,0} to the current coordinates.



The rat can start off at the first row and the first column as the entrance point.

From there, it tries to move to a cell which is currently free. A cell is free if it has a zero in it.

It tries all the 4 options one-by-one, till it finds an empty cell. If it finds one, it moves to that cell and marks it with a 1 (saying it has visited it once). Then it continues to move ahead from that cell to other cells.

If at a particular cell, it runs out of all the 4 options (that is it cant move either right, left, up or down), then it needs to backtrack. It backtracks till a point where it can move ahead and be closer to the exit.

If it reaches the exit point, it gets the cheese, ofcourse.

The complexity is O(m*m).



Here is some pseudocode to chew upon


findpath()
{
Position offset[4];
Offset[0].row=0; offset[0].col=1;//right;
Offset[1].row=1; offset[1].col=0;//down;
Offset[2].row=0; offset[2].col=-1;//left;
Offset[3].row=-1; offset[3].col=0;//up;

// Initialize wall of obstacles around the maze
for(int i=0; i < m+1;i++)
maze[0][i] = maze[m+1][i]=1; maze[i][0] = maze[i][m+1]=1;

Position here;
Here.row=1;
Here.col=1;

maze[1][1]=1;
int option = 0;
int lastoption = 3;

while(here.row!=m || here.col!=m)
{
//Find a neighbor to move
int r,c;

while (option <= LastOption)
{
r=here.row + offset[position].row;
c=here.col + offset[option].col;
if(maze[r][c]==0)break;
option++;
}

//Was a neighbor found?
if(option <= LastOption)
{
path->Add(here);
here.row=r;here.col=c;
maze[r][c]=1;
option=0;
}
else
{
if(path->Empty())return(False);
Position next;
Path->Delete(next);
If(new.row==here.row)
Option=2+next.col - here.col;
Else { option = 3 + next.row - here.col;}
Here=next;
}
return(TRUE);
}
}

Read More

Write a C program which when compiled and run, prints out a message indicating whether the compiler that it is compiled with, allows /* */ comments to nest.

#include
int allowed(){
     int a=1;
     /* /* */ a=0; // */
    return  a;
}

int main(){
   if (allowed())
       printf("Nested comments Allowed\n");
   else
       printf("Nested comments not Allowed\n");
   return 0;
}

In case of nested comments not allowed, we have it as /*/* */ a=0;// */
Bigger font show commented area........


What if the single line comment style is not supported?
After all, single line style comments were introduced with C++...........
#include
int allowed(){
    int i=0, k=1;
    int *j = &k;
    return  /* /* */ i */*j;/* */1;
}

int main(){
   if (allowed())
       printf("Nested comments Allowed\n");
   else
       printf("Nested comments not Allowed\n");
   return 0;
}

So in case of nested comments allowed we have /*/* *\ *\.....
but in case its allowed it is : /*/* *\ *\

Read More

Find the nth Ugly Number

Problem

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... shows the first 11 ugly numbers. ...By convention, 1 is included. Write a program to find and print the 1500'th ugly number. 

 Solution
Method 1 - Brute force
Loop for all positive integers until ugly number count is smaller than n, if an integer is ugly than increment ugly number count.
To check if a number is ugly, divide the number by greatest divisible powers of 2, 3 and 5, if the number becomes 1 then it is an ugly number otherwise not.
For example, let us see how to check for 300 is ugly or not. Greatest divisible power of 2 is 4, after dividing 300 by 4 we get 75. Greatest divisible power of 3 is 3, after dividing 75 by 3 we get 25. Greatest divisible power of 5 is 25, after dividing 25 by 25 we get 1. Since we get 1 finally, 300 is ugly number.

private static int maxDivide(int a, int b)
{
  while (a%b == 0)
   a = a/b; 
  return a;
}   

private static int isUgly(int no)
{
  no = maxDivide(no, 2);
  no = maxDivide(no, 3);
  no = maxDivide(no, 5);
   
  return (no == 1)? 1 : 0;
}    
 
/* Function to get the nth ugly number*/
public static int getNthUglyNo(int n)
{
  int i = 1; 
  int count = 1;   /* ugly number count */
 
  while (n > count)
  {
    i++;      
    if (isUgly(i))
      count++; 
  }
  return i;
}

This method is not time efficient as it checks for all integers until ugly number count becomes n, but space complexity of this method is O(1)

Method 2 - Using dynamic programming

1 Declare an array for ugly numbers:  ugly[150]
2 Initialize first ugly no:  ugly[0] = 1
3 Initialize three array index variables i2, i3, i5 to point to 
   1st element of the ugly array: 
        i2 = i3 = i5 =0; 
4 Initialize 3 choices for the next ugly no:
         next_mulitple_of_2 = ugly[i2]*2;
         next_mulitple_of_3 = ugly[i3]*3
         next_mulitple_of_5 = ugly[i5]*5;
5 Now go in a loop to fill all ugly numbers till 150:
For (i = 1; i < 150; i++ ) 
{
    /* These small steps are not optimized for good 
      readability. Will optimize them in C program */
    next_ugly_no  = Min(next_mulitple_of_2,
                                  next_mulitple_of_3,
                                  next_mulitple_of_5); 
    if  (next_ugly_no  == next_mulitple_of_2) 
    {             
        i2 = i2 + 1;        
        next_mulitple_of_2 = ugly[i2]*2;
    } 
    if  (next_ugly_no  == next_mulitple_of_3) 
    {             
        i3 = i3 + 1;        
        next_mulitple_of_3 = ugly[i3]*3;
     }            
     if  (next_ugly_no  == next_mulitple_of_5)
     {    
        i5 = i5 + 1;        
        next_mulitple_of_5 = ugly[i5]*5;
     } 
     ugly[i] =  next_ugly_no       
}/* end of for loop */ 
6.return next_ugly_no

Example
Suppose N = 50

initialize
   ugly[] =  | 1 |
   i2 =  i3 = i5 = 0;

First iteration
   ugly[1] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
            = Min(2, 3, 5)
            = 2
   ugly[] =  | 1 | 2 |
   i2 = 1,  i3 = i5 = 0  (i2 got incremented ) 

Second iteration
    ugly[2] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
             = Min(4, 3, 5)
             = 3
    ugly[] =  | 1 | 2 | 3 |
    i2 = 1,  i3 =  1, i5 = 0  (i3 got incremented ) 

Third iteration
    ugly[3] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
             = Min(4, 6, 5)
             = 4
    ugly[] =  | 1 | 2 | 3 |  4 |
    i2 = 2,  i3 =  1, i5 = 0  (i2 got incremented )

Fourth iteration
    ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
              = Min(6, 6, 5)
              = 5
    ugly[] =  | 1 | 2 | 3 |  4 | 5 |
    i2 = 2,  i3 =  1, i5 = 1  (i5 got incremented )

Fifth iteration
    ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
              = Min(6, 6, 10)
              = 6
    ugly[] =  | 1 | 2 | 3 |  4 | 5 | 6 |
    i2 = 3,  i3 =  2, i5 = 1  (i2 and i3 got incremented )

Will continue same way till I < 150

Here is the code in java

public static int getKthMagicNumber(int k) {
    if (k <= 0)
        return 0;
    int val = 1;
    Queue<Integer> Q2 = new LinkedList<Integer>();
    Queue<Integer> Q3 = new LinkedList<Integer>();
    Queue<Integer> Q5 = new LinkedList<Integer>();
    Q2.add(2);
    Q3.add(3);
    Q5.add(5);
    for (--k; k > 0; --k) { // We’ve done one iteration already.
        val = Math.min(Q2.peek().intValue(),
                Math.min(Q3.peek().intValue(), Q5.peek().intValue()));
        if (val == Q5.peek()) {
            Q5.remove();
        } else {
            if (val == Q3.peek()) {
                Q3.remove();
            } else { // must be from Q2
                Q2.remove();
                Q2.add(val * 2);
            }
            Q3.add(val * 3);
        }
        Q5.add(val * 5);
    }
    return val;
}

References
http://www.geeksforgeeks.org/ugly-numbers/
http://stackoverflow.com/questions/4600048/nth-ugly-number
http://tianrunhe.wordpress.com/2012/04/03/find-the-kth-number-with-prime-factors-3-5-and-7/

Read More

Given a string s1 and a string s2, write a snippet to say whether s2 is a rotation of s1 using only one call to strstr routine? (eg given s1 = ABCD and s2 = CDAB, return true, given s1 = ABCD, and s2 = ACBD , return false)

Syntax of strstr 

const char * strstr ( const char * str1, const char * str2 );

 Returns a pointer to the first occurrence of str2 in str1, or a null pointer if str2 is not part of str1.
The matching process does not include the terminating null-characters.

Approach1
Append str1 to itself and do a strstr for str2. That should work.
(I am assuming strstr looks for string x within string y).
But this fails sometime...for eg. s1 = ABCDA, s2 = BCDA, s2s2 = BCDABCDA
s2s2 now contains s1, but it is not a rotation of s1.
probably other corner cases exist. 

So we can improve it...by first checking whether s1 and s2 have equal number of characters or not.

Read More