i need help with this question:

This is a discussion on i need help with this question: within the C Programming forums, part of the General Programming Boards category; 2n ambassadors are invited to a meeting. Every ambassador has at most n-1 enemies. Devise an algorithm to prove that ...

  1. #1
    Registered User
    Join Date
    Aug 2010
    Posts
    2

    Unhappy 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

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,968
    What have you tried?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Aug 2010
    Posts
    2
    am a beginner with c programming,i haven`t tried anything,but i`ll look up the links,thanx

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,525
    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.

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Can A1 be A2's enemy without A2 being A1's enemy?


    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,170
    The first step is to formulate an algorithm for the task. That has nothing to do with C.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  7. #7
    Registered User
    Join Date
    Jul 2010
    Location
    Oklahoma
    Posts
    107
    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

  8. #8
    Registered User
    Join Date
    Jul 2010
    Location
    Oklahoma
    Posts
    107
    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

  9. #9
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,336
    No worries.
    The OP hasn't been back since it became obvious to all that they weren't going to get their homework done for them in time.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  10. #10
    Registered User
    Join Date
    Jul 2010
    Location
    Oklahoma
    Posts
    107
    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

  11. #11
    Registered User
    Join Date
    Jul 2010
    Location
    Oklahoma
    Posts
    107
    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

  12. #12
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,336
    The elegance (or otherwise) is immaterial.

    The fact is, it's a TOTAL answer that some lazy sod is just going to hand in without so much as a bean of effort on their part. But hey, it's your free time, you can do what you want.

    Perhaps you would be interested in nurse-maiding them when they get a job, based on the worthless qualification obtained by getting others to do their homework.

    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.

    There is a very simple rule on this forum (and most others as well). Our effort matches their effort.
    If someone shows up with a copy/paste question, then all they'll get is a copy/paste answer.

    > but I wonder what the OP came up with
    ROFLMAO - you're kidding right?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  14. #14
    Registered User
    Join Date
    Jul 2010
    Location
    Oklahoma
    Posts
    107

    Talking What I want...

    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.

    Quote Originally Posted by Salem View Post
    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.

    Quote Originally Posted by Salem View Post
    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.

    Quote Originally Posted by Salem View Post
    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

  15. #15
    Registered User
    Join Date
    Jul 2010
    Location
    Oklahoma
    Posts
    107
    By the way, thank you for the guidance. I really appreciate it.

    Best Regards.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question bout my work
    By SirTalksAlots in forum C Programming
    Replies: 4
    Last Post: 07-18-2010, 03:23 PM
  2. A question about a question
    By hausburn in forum C++ Programming
    Replies: 3
    Last Post: 04-25-2010, 05:24 AM
  3. Alice....
    By Lurker in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 06-20-2005, 02:51 PM
  4. Debugging question
    By o_0 in forum C Programming
    Replies: 9
    Last Post: 10-10-2004, 05:51 PM
  5. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21