Solved

Seating arrangement program for foreign diplomats.  What type of data structure to use.

Posted on 2007-04-07
16
652 Views
Last Modified: 2008-05-23
I have to write a program that will create a seating arrangement for 10 diplomats from different countries.  The program has to take into account the languages spoken and the diplomatic relations between countries.  I am trying to figure out the best way to implement this program.
0
Comment
Question by:eric68
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 2
  • 2
  • +5
16 Comments
 

Author Comment

by:eric68
ID: 18870882
This is a description of the problem.
The table to be used for dinner is round, and seats 10 people. Your employer will be seated at the first position at the table. The other positions will be numbered clockwise from 2 to 10. The person seated to the left of your employer is in seat number 2, the person seated to the right of your employer is in seat number 10.

Persons seated next to each other must speak a common language. A person may speak to the person on the left in one common language, and speak to the person on the right in another language. The governments of the guests seated next to each other must have formally recognized each other.

The government of your employer has diplomatic relations with the governments of all of his guests. The government of a guest may or may not have diplomatic relations with the governments of all the other guests.

Two diplomats from the same country will have diplomatic relations with the same list of countries. A country will always have diplomatic relations with itself. Diplomats from the same country may or may not speak any languages in common.
0
 
LVL 1

Accepted Solution

by:
robear7nt earned 64 total points
ID: 18871203
Start out by thinking of the objects that would be involved here:

I would think you would have a Table object. What attributes would it have?
It might have a list of chairs usable as a seating arrangement.
It might need to check if two neighboring chairs had appropriate diplomats seating in them.

I would think you would have a Chair object. What attributes would it have?
It might be empty or it might have a single Diplomat assigned to it.
It might need to know which Chair is to it's left.
It might need to know which Chair is to it's right.

I would think you would have a Diplomat object. What attributes would it have?
It might have a list of languages that diplomat speaks.
It might have what government that diplomat is from.

I would think you would have a Government object. What attributes would it have?
It might have a list of friendly other governments.
It might have a list of it's diplomats.

Just some starting ideas, hope that gets you started.
0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 62 total points
ID: 18871587
I would probably approach this more abstractly,
looking to see if it could be transformed into a graph theory or set packing or block design or similar problem with a known soultion.
For somthing like this, I'd probably try to think about how I would want to solve it first, and then try to come up with a data structure that supports that method.
For example, if I wanted to start with a solution that did not satisfy all constraints
and apply transforms to try to get it to satisfy all constraints, I would want a data structure that made those transforms easy and detecting which constrants are satisfied easy.
I might also want ways of deciding which tranforms might be most efficacious
in reaching a solution, and I'd want a data structure that supported those ways.
0
What Is Transaction Monitoring and who needs it?

Synthetic Transaction Monitoring that you need for the day to day, which ensures your business website keeps running optimally, and that there is no downtime to impact your customer experience.

 
LVL 24

Expert Comment

by:sciuriware
ID: 18871658
This is homework!

;JOOP!
0
 
LVL 17

Expert Comment

by:rstaveley
ID: 18872949
Is this why the world is in such a mess?
0
 
LVL 24

Expert Comment

by:sciuriware
ID: 18872952
No, it's only Easter.

;JOOP!
0
 
LVL 24

Expert Comment

by:sciuriware
ID: 18872957
Seriously: we, on EE,  are not allowed to solve school and course problems for students.

;JOOP!
0
 
LVL 17

Expert Comment

by:rstaveley
ID: 18874578
I was concerned that C++ programmers were arranging seating for diplomats. God forbid they'd have us controlling weapon systems too.

Erm... How does that rand() function work? ....
0
 
LVL 24

Expert Comment

by:sciuriware
ID: 18874618
Remember the failure of the Patriot's in the 1st Gulf War?  Software!
0
 

Author Comment

by:eric68
ID: 18879792
Thank you for all of the suggestions.  I am not looking for someone to solve my homework for me, I am just trying to get some suggestions on how to approach this problem (using graphs, sets, etc.), and I thought that the best people to ask would be programmers in the field since we are aloud to use any available resources.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 18880918
>> I am just trying to get some suggestions on how to approach this problem

Did the posted comments help you get a better idea of what you'll need to do to implement this ?
Are you still unsure about certain parts ? (which ?)

It would maybe help if you would tell us how you think you'd do it. Explain with enough detail, so we can take a look at your approach, and give you tips on improving it if needed.
0
 
LVL 1

Expert Comment

by:robear7nt
ID: 18883837
eric68,

This is an "interactive" process. The experts offer answers, suggestions, and comments to your question, then monitor the question waiting to hear feedback from you. Your feedback is vital to getting your question answered. Since this is a homework assignment, the experts can't solve it for you, but they will help guide you towards YOU being able to complete your assignment. The example in rules is: "You can teach them to count, but you can not tell them 2 + 2 = 4".

Robert
0
 
LVL 6

Assisted Solution

by:carchitect
carchitect earned 62 total points
ID: 19162424
Its a multidimensional matrix and kind of work assignment problem.

Try something like.

http://en.wikipedia.org/wiki/Quadratic_assignment_problem
0
 
LVL 1

Assisted Solution

by:ajibola
ajibola earned 62 total points
ID: 19851721
how about using a graph algorithm. first of all the arrangement of the seating is needed to be established. Then the constraints. This is a Constraint Satisfaction Problem. http://en.wikipedia.org/wiki/Constraint_satisfaction_problem .Check out the examples there. You might need a heuristic like the value or 2 diplomats sitting close to each other, and far away. IF they have good relations then they should be closer there fore the heuristic value should be higher and if bad relations they should be apart, lower value. You should know what you want the heuristic to stand for, Closeness of diplomacy or seperation.
The goal of solving the problem is to make the most optimal selection at a point in time and when you get to a block back track. You could also apply forward checking for every decision made. This is when after a decision is made you take out all constraining posibilities, if you get to where the problem is unsolvable i.e some constrainst are not satisfied  you backtrack and take diff steps where necesary. you should do this from different starting points so as to reach a most feasible solution.
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
In this post we will learn different types of Android Layout and some basics of an Android App.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

728 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question