Congratulations! You have just won $9.3M in the lottery! Now you want to throw a huge party to celebrate. You want as many people as possible to come to your party.
Unfortunately, not everyone that you know likes everyone else....
For any two people X and Y:
The above is always true, and will constrain who you should invite to the party. Partly because you have a partner in this assignment, write this program with two different (but similar) sets of constraints. I recommend that you work together to figure out how best to solve the problem, then each take primary responsibility for one constraint set.
I will test your program with my data. To make this possible, your program must satisfy the following requirements:
+(meaning "likes") or
-(meaning "hates"). For example,
John +Mary -Bill +Sammeans that John likes Mary and Sam, but hates Bill (and is neutral about everyone else).
Sam, Sam will not be invited).
solve_1(file_name): This function will read its input from the given file, find the best solution it can according to constraint set #1, and return a list of names of people to invite. It does not ask for any input from the user, nor does it provide any output to the user.
solve_2(file_name): This function will read its input from the given file, find the best solution it can according to constraint set #2, and return a list of names of people to invite. It does not ask for any input from the user, nor does it provide any output to the user.
solve_ifunctions should each produce a reasonably good answer in less than a minute.
solve_ifunctions should almost certainly produce the best possible solutions.
main()is such a function.
I have specified the form of the input data, so that I can test your program with my own data.
I have not told you what kind of data structures to use to store and work with this data. Try to choose a representation that is easy to work with. You have lists, tuples, sets, and dictionaries, and combinations of these (lists of lists, sets of dictionaries, sets of lists of tuples, etc.). Your choice will have a major impact on how easy or difficult the program is to write, so think carefully about this.
This is an exponential problem. You can find a guaranteed optimal solution to small problems by trying every possible combination of people. For p people, that's 2p combinations. By using various tricks, you can reduce this number, but the problem will remain inherently exponential. That means that, given more than a couple dozen people, your program would run for a very, very long time, maybe years. We won't accept a program that takes years to run! Remember, the assignment is to find a reasonably good solution, in a reasonable amount of time.
How do you do this? Well, if you have (say) 100 friends, you cannot try all 2100 subsets of them. Instead, try to form various legal subsets of your friends--that is, subsets that satisfy whichever constraint you are using. You could try (depending on how you write the program) maybe as many as 10000 possible subsets. Think about ways you might create legal random subsets. Keep track of the largest legal subset you find, and that will be your answer.
It would be a good idea to read How Assignments Are Graded, but here's a summary: Do exactly what the assignment says to do, use good programming style, test your program carefully, zip up your program along with your unit tests, and turn it in via Blackboard. Late programs will lose points.
Your program is due before