Need help with project
I have this project, but I have no idea what to do. Can anyone point in the right direction, I just need a starting place and then I think I can probably work it out. Thank you.
King Arthur has 8 trusted knights: Agrawain, Bedivere, Dinadan, Galahad, Gwain, Lancelot, Mordred and Percival. They gather around a round table for important meetings. However there is one problem. Not all knights get along with each other. Some are friends while others are enemies. Hence, Arthur has to come up with a solution so that knights who are friends sit next to each other. Devise an algorithm that gives a seating chart. (Arthur does not have to be included in the solution since he can sit wherever he wants.)
Below is a list of friends of each knight. If a knight is not in another knights friend list, that means they are enemies.
Friends:
Agrawain: Galahad, Percival, Lancelot, Gwain
Bedivere: Dinadan, Galahad, Mordred, Lancelot
Dinadan: Bedivere, Lancelot, Percival, Gwain
Galahad: Agrawain, Bedivere, Lancelot, Mordred
Gwain: Dinadan, Agrawain, Mordred, Percival
Lancelot: Agrawain, Dinadan, Galahad, Bedivere
Mordred: Bedivere, Gwain, Percival, Galahad
Percival: Agrawain, Dinadan, Gwain, Mordred
King Arthur has 8 trusted knights: Agrawain, Bedivere, Dinadan, Galahad, Gwain, Lancelot, Mordred and Percival. They gather around a round table for important meetings. However there is one problem. Not all knights get along with each other. Some are friends while others are enemies. Hence, Arthur has to come up with a solution so that knights who are friends sit next to each other. Devise an algorithm that gives a seating chart. (Arthur does not have to be included in the solution since he can sit wherever he wants.)
Below is a list of friends of each knight. If a knight is not in another knights friend list, that means they are enemies.
Friends:
Agrawain: Galahad, Percival, Lancelot, Gwain
Bedivere: Dinadan, Galahad, Mordred, Lancelot
Dinadan: Bedivere, Lancelot, Percival, Gwain
Galahad: Agrawain, Bedivere, Lancelot, Mordred
Gwain: Dinadan, Agrawain, Mordred, Percival
Lancelot: Agrawain, Dinadan, Galahad, Bedivere
Mordred: Bedivere, Gwain, Percival, Galahad
Percival: Agrawain, Dinadan, Gwain, Mordred
I read the problem and found a good seating arrangement in just a couple minutes. Now I ask myself... How did I do that? What was my thought process? Can my thought process be written down into steps? This is the start of a very simple algorithm. And never once did the idea of an undirected graph enter into thought... :P
Although you never thought "undirected graph", the data is in fact an undirected graph.
I solved it with a simple recursive function, equivalent to a DFS graph traversal, which, if you think about it, is almost certainly what you did on paper.
I solved it with a simple recursive function, equivalent to a DFS graph traversal, which, if you think about it, is almost certainly what you did on paper.
Last edited on
What's google?
Anyway, as Manga said, it doesn't matter.
Just solve it on paper.
Then implement that algorithm in code.
You probably need to use recursion since you will need backtracking.
Anyway, as Manga said, it doesn't matter.
Just solve it on paper.
Then implement that algorithm in code.
You probably need to use recursion since you will need backtracking.
In computer science, a "graph" is a set of nodes and edges that connect the nodes. A "directed" graph is one where the edges have a direction, so you might connect A to B, but not B to A. An undirected graph is when the edges connect the nodes in both directions.
For a visual, consider a bunch of small islands (nodes) connected by bridges (edges). If the bridges are one-way then the graph is directed. If they are two-way bridges then the graph is undirected.
For this problem, the nodes are the knights. If two knights are friends then they are connected by an edge.
For a visual, consider a bunch of small islands (nodes) connected by bridges (edges). If the bridges are one-way then the graph is directed. If they are two-way bridges then the graph is undirected.
For this problem, the nodes are the knights. If two knights are friends then they are connected by an edge.
But I think this assignment is flawed. It states King Arthur can sit anywhere. Why not? He is the king after all. But if memory servers... Didn't King Arthur and Lancelot not get on to well? I think Lancelot was banging the king's wife. Maybe we should burn that bridge and keep them apart.
Don't most homework task have fictional nonsense backstory, like "students with marks"?
Leaving Arthur out is a restriction. We could put enemies close to each other, if we are allowed to squeeze Arthur between them.
Leaving Arthur out is a restriction. We could put enemies close to each other, if we are allowed to squeeze Arthur between them.
i don't know that you need all that complexity.
solution, circular:
Agrawain: Galahad, Percival, Lancelot, Gwain
Galahad: Agrawain, Bedivere, Lancelot, Mordred
Bedivere: Dinadan, Galahad, Mordred, Lancelot
Lancelot: Agrawain, Dinadan, Galahad, Bedivere
Dinadan: Bedivere, Lancelot, Percival, Gwain
Gwain: Dinadan, Agrawain, Mordred, Percival
Mordred: Bedivere, Gwain, Percival, Galahad
Percival: Agrawain, Dinadan, Gwain, Mordred
how? just pick one, and then pick the next guy on his list that hasn't been seated yet. greedy algorithm. the last guy has to be friends with the first, or it isnt valid. There will be invalid solutions so you have to back-track to try something else if you get stuck. Its the same idea, you just don't need to build a complex data structure to resolve it.
edit.. messed it up, lol... fixed
solution, circular:
Agrawain: Galahad, Percival, Lancelot, Gwain
Galahad: Agrawain, Bedivere, Lancelot, Mordred
Bedivere: Dinadan, Galahad, Mordred, Lancelot
Lancelot: Agrawain, Dinadan, Galahad, Bedivere
Dinadan: Bedivere, Lancelot, Percival, Gwain
Gwain: Dinadan, Agrawain, Mordred, Percival
Mordred: Bedivere, Gwain, Percival, Galahad
Percival: Agrawain, Dinadan, Gwain, Mordred
how? just pick one, and then pick the next guy on his list that hasn't been seated yet. greedy algorithm. the last guy has to be friends with the first, or it isnt valid. There will be invalid solutions so you have to back-track to try something else if you get stuck. Its the same idea, you just don't need to build a complex data structure to resolve it.
edit.. messed it up, lol... fixed
Last edited on
| jonnin wrote: |
|---|
| The last guy has to be friends with the first, or it isnt valid |
Perhaps not. Consider this from the assignment:
| phazed99 wrote: |
|---|
| Arthur does not have to be included in the solution since he can sit wherever he wants. |
So once you find the last knight, you can sit Arthur between him and the first knight.
A: B, H, D, F B: A, C, D, G C: E, B, G, D D: A, E, B, C E: C, D, H, F F: E, A, G, H G: C, F, H, B H: A, E, F, G |
8 nodes. Each connects to 4 nodes and is not connected to 3 nodes. Favourable odds.
| dhayden wrote: |
|---|
| So once you find the last knight, you can sit Arthur between him and the first knight. |
That's a good point, but it's definitely unclear.
My solution ensures that the first and last knights are friends, which yields 60 solutions. If I change it so the first and last knights do not need to be friends, it yields 100 solutions.
This is my graph representation, using the first letter of the knights' names except for using H for Gwain.
|
|
Last edited on
i been playing around with this for 2 days and im having issues with stack overflow. Is it like a bad idea to call other functions from inside of a recursive function?
Last edited on
| My solution ensures that the first and last knights are friends, which yields 60 solutions. If I change it so the first and last knights do not need to be friends, it yields 100 solutions. |
i'm not getting anywhere near that many results. I fixed overflow problem. I'm just wondering if you're getting some duplicate results but since its a circle some of the results are the same just they seem different bc the start and the ends are different. like if they were shifted over until they started at the same person they'd be the same.
part of the issue i'm coming up against is the order in which the friends are searched. like if i start at friend 0 and search up the results are different if i do the opposite.
edit nm; i changed it to look randomly in the friend list and i'm getting way more unique results;
ok so now im getting over 90 results with the person in the first position always being the same. and i have a pretty deep verification process so i'd imagine that theyre good results.
Last edited on
| markyrocks wrote: |
|---|
| i'm not getting anywhere near that many results. |
How many are you getting?
I don't think 8*8 = 64 has anything to do with it, more like 8! = 40320.
Obviously there's not that many due to the restrictions.
But 60 doesn't seem too high.
As for rotations being equivalent, I start all of the arrangements with A so that'a not a problem.
I'm not sure what you mean by the "inside edges", but as I said I get 60 if the first and last in line (closing the circle) are friends and 100 if they don't need to be (because King Arthur can sit between them).
Here's the 60 I get:
A G B L D H M P A G B L D P M H A G B M H P D L A G B M P H D L A G L B D H M P A G L B D P M H A G L B M H D P A G L B M P D H A G L D B M H P A G L D B M P H A G M B L D H P A G M B L D P H A G M H P D B L A G M P H D B L A H D B L G M P A H D L B G M P A H D L G B M P A H D P M B G L A H D P M B L G A H D P M G B L A H M B G L D P A H M G B L D P A H M G L B D P A H M P D B G L A H M P D B L G A H M P D L B G A H P D B M G L A H P D L B M G A H P M B D L G A H P M G B D L A L B D H P M G A L B D P H M G A L B G M H D P A L B G M P D H A L D B G M H P A L D B G M P H A L D H P M B G A L D P H M B G A L G B D H M P A L G B D P M H A L G B M H D P A L G B M P D H A L G M B D H P A L G M B D P H A P D B L G M H A P D H M B G L A P D H M B L G A P D H M G B L A P D L B G M H A P D L G B M H A P H D B M G L A P H D L B M G A P H M B D L G A P H M G B D L A P M B G L D H A P M G B L D H A P M G L B D H A P M H D B G L A P M H D B L G A P M H D L B G Number of solutions: 60 |
| Is it like a bad idea to call other functions from inside of a recursive function? |
As long as those functions aren't also recursive it shouldn't matter.
now the question is why am i getting more unique results than you ;-) and i don't think its an issue with my verification function. I checks if every person in the list is unique so no repeats and it checks if A is friends with B and it checks if the people on the edges are friends.
and i'm checking the stored results against itself for repeats.
ya i'm fairly certain that theres about 120 valid results if the first postion is always the same
and i'm checking the stored results against itself for repeats.
ya i'm fairly certain that theres about 120 valid results if the first postion is always the same
Last edited on
| ya i'm fairly certain that theres about 120 valid results if the first postion is always the same |
It's kind of silly to say you're "fairly certain" when someone with vastly more experience than you says otherwise. It's a simple program that took me less than five minutes to write. I'm "fairly certain" that it's correct.
Anyway, put your money where your mouth is.
I may very well have made a mistake.
Post your results.
Just showing one that isn't in my list is enough.
Last edited on