Solved

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

Posted on 2007-04-07
16
636 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
  • 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
 
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
How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

 
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

Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

Join & Write a Comment

Suggested Solutions

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…

746 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

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now