Thread: i need help with this question:

2n ambassadors are invited to a meeting. Every ambassador has at most n-1 enemies. Devise an algorithm to prove that the ambassadors can be seated around a table, so that nobody sits next to an enemy.note: the table is round

am a beginner with c programming,i haven`t tried anything,but i`ll look up the links,thanx

Isn't this a sorting problem? All you have to do is make sure person A doesn't hate B and sort on that criteria.

Marcus,

I apologize that it's taken me so long to reply. The question's solution pertains to a topic in mathematics, namely matching. The general summary is to match the ambassador's to seats which meet the "nobody sits next to an enemy" requirement/constraint. Something that programmers do deal with or if not then the engineer stays late leaving detailed instructions.... The proof that it can be accomplished is given by the chromatic number of the graph, that is the number of colors required so that no two neighbors have the same color. If every ambassador had n-1 enemies, it would leave n+1 potential neighbors...etc.

I've been tinkering with some solutions for a seating chart in C code, and I'll have something posted to look at soon. The text books I am using are: Dossey, et. al. Discrete Mathematics 3rd Ed. and Cormen, et. al. Introduction to Alogrithms 2nd Ed. Frankly, I am rather flattered that you would expect a programmer to deal with these problems, and it's part of why I got into mathematics.

By the way Quzah, the ambassadors are not assassins so the edges are bi-directional. Where did you find the question Marcus? To address Elysia's point, it may have been more appropriately placed in the networking board or non-programming board...I'm not sure either.

Best Regards,

New Ink -- Henry

Marcus,

Again I apologize about taking so long to close this thread. I've only been able to spend a couple hours a day on it, and I didn't find the thread until the 10th (Tues.). So I read through the text books, and found that the matching problems are the right sort. Although the problem lends itself to a little bit of guessing, and I think maybe I should have checked in with an Operations Research text...

So rather than attempting to populate the seats directly while reading the enemy list, I chose to approach the seating with an ideal arrangement (which happened to be a maximal matching) and apply the enemy constraints via a series of row swaps. I don't get to do these a lot lately, so suggestions are welcome, and I look forward to reading any replies.

I tested it with some small inputs, and it produced a completely accurate seating chart every time. The input files I wrote, produced bugs because the text encoding in my editor and the command line are different...I'd like any suggestions about that one.

Here is the algorithm:

Read the enemy matrix.
Assume a seating chart (a maximal matching between ambassadors and seats).
For every contradictory seating arrangement, swap seats until there is no contradiction.

The code that implements this:

Code:

#include <stdio.h>
#include <stdlib.h>

#define MAX_LINE 256
#define TRUE 1==1
#define FALSE 1==0

int **createMatrix(int rows, int columns);
int **createIdentity( int rows );
void releaseMatrix( int **mat, int rows, int columns );

int **readAdjacency( FILE *fp, int *rows, int *columns );

int getNeighbors( int **mat, int rows, int columns, int ambassador /* zero index */, int *neighbors );

int getRowWithOne( int **mat, int rows, int column );
int getColWithOne( int **mat, int columns, int row );
void rowSwap( int **mat, int columns, int swap1 /* zero index */, int swap2 );

void printSeating( int **mat, int rows, int columns );


int main()
{
   int **enemies;
   int **seats;
   int neighbors[2];
   int current_seat;
   
   int rows;
   
   int hostile;
   int j;
   int k;
   
   enemies = readAdjacency( stdin, &rows, &rows );  // enemy list
   seats = createIdentity( rows );  // ideal seating
   
   // adjust from the ideal seating to a conflict free arrangement
   for( j = 0; j < rows; j++ )
   {
      current_seat = getNeighbors( seats, rows, rows, j, neighbors );  
         // always != -1 since started with ideal
      if( TRUE == enemies[j][ neighbors[0] ] || TRUE == enemies[j][ neighbors[1] ] )
      {
         // currently seated with an enemy
         hostile = TRUE;
      }         
      
      while( hostile )
      {
         // swap until seated with an acceptable partners
         for( k = 0; k < rows && hostile; k++ )
         {
            rowSwap( seats, rows, current_seat, k );
            
            current_seat = getNeighbors( seats, rows, rows, j, neighbors );

            if( FALSE == enemies[j][ neighbors[0] ] && FALSE == enemies[j][ neighbors[1] ] )
            {
               hostile = FALSE;
            }
         }
      }
   }
   
   printSeating( seats, rows, rows );
   releaseMatrix( enemies, rows, rows );
   releaseMatrix( seats, rows, rows );
   
   return 0;
}

// read from fp.  formatted:
// 2n\n
// Ai   Ak  Aj  ... An-1\n
// ...
// EOF (ctrl+d)
// Where 2n, A are integer's
int **readAdjacency( FILE *fp, int *rows, int *columns )
{
   int **mat;
   int reading;

   int selected;
   int j;
   int k;
   
   int rd;
   int water;
   char buffer[MAX_LINE];

   fscanf( fp, "%d\n", &k );
   
   *rows = k;
   *columns = k;
   mat = createMatrix( k, k );

   selected = FALSE;   
   water = 0;
   reading = TRUE;
    
   while( ! feof( fp ) && reading )
   {
      rd = fgetc( fp );
      
      switch( rd )
      {
         case EOF:       // end of input
         
            reading = FALSE;

         case '\n':      // next ambassador

            if( FALSE == selected )  // if we weren't reading one...finished
            {
               reading = FALSE;
            }
            else               // update
            {
               buffer[water] = '\0';
               k = atoi( buffer ) - 1;
               water = 0;
               mat[j][k] = mat[k][j] = TRUE;   // not a friendly ambassador
               selected = FALSE;
            }
            
            break;
            
         case '\t':      // next number

            if( FALSE == selected )
            {
               selected = TRUE;
               buffer[water] = '\0';
               j = atoi( buffer ) - 1;
               water = 0;
            }
            else
            {
               buffer[water] = '\0';
               k = atoi( buffer ) - 1;
               water = 0;
               
               mat[j][k] = mat[k][j] = TRUE;   // not a friendly ambassador
            }
            
            break;
            
         default:        // current number
         
            buffer[water++] = rd;
      }
   }
   
   return mat;
}

int **createMatrix(int rows, int columns)
{
    int **mat;
    int j;
    int k;
    
    mat = (int**) malloc( rows * sizeof(int*) );
    
    if( NULL == mat )
    {
        fprintf( stderr, "Problem allocating memory in createMatrix...exiting." );
        
        exit( 1 );
    }
    
    for( j = 0; j < rows; j++ )
    {
       mat[j] = (int*) malloc( columns * sizeof(int) );

       if( NULL == mat[j] )
       {
           fprintf( stderr, "Problem allocating memory in createMatrix...exiting." );
           
           for( k = j-1; k >= 0; k-- )
           {
              free(mat[k]);
           }
           free(mat);
        
           exit( 1 );
       }
       
       for( k = 0; k < columns; k++ )
       {
          mat[j][k] = FALSE;  // populate with zeros
       }
   }
   
   return mat;
}

int **createIdentity( int rows )
{
   int **identity = createMatrix( rows, rows );
   
   while(rows > 0)
   {
      identity[rows - 1][rows - 1] = TRUE;
      rows--;
   }
   
   return identity;
}

void releaseMatrix( int **mat, int rows, int columns )
{
   int j;
   
   if( NULL == mat )
   {
      return;
   }
   
   for( j = 0; j < rows; j++ )
   {
      free( mat[j] );
   }
   free( mat );
   
   return;
}

void rowSwap( int **mat, int columns, int row1 /* zero index */, int row2 )
{
   int temp;

   while( 0 < columns )
   {
      temp = mat[row1][columns - 1];
      mat[row1][columns - 1] = mat[row2][columns - 1];
      mat[row2][columns - 1] = temp;
      
      columns--;
   }

   return;
}

int getNeighbors(                     // -1 if there is not any seat assigned
    int **mat,                        // seating chart
    int rows,                         // size information
    int columns, 
    int ambassador /* zero index */,  // ambassador of interest
    int *neighbors )                  // current pair of ambassador's adjacent
{
   int seat;
   
   seat = getRowWithOne( mat, rows, ambassador );
   
   if( -1 != seat )
   {
      if( 0 == seat )
      {
         neighbors[0] = getColWithOne( mat, columns, rows -1 );
      }
      else
      {
         neighbors[0] = getColWithOne( mat, columns, seat-1 );
      }
      neighbors[1] = getColWithOne( mat, columns, (seat + 1) % rows );
   }
   
   return seat;
}

int getRowWithOne( int **mat, int rows, int column )
{
   int result = -1;
   int j;
   
   for( j = 0; j < rows; j++ )
   {
      if( 1 == mat[j][column] )
      {
         result = j;
         
         return result;
      }
   }
   
   return result;
}

int getColWithOne( int **mat, int columns, int row )
{
   int result = -1;
   int j;
   
   for( j = 0; j < columns; j++ )
   {
      if( 1 == mat[row][j] )
      {
         result = j;
         
         return result;
      }
   }
   
   return result;
}

void printSeating( int **mat, int rows, int columns )
{
   int j, k;
   
   fprintf( stdout, "      " );
   
   for( j = 0; j < columns; j++ )
   {
      fprintf( stdout, "A%d   ", j+1 );
   }
   fprintf( stdout, "\n" );
   
   for( j = 0; j < rows; j++ )
   {
      fprintf( stdout, "S%d   ", j+1 );
      
      for( k = 0; k < columns; k++ )
      {
         fprintf( stdout, " %d   ", mat[j][k] );
      }
      fprintf( stdout, "\n" );
   }
   
   return;
}

I ran it at the prompt with 'script' and this is the typescript that was produced:

Code:

Script started on Fri Aug 13 18:54:46 2010
]0;~

Henry@local-a3120676b ~

$ gcc -g ambassadors2.c
]0;~

Henry@local-a3120676b ~

$ ./a.exe
4
1	2
3	4
      A1   A2   A3   A4   
S1    0    1    0    0   
S2    0    0    1    0   
S3    1    0    0    0   
S4    0    0    0    1   
]0;~

Henry@local-a3120676b ~

$ exit
exit

Script done on Fri Aug 13 18:55:23 2010

I feel a little awkward about the length of the post, but I wanted to be as clear as possible. It seems that you may have given up on us, so I wanted to offer as much information as possible Marcus. If you notice anything that you have questions about please remark.

Best Regards,

New Ink -- Henry

Salem,

No kidding. I thought this was a rather elegant solution, but I wonder what the OP came up with.... It was a little early to optimize when I got it running, but I think that one could replace the enemy list with an adjacency list to save some space. Of course, then the measuring the constraints portion of the algorithm would look different. And I left a #define from an earlier revision about a maximum line that is superfluous....

Best Regards,

New Ink -- Henry

Whiteflags,

Yes it is a sorting problem in that sorting is a matching problem. Rather than using the ordering principle on real numbers, the ordering requirement is derived from the enemy list.

Best Regards,

New Ink -- Henry

I've had to suffer from clueless dolts who couldn't find their ass in the dark, and I've no interest in pushing more clueless people into the workplace.

Sounds like excellent job security to me!

< just kidding, of course! >

The problem reminds me a lot of a Sudoku puzzle. Very constrained guest/number placement.

Salem,

I agree that my time may be better spent, but I haven't landed a contract since I signed up on the contracting boards (e.g. ELance, vWorker, Freelancer, ...etc.) a few years ago. I can't even get HR to call me back most of the time. I'm mostly interested in building a little bit of background, and actually getting something done rather than getting shot down in the proposal stage.

Originally Posted by Salem

The elegance (or otherwise) is immaterial.

It does a little, in that it is a measure of my sophistication, and desire to learn. At least, I think. If nothing else, it saves a lot of time during the maintenance phase of the life-cycle.

Originally Posted by Salem

Perhaps you would be interested in nurse-maiding them when they get a job...

Absolutely not, no sir. And to quote myself from other boards: If this does happen to relate to graded work, if any, I never got into plagiarism because it is a question of honour. If that isn't enough to complete the premise, I must also point out that one can not take us to the test...or any other controlled environment like a safe room. It's nice to see an answer though...I can appreciate that myself. From what I read that's what these boards are for.... I verified that with the guidelines and faq.

Originally Posted by Salem

I've had to suffer from clueless dolts who couldn't find their ass in the dark, and I've no interest in pushing more clueless people into the workplace.

Then you've accomplished more success than I. I didn't put up with them, and I didn't push either. I haven't been gainfully employed in this field for about five years now, because it would seem that what those "...clueless dolts..." lack in ability, they make up for with slander and poor management decisions. Perhaps, I could get one of those persuasive references that they issue with cold blooded precision?

If I find the question on the board, I assume it is fair game. I will check out the references you are suggesting, but occasionally it edifies my need to be able to brag to recruiters when I can refer to a venue such as this. Especially when I come across like a dinosaur to some of the hack and slashers that treat elegance as vanity -- rather than realize that the maintenance phase of the software life cycle is supposed to go for a while.

Now, before this starts sounding like a support group, I was thinking about the constraints on the problem. If there were an odd number of ambassadors, I don't think it is deterministically possible (in the worst case). Would anyone care to debate that point? I'm rather confident that one could use the chromatic number of the graph to complete the proof, but I've got a lot on my plate at the moment...trying to blend in.

Best Regards,

New Ink -- Henry

By the way, thank you for the guidance. I really appreciate it.

Best Regards.