Transform one string to another string using BFS

Question

There is a string whose characters can only be either ‘a’, ‘b’ or ‘$’, there is only one ‘$’ in the string.

At each step, we can modify the string as follows:

1. ‘$’ can be swapped with its adjacent character, example “a$ba” can be changed to either “$aba” or “ab$a”.

2. You can swap $ character with next to adjacent character only if adjacent character is different from next to adjacent character. (For example ‘aba$ab’ can be converted into ‘a$abab’ or ‘ababa$’, but ‘ab$aab’ cannot be converted to ‘abaa$b’, because ‘a’ cannot jump over ‘a’).

You are given two strings, the initial state and the final state (lengths will be same), you have to output the minimum number of steps required to change the string in initial state to the string in the final state.

How to solve this problem using Breadth first search ?

example:
string s1 ,s2 ;
input: s1 = a$b , s2 = ab$
output: 1
input: s1 = aba$a , s2 = $baaa
output: 2

Answer 1

In Java:

private static int findTime(String s1, String s2) {
    Queue<String> queue = new LinkedList<>();
    queue.add(s1);
    Map<String, Boolean> visited = new HashMap<>();
    while (!queue.isEmpty()) {
        String in = queue.poll();
        Boolean isVisited = visited.get(in);
        if (isVisited != null && isVisited)
            continue;
        visited.put(in, true);
        int index = in.indexOf('$');
        //First case...
        if ((index + 1) < in.length()) {
            String in1 = in.substring(0, index) + in.charAt(index + 1) + "$";
            if ((index + 2) < in.length()) {
                in1 += in.substring(index + 2);
            }
            if (in1.equals(s2)) {
                return log(visited.size() + 1, 2);
            }
            if (in1.length() == s2.length()) {
                queue.add(in1);
            }
        }
        if (index > 0) {
            String in2 = "$" + in.charAt(index - 1) + in.substring(index + 1);
            if ((index - 2) >= 0) {
                in2 = in.substring(0, index - 1) + in2;
            }
            if (in2.equals(s2))
                return log(visited.size() + 1, 2);
            if (in2.length() == s2.length()) {
                queue.add(in2);
            }
        }
        //Second case...
        if ((index + 2) < in.length()) {
            if (in.charAt(index + 1) != in.charAt(index + 2)) {
                String in1 = in.substring(0, index) + in.charAt(index + 2)
                        + in.charAt(index + 1) + "$";
                if ((index + 3) < in.length()) {
                    in1 += in.substring(index + 3);
                }
                if (in1.equals(s2))
                    return log(visited.size() + 1, 2);
                if (in1.length() == s2.length()) {
                    queue.add(in1);
                }
            }
        }
        if (index - 1 > 0) {
            if (in.charAt(index - 1) != in.charAt(index - 2)) {
                String in2 = "$" + in.charAt(index - 1) + in.charAt(index - 2) +
                        in.substring(index + 1);
                if ((index - 3) >= 0) {
                    in2 = in.substring(0, index - 2) + in2;
                }
                if (in2.equals(s2))
                    return log(visited.size() + 1, 2);
                if (in2.length() == s2.length()) {
                    queue.add(in2);
                }
            }
        }
    }
    return 0;
}

static int log(int x, int base) {
    return (int) (Math.log(x) / Math.log(base));
}

System.out.println(findTime("a$b", "ab$"));
System.out.println(findTime("aba$a", "$baaa"));
System.out.println(findTime("abaa$a", "b$aaaa"));

Answer 2

in C++,

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int size;

struct str
{
    char a[1000];
    int change;
};

int position(char a[], char b)
{
    for(int i = 0; i < size; i++) {
        if(a[i] == b)
            return i;
    }
    return -1;
}

void swap(char a[], int pos, int shift)
{   
    int temp = a[pos];
    a[pos] = a[pos + shift];
    a[pos + shift] = temp;
}

int minChange(char arr[], char out[])
{
    std::queue <str> q;

    str i;
    strcpy(i.a, arr);
    i.change = 0;

    q.push(i);

    while(!q.empty()) {
        str fin = q.front();
        q.pop();
        if(strcmp(out, fin.a) == 0)
            return fin.change;

        int pos = position(fin.a, '$');

        if(pos > 0) {
            str temp;
            strcpy(temp.a, fin.a);
            swap(temp.a, pos, -1);
            temp.change = fin.change + 1;
            q.push(temp);
        }
        if(pos < size - 1) {
            str temp;
            strcpy(temp.a, fin.a);
            swap(temp.a, pos, 1);
            temp.change = fin.change + 1;
            q.push(temp);
        }
        if(pos > 1 && (fin.a[pos - 1] != fin.a[pos - 2])) {
            str temp;
            strcpy(temp.a, fin.a);
            swap(temp.a, pos, -2);
            temp.change = fin.change + 1;
            q.push(temp);
        }
        if(pos < size - 2 && (fin.a[pos + 1] != fin.a[pos + 2])) {
            str temp;
            strcpy(temp.a, fin.a);
            swap(temp.a, pos, 2);
            temp.change = fin.change + 1;
            q.push(temp);
        }
    }
}


int main()
{
    size = 3;
    cout<<minChange("a$b", "ab$")<<endl;
    size = 6;
    cout<<minChange("abaa$a", "b$aaaa")<<endl;
    size = 5;
    cout<<minChange("aba$a", "$baaa")<<endl;    
}

Answer 3

In Python:

from collections import deque

def swap(s, a, b):
    a, b = min(a,b), max(a,b)
    if 0 <= a < b < len(s):
        return s[:a] + s[b] + s[a] + s[b+1:]

def rotate(s, a, b):
    a, b = min(a,b), max(a,b)
    if 0<= a < b < len(s) and len(set(s[a:b+1])) == 3:
        return s[:a] + s[b:a:-1] + s[a] + s[b+1:]

def push(Q, changes, s):
    if s is not None:
        Q.append((changes, s))

def bfs(s1, s2):
    Q = deque()
    Q.append((0, s1))

    while Q:
        changes, s = Q.popleft()

        if s == s2: 
            return changes

        pos = s.index('$')

        push(Q, changes+1, swap(s, pos, pos-1))
        push(Q, changes+1, swap(s, pos, pos+1))
        push(Q, changes+1, rotate(s, pos, pos+2))
        push(Q, changes+1, rotate(s, pos-2, pos))


print bfs('a$b', 'ab$')
print bfs('abaa$a', 'b$aaaa')
print bfs('aba$a', '$baaa')

Answer 4

The problem can be solved via breadth-first search as follows, using C#-like pseudocode syntax.

string FinalState; (to be assigned the final state)

int DistanceToFinalState(string CurrentState)
{
  if (CurrentState == FinalState)
  {
    return 0; // end of recursion - strings match, distance is zero
  }
  else
  {
    int val1 = Infinity;
    int val2 = Infinity;
    int val3 = Infinity;
    int val4 = Infinity;
    if ($ is not at the leftmost position of CurrentState)
      val1 = DistanceToFinalState(CurrentState with $ moved to the left);
    if ($ is not at the rightmost position of CurrentState)
      val2 = DistanceToFinalState(CurrentState with $ move to the right);
    if ($ has 2 chars left to it)
      val3 = DistanceToFinalState(CurrentState with $ moved 2 chars to the left with the 2 skipped characters reversed);
    if ($ has 2 chars right to it)
      val4 = DistanceToFinalState(CurrentState with $ moved 2 chars to the right with the 2 skipped characters reversed);
    return minumum of {val1, val2, val3, val4};
  }
}

The initial problem can be solved by evaluating DistanceToFinalState(InitialState).