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 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 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;    
}