aaabbb.js

/*
Problem:
A group of 2n people, consisting of n individuals from Team A and n individuals from Team B, are seated in a row of 2n+1 chairs in the following arrangement:
A...A_B...B (where "_" represents an empty seat)

The task is to find a method to rearrange the seating positions of each person to achieve the following order:
B...B_A...B

Rules:
- In each step, only one person can be moved to an empty seat.
- A person can be moved only if they meet one of the following conditions:
a. They are seated directly to the left or right of an empty seat.
b. They are separated from an empty seat by exactly one person from the opposite team.

Example:
For the case n=1, A_B needs to be rearranged to B_A:
A_B => _AB => B_A

For the case n=2, AA_BB needs to be rearranged to BB_AA:
AA_BB => A_ABB => ABA_B => AB_AB => BAAB => B_AAB => BA_AB => BABA => BAB_A => B_BAA => BB_AA
*/
class State {
    constructor(state, prev = null){
        this.state = state;
        this.prev = prev;
    }

    generateNewStates(){
        const newStates = [];
        for (let i=0; i<this.state.length; i++){
            if (this.state[i] == "_"){                
                if (i == 0) {
                    const newState = [...this.state];
                    newState[0] = this.state[1];
                    newState[1] = "_";                    
                    newStates.push(new State(newState, this));
                    break;
                }
                else if (i==this.state.length-1){
                    const newState = [...this.state];
                    newState[this.state.length-1] = this.state[this.state.length-2];
                    newState[this.state.length-2] = "_";
                    newStates.push(new State(newState, this));
                    break;
                } else {
                    const newState1 = [...this.state];
                    newState1[i] = this.state[i+1];
                    newState1[i+1] = "_";                    
                    newStates.push(new State(newState1, this));
                    const newState2 = [...this.state];
                    newState2[i] = this.state[i-1];
                    newState2[i-1] = "_";
                    newStates.push(new State(newState2, this));

                    if (i-2 >=0 && this.state[i-2] != this.state[i-1]){
                        const newState3 = [...this.state];
                        newState3[i] = this.state[i-2];
                        newState3[i-2] = "_";
                        newStates.push(new State(newState3, this));
                    }

                    if (i+2 < this.state.length && this.state[i+2] != this.state[i+1]){
                        const newState4 = [...this.state];
                        newState4[i] = this.state[i+2];
                        newState4[i+2] = "_";
                        newStates.push(new State(newState4, this));
                    }

                    break;
                }
            }
        }
        return newStates;
    }
}

function solve(initState, targetState){
    const queue = [];
    const visited = new Set();
    queue.push(initState);
    visited.add(initState);
    while (queue.length > 0){
        const state = queue.shift();
        if (state.state.join("") == targetState){
            return state;
        }
        const newStates = state.generateNewStates();                
        for (let i=0; i<newStates.length; i++){
            if (!visited.has(newStates[i].state.join(""))){
                queue.push(newStates[i]);                
            }
        }
        visited.add(state.state.join(""));
    }
}

const startState = new State(["A","A","A","A","A","A","_","B","B","B","B","B","B"]);
//const newStates = startState.generateNewStates();
//newStates.forEach(s => console.log(s.state));
let s = solve(startState, "BBBBBB_AAAAAA");
const solution = [];

while (s != null){
    solution.push(s.state);
    s = s.prev;
}
solution.reverse();
solution.forEach(s => console.log(s.join("")));