Share via

Rendezvous with C/C++

  • Article

/*
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
}

Comments