Fall 2012, David Matuszek

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

** 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:

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

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

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

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(`

: 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.*file_name*)`solve_2(`

: 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.*file_name*)

- Given information about 100 people, your
`solve_`

functions should each produce a reasonably good answer in less than a minute.*i* - Given information about a small number of people (say, up to 15), your
`solve_`

functions should almost certainly produce the best possible solutions.*i*

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

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^{100} 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 **
**