Skip to content

Instantly share code, notes, and snippets.

@quangnle
Created April 17, 2024 09:26
Show Gist options
  • Save quangnle/a1d200290abc227fd3b0e3de00e8aea9 to your computer and use it in GitHub Desktop.
Save quangnle/a1d200290abc227fd3b0e3de00e8aea9 to your computer and use it in GitHub Desktop.
/*
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("")));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment