CareerCup

public class MainTask {
	public static int FindPos(char letter,char[] str) {
		int retPos=0;
		for(int i=0;i<=str.length-1;i++){
			if(str[i]==letter){
				retPos=i;
				break;
			}
		}
		return(retPos);
	}
	public static char[] MoveRight(char[] str,int pos,int npos)
	{
		char[] retArray;
		char chTemp;
		retArray=str.clone();
		for(int i=pos;i<npos;i=i+1){
			chTemp=retArray[i];
			retArray[i]=retArray[i+1];
			retArray[i+1]=chTemp;
		}
		return(retArray);
	}
	public static char[] MoveLeft(char[] str,int pos,int npos)
	{
		char[] retArray;
		char chTemp;
		retArray=str.clone();
		for(int i=pos;i>npos;i=i-1){
			chTemp=retArray[i];
			retArray[i]=retArray[i-1];
			retArray[i-1]=chTemp;
		}
		return(retArray);
	}
	public static void main(String[] args) {
		String A = "NUMBERS";
        String B = "ERUNMBS";
        System.out.println("started");
        char[] aChar = A.toCharArray();
        char[] bChar = B.toCharArray();
        System.out.println("A: " + String.valueOf(aChar));
        System.out.println("B: " + String.valueOf(bChar));
        int numMoves = 0;
        int numPos=0;
        for(int i=0;i<=aChar.length-1;i++)
        {
        	if(aChar[i]!=bChar[i]){
        		numPos=FindPos(aChar[i],bChar);
        		if(numPos<i){
        			bChar=MoveRight(bChar,numPos,i);
        		}
        		if(numPos>i){
        			bChar=MoveLeft(bChar,numPos,i);
        		}
        		numMoves=numMoves+(numPos);
        	}
        }
        System.out.println("-----------------------------");
        System.out.println("A: " + String.valueOf(aChar));
        System.out.println("B: " + String.valueOf(bChar));
        System.out.println("Number of swaps: " + numMoves);
	}
}

*** I am the miloslav. This solution is made in america ****

Step1: Take one word and call it source. Take the other and call is destination. initialize variable totalsteps = 0
Step2: Take the source and compute, for each letter, the swap distance between the letter in its current position and the letter in its correct target position. Don't forget about the wrap around.
Source: C D A B
Target: A B C D
Step 3: Define a badness metric which is the sum of swap distances for all letters of the given word. If badness metric is 0, you're done. Consider all possible single swaps for the given word, and compute the badness metric of these derivative words.
Source C(2) D (2) A(2) B(2) --> total edit distance is 8
Options to transition to: C (2) D(2) B(1) A(1), D (1) C(1) A(2) B(2), ......etc
Step4: If there exists a derivative word that has a badness metric that is less than the badness metric of the source, find the derivative word with the lowest badness metric and make it the new source and go to step 1. Flush the temporary cache (described below) and Increment total steps.

If there does not exist a derivative word that has a badness metric less than the badness metric of the source, there will always exist a word with the badness metric which is equal to the badness metric of the source. In this case, remember the source in a temporary cache, and choose a new source which we have not already visited (i.e., is not there in the temporary cache). Now go to step 1.

{
        static void Main(string[] args)
        {
            string str1 = "A B C D E";

            string str2 = "E A C D B";

            Console.WriteLine(PrintMinSteps(str1, str2));

        }

        public static int PrintMinSteps(string str1, string str2)
        {
            if (str1 == str2)
                return 0;

            if (str1.Length == 0)
                return str2.Length;

            if (str2.Length == 0)
                return str1.Length;

            int len1 = PrintMinSteps(str1.Substring(1), str2) + 1;
            int len2 = PrintMinSteps(str1, str2.Substring(1)) + 1;
            int len3 = PrintMinSteps(str1.Substring(1), str2.Substring(1)) + (str1[0]==str2[0]?0:1) ;

            return Math.Min(len1, Math.Min(len2, len3));
        }
    }

Scan both strings from left to right, let n be the index.

When you find a mismatch, then either A[n] char or B[n] must be replaced by the corresponding character in the other string. Find the nearest matching character to the right of n (either the nearest in A[n+1..] which matches B[n] or the nearest in B[n+1..] which matches A[n]). Move this character into the right place and continue.

For the first character, you can start searching from the end of the string, but once you have started matching characters then I cannot see how to use the "swap first and last characters" function to improve the result.

Here is my bubblesort-ish algo- O(n^2) :(

void makeSame(const std::string& orig, std::string& copy)
{
    const int numLetters = orig.size();
    for(int i = 0; i < numLetters; i++)
    {
        int iterIdx = i;

        while(copy.at(i) != orig.at(i))
        {
            if((iterIdx + 1) < numLetters)
            {
                char& oldChar = copy.at(iterIdx);
                iterIdx++;
                char& newChar = copy.at(iterIdx);

                char tmpChar = oldChar;
                oldChar = newChar;
                newChar = tmpChar;
            }
            else
            {
                // start swapping again
                iterIdx = i;
            }
        }
    }
}

cout<<"Hello World!";

Simply, we can use Bubble Sort technique, which swaps consecutive items.
In such a way, we have to sort both the strings, then it will be equal.

I think, this is the most simple and automated algorithm.

That won't get you the minimum number of moves, but the algorithmic approach of "bubble sort" isn't far off. For example, if you have:

ZYXA
ZYAX

Bubble sort would require: almost 2n^2 moves.

If your comparator function wasn't "alphabetical order" and instead matching string A, that should work.

Using String A as comparator. If a character in position i doesn't match (e.g. Ai != Bi) then swap.

public class TwoStringsMatching {

    public static void main(String[] args) {
        String A = "ZYXA";
        String B = "ZYAX";

        char[] aChar = A.toCharArray();
        char[] bChar = B.toCharArray();
        char temp;
        System.out.println("A: " + String.valueOf(aChar));
        System.out.println("B: " + String.valueOf(bChar));

        int numMoves = 0;
        int noSwaps = 0;
        while(noSwaps != aChar.length-1) {
            noSwaps = 0;
            for (int i = 0; i < aChar.length-1; i++) { //currently ignore the last character
                if (aChar[i] != bChar[i]) {
                    numMoves++;
                    temp = bChar[i];
                    bChar[i] = bChar[i+1];
                    bChar[i+1] = temp;
                } else {
                    noSwaps++;
                }
            }
        }
        System.out.println("A: " + String.valueOf(aChar));
        System.out.println("B: " + String.valueOf(bChar));
        System.out.println("Number of swamps: " + numMoves);
    }
}