Tower Of Hanoi - Non-recursive Approach

Tower Of Hanoi

                                                             --  shaikzakir3149@gmail.com

Hello all, this is my first post. Hope you find it useful ...


Implement non-recursive Towers of Hanoi. Given the number n of disks as input, maintain appropriate pegs/rods to simulate the movement of the disks among the three pegs: Source, Auxilary & Destination.
Output the sequence of moves of the disks. Following is an example of the output expected by your program.

No. of disks: 3
Sequence of Moves
1. Source → Destination
2. Source → Auxilary
3. Destination → Auxilary
4. Source → Destination
5. Auxilary → Source
6. Auxilary → Destination
7. Source → Destination

Note: Remember that towers of hanoi can be solved in (2^n - 1) at the best for given n disks.

Algorithm:

While size of Destination is less not equal to n
do
{
If num of disks is even then

       Make legal move between Source and Auxilary
       Make the legal move between pegs Source and Destination

else

        Make the legal move between pegs Source and Destination  
        Make the legal move between pegs Source and Auxilary

endif

Make legal move between pegs Auxilary and Destination



}
end While


Note that a legal move is one which abides by the rules of the puzzle. Only a smaller disk can be moved onto a larger disk.

Running Time Complexity :

 The runtime complexity of this algorithm is O((2^n - 1)/3) which is equivalent to O(2^n). Clearly the stack operations (push, pop and peek) have a runtime equal to O(1).

The code is given in Java.

Source Code :

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
//package tower.of.hanoi;
import java.io.*;
import java.util.Stack;
import java.util.EmptyStackException;
/**
 *
 * @author Shaik
 */
public class TowerOfHanoi {

    
    public static int legalMove(Stack A, Stack B)
    {
        int a,b;
        try {
        a = Integer.parseInt(A.peek().toString());
        }
        catch(EmptyStackException e){
        a = 0;    
        }
        try {
            b = Integer.parseInt(B.peek().toString());
        }
        catch(EmptyStackException e){
        b = 0;    
        }
        if(a==b) return 0;
        if(a == 0)             // If peg A is empty, then pop from B and push the disk onto A
    {
        A.push(B.pop());
            return 2;           // Return 2 as move occurred from B to A
    }
        else if(b == 0)        // If peg B is empty, then pop from A and push the disk onto B
        {
        B.push(A.pop());
        return 1;           // Return 1 since move occurred from A to B
    }
        
        if(a<b)
        {
        B.push(A.pop());
        return 1;               // Return 1 since move occurred from A to B
        }
        else if(a > b)            // value of top disk of peg A is greater than the value of topmost disk of peg B
        {
        A.push(B.pop());
        return 2;               // Return 2 since move occurred from B to A
        }
        return -1;
    }
        
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        int stepNumber = 0;
        int status = 0;
        try {
        Stack Source = new Stack();
        Stack Auxilary = new Stack();
        Stack Destination = new Stack();
        
        System.out.println("Enter the number of disks : ");
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(input.readLine());
        if(n<=0)
        {
            System.out.println("Sorry wrong input, negative numbers not allowed.");
            System.exit(1);
        }
        for(int i=n; i>0; i--)
            Source.push(i);
        int m = n%2;
        do {
            if(m==1)
            {
                if((status = legalMove(Source,Destination)) == 1)
                    System.out.println((++stepNumber) + ". Source --> Destination");
                else if (status == 2)
                    System.out.println((++stepNumber) + ". Destination --> Source");
                
                if((status = legalMove(Source,Auxilary)) == 1)
                    System.out.println((++stepNumber) + ". Source --> Auxilary");
                else if(status == 2)
                    System.out.println((++stepNumber) + ". Auxilary --> Source");
                else 
                    break;
            }
            
            else
            {
                if((status = legalMove(Source,Auxilary)) == 1)  
                    System.out.println((++stepNumber) + ". Source --> Auxilary");
                else if (status == 2)
                    System.out.println((++stepNumber) + ". Auxilary --> Source");
                
                if((status = legalMove(Source,Destination)) == 1)
                    System.out.println((++stepNumber) + ". Source --> Destination");
                else if(status == 2)
                    System.out.println((++stepNumber) + ". Destination --> Source");
                
            }
            
            if((status = legalMove(Auxilary,Destination)) == 1) 
                System.out.println((++stepNumber) + ". Auxilary --> Destination");
            else if(status == 2)
                System.out.println((++stepNumber) + ". Destination --> Auxilary");
        }while(Destination.size()!=n);
        System.out.println("X-----------------------X");
        }         

        catch (Exception e){
        }
        }
    }

Interviewstreet String Reduction Solution C++

Interviewstreet Challenge String Reduction

Problem Statement

You are given a string consisting of a, b, and c's and following operation is allowed: Take any two adjacent character and they can be replaced with third character. For ex: a and b with c, b and c with a. Find length of smallest string, the operation can be applied repeatedly.
Ex: for input bcab, bcab -> aab -> ac -> b the output will be 1

Input: T test cases and next T lines contain strings to start with.
Output: T lines containing length of smallest possible resultant strings after applying operations repeatedly and optimally.

Algorithm

Use brute force approach, For each string
1) If length of string is 1 return 1
2) if len is 2 and both character are same return 2
3) else try to find smallest possible string from all possible ways i.e for every two adjacent character replace it with third character and invoke reduce again on this new smaller string until smallest possible string is reached.
4) If the string achieved is smaller then previous possible smaller string store and update minimum length.

If you have a different approach in mind, please share it in comments section for our readers.

Solution

// all 10 test cases passed

import java.util.Arrays;
import java.util.Scanner;

public class Solution {

int minimum=1;
int value=1;


private boolean reduce(String s1) {
char[] array=s1.toCharArray();
int len=array.length;
minimum =array.length;
boolean flag;
String cat;
if(len==1)
{
value=1;
return true;
}
else if(array[0]==array[1] && len == 2)
{
value=2;
return true;
}

for(int i=0;i<len-1;i++)
{
if(array[i+1]!=array[i])
{

String new_string

=Character.toString(array[i]).concat(Character.toString(array[i+1]));
char reduce =other(new_string);
String sub1="";
String sub2=Character.toString(reduce);
String sub3="";
if(i==1)
{
sub1=Character.toString(array[0]);
}else if(i>1)
{
sub1=s1.substring(0, i);
}
if(i+2<len-1)
{
sub3=s1.substring(i+2,len);
}else if(i+2==len-1)
{
sub3=Character.toString(array[i+2]);
}
cat=sub1+sub2+sub3;
flag=reduce(cat);
if(flag)
{
minimum=Math.min(minimum, value);
return flag;
}
}
}
return false;
}

private char other(String s1) {
char ret_value='b';
if (s1.equalsIgnoreCase("bc")|| s1.equalsIgnoreCase("cb")) {
ret_value='a';
}
else if (s1.equalsIgnoreCase("ab")|| s1.equalsIgnoreCase("ba")) {
ret_value='c';
}
return ret_value;
}
   
   
public static void main(String[] args) {
Scanner scan;
Solution obj = new Solution();
scan = new Scanner(System.in);
int T = scan.nextInt();
for (int i = 0; i < T; i++) {
String s1 = scan.next();
obj.reduce(s1);
System.out.println(obj.minimum);
}
}
       
}

Time Complexity

In a string of length n, there are n-1 2 character pairs, At max each of these pair would contain different character so for n-1 pairs we replace it with third character and call reduce again on new string of length n-1 which has n-2 pairs and so on....(n-1)*(n-2)*(n-3)..1 = (n-1)! times.
Surely it can be done in better way. If you find a better solution, update me.

find all anagrams of a word in a file, Java Code : Amazon Interview

Find all anagrams of a word in a file 

Amazon Interview (Dec 2011)

Problem Statement

Find all anagrams of a word in a file. Input -  only file name and word. Output - all set of word in file that are anagrams of word. Write production quality code.

Algorithm

1) Use a hashmap with string as key and list<string> as value where list of strings contain all anagrams of a key string.
2) For each word in the file, find beta string which is its sorted version ex abd is sorted version of bad, adb and dba. Put this word to that list whose key is this beta string. If it does not exist then create a new list with the beta string as key in map.
3) Finally print all strings from the list whose key is the input word(sorted/beta string).

If you have a different approach in mind, please share it in comments section for our readers.

Solution

import java.util.*;
import java.io.*;

public class Anagram {
    public static void main(String[] args) {
    String beta = args[1];

        try {

            Map<String, List<String>> m = 

                   new HashMap<String, List<String>>();

            Scanner s = new Scanner(new File(args[0]));
            while (s.hasNext()) {
                String word = s.next();
                String alpha = sorting(word);
                List<String> l = m.get(alpha);
                if (l == null)
                    m.put(alpha, l=new ArrayList<String>());
                l.add(word);
            }

         List<String> l = m.get(sorting(beta));
       Object[] arr = l.toArray();
           for (int i=0; i < arr.length; i++)
                System.out.println(arr[i]);

        }
    catch (Exception e) {
            System.out.println(e);
            System.exit(1);
        }

    }

    private static String sorting(String s) {
        char[] a = s.toCharArray();
        Arrays.sort(a);
        return new String(a);
    }
}

Time Complexity

O(n) for visiting each word in file once. You can't do it actually in O(n) if you consider the time complexity involved in sorting each word.
If you consider that time complexity involve with sorting also, then you should know that java uses quicksort algorithm to sort char array for which time complexity is O(mlogm) and I have applied sorting function in my code to each word of file .Therefore the time complexity would be O(n*mlogm), where longest word has length m.

Merge two special arrays O(n) Code

Merge two special arrays with given conditions. 

Amazon Interview (May 2012).

 

 Problem Statement

Given two arrays having some elements in common, write a program to merge them such that all the elements occurring before common elements in both arrays also lie before common elements in merged array also and common element occurs only once in merged array.
Array can contain both alphabets and integers.
The elements lying before common element of both arrays can appear in any order in merged array.
Write a O(n) time complexity code.
Ex. A = [z,a,b,c,d,e,f]
       B = [k,g,a,h,b,f]
   Ans = [z,k,g,a,h,b,c,d,e,f]

Algorithm

1) Put elements of one array in hash-table.
2) Start incrementing pointer in 2nd array from 1 to n, if the element lie in hash-table put all elements before it in 1st array into the merged array else put this element into merged array.
3) Put any remaining elements into the merged array

If you have a different approach in mind, please share it in comments section for our readers.

Solution

import java.util.Map;
import java.util.HashMap;

class Solution
{

public static void main(String arg[])
{
char a[] = arg[0].toCharArray();
char b[] = arg[1].toCharArray();
char c[] = new char[a.length+b.length];
merge(a,b,c);
String s = new String(c);
System.out.println(s);
}

private static void merge(char a[], char b[], char c[]) {

Map<Character, Integer> m1 = new HashMap<Character, Integer>();

int i,j,k,l;

for(i=0;i<a.length;i++)
    m1.put(a[i],i);
       
l=0;i=0;j=0;
while(j<b.length) {
   
    if(m1.containsKey(b[j])) {
   
        k = m1.get(b[j]);
        while(i<=k)
            c[l++] = a[i++];
        j++;
    }
    else c[l++] = b[j++];
}
while(i<a.length)
    c[l++] = a[i++];
   
}
}   

Time Complexity: 

O(2n+m) where n is size of first array and m is size of second array. We travel first array twice once while putting its elements into merged array and second time while merging, therefore 2n for first array.



If you find this blog somewhat helpful, please give a +1.