Purposes of this assignment

• Give you some experience with more complex data structures
• Give you an opportunity to think about solving programming problems

Backstory

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....

General idea of the assignment

For any two people X and Y:

• X either likes Y, hates Y, or is neutral about Y.
• How X feels about Y is unrelated to how Y feels about X.

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.

Constraint set #1: Absolute constraints

• If X hates Y and Y comes to the party, X will not come to the party.
• X will not come to the party unless someone that X likes will also be at the party.

Constraint set #2: Relative constraint

• X will come to the party if and only if there are more people at the party that X likes, than there are people that X hates.

Detailed specification

Requirements

Critical requirements

I will test your program with my data. To make this possible, your program must satisfy the following requirements:

• Input will be from a text file. Each line of the file will represent one person. The first "word" on the line will be the name of a friend, and it will be followed by names of other people, each prefixed by a + (meaning "likes") or - (meaning "hates"). For example,
       John +Mary -Bill +Sam
means that John likes Mary and Sam, but hates Bill (and is neutral about everyone else).
• Names do not contain spaces. Spaces separate names.
• Every name is unique (there is only one person with each name).
• Lines may be any length and contain any number of prefixed names.
• Only people whose names appear first on the line may be invited (for example, John likes Sam, but if no line begins with Sam, Sam will not be invited).
• Define the following functions:
  • 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.
• Given information about 100 people, your solve_i functions should each produce a reasonably good answer in less than a minute.
• Given information about a small number of people (say, up to 15), your solve_i functions should almost certainly produce the best possible solutions.

Style requirements

• Functions should be of four types:
  • Functions that do input,
  • Functions that do output (and possibly a trivial amount of computation, to produce neater output),
  • Functions that do computation, and
  • Functions that mainly call other functions to do the work. This includes any functions whose job it is to do both computation and input/output. main() is such a function.
• All functions that do computation should be thoroughly tested (use TDD!). (The purpose of the above division of functions into four types is to try to ensure all significant computations get tested. Trivial computations, such as adding 1 in order to step through a list, are okay.)

Advice

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 2^p 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 2¹⁰⁰ 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.

Grading

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.

Due Date

Your program is due before 6am Friday, October 5.