# Rendezvous with C/C++

/*
PROBLEM
=======
Given 2*N  boxes in  line  side  by  side  (N<=5).  Two
adjacent boxes are empty, and the other boxes contain N-1
symbols "A" and N-1 symbols "B".

Example for N=5:

| A | B | B | A |   |   | A | B | A | B |

Exchanging rule:

The content  of any two adjacent non-empty boxes can
be moved  into the  two empty ones, preserving their
order.

Aim:

Obtain a  configuration where  all A's are placed to
the left of all B's, no matter where the empty boxes
are.

*/

# include <iostream.h>
# include <stdio.h>

int getblankposition(int size, char* arrBoxes){
if(!arrBoxes) return -1; //if the array is null return -1
int position=0;
for(int i=0;i<size;i++){
if(arrBoxes[i]==' '){
position=i;
break; //break on first find
} //end if
} // end for
return position;
}

int evaluateRank(int windowPos, int blankPos, int size, char* arrBoxes){
// rank is evaluated on the basis of number of sequences formed
if(!arrBoxes) return -1;
// there will be two conditions based on where the window is with reference to the blanks
// under no ciscumstances will both be equal
int fCounter=0;
int bCounter=0;
int fCount=0;
int bCount=0;

if(windowPos>blankPos){
// count UP the array
for(fCounter=(blankPos+2);fCounter<windowPos;fCounter++){
(arrBoxes[fCounter]==arrBoxes[windowPos+1])?fCount++:break;
}//end for

// count DOWN the array
for(bCounter=(blankPos-1);bCounter>=0;bCounter--){
(arrBoxes[bCounter]==arrBoxes[windowPos])?bCount++:break;
}//end for
}
else{
// here windowPos<blankpos
// count UP the array
for(fCounter=(blankpos+2);fCounter<size;fCounter++){
(arrBoxes[fCounter]==arrBoxes[windowPos+1])?fCount++:break;
} //end for

// count DOWN the array
for(bCounter=(blankPos-1);bCounter>(windowPos+1);bCounter--){
(arrBoxes[bCounter]==arrBoxes[windowPos])?bCount++:break;
}//end for
} // end if..else
// at this point return rank
return (bCount+fCount);
}

void rearrange(int size, char* arrBoxes){
if(!arrBoxes) return; // if the array is null exit
int blankPos; //position of the first blank
blankPos = getblankposition(size, arrBoxes);

if(blankPos==-1) return; //some error here
// here we have the blank position
// now need to find the rank for each two character window.

int bSwitch=1; //flag to continue the loop
int rank=0;
int rankPos=0;

while(bSwitch){
for(int i=0;i<(size-1);i++){
int tempRank = evaluateRank(i,blankPos, size, arrBoxes);
if(tempRank>rank){
// make this the new rank
rank = tempRank;
rankPos = i;
}//end if
}//end for
// at this point, we have the position that is going to provide the best move
// so perform the exchange
arrBoxes[rankPos] ^= arrBoxes[blankPos];
arrBoxes[blankPos] ^= arrBoxes[rankPos];
arrBoxes[rankPos] ^= arrBoxes[blankPos];

// exchange the second positions on each side
arrBoxes[rankPos+1] ^= arrBoxes[blankPos+1];
arrBoxes[blankPos+1] ^= arrBoxes[rankPos+1];
arrBoxes[rankPos+1] ^= arrBoxes[blankPos+1];

// now the blanks have moved, so set the new blank position
blankPos = rankPos;

// check if we need to proceed
if(rank==(size-4)){
bSwitch=0;
}
} //end while
}

Tags